Question

Outcomes: • Write a Java program that implements linked list algorithms

can u also show thee testing code

--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

This is the starter code

import java.util.NoSuchElementException;

// Put your prologue comments here

public class LinkedAlgorithms {

  
   private class Node {
       private String data;
       private Node next;

       private Node(String data) {
           this.data = data;
           this.next = null;
       }
   }

   public Node head;
   public int numItems;

   /**
   * Creates the empty list.
   */
   public LinkedAlgorithms() {
   }

   /**
   * Creates a list containing all the elements of the passed array.
   * {@code data[0]} will be the first element of the list, {@code data[1]} will
   * be the second element of the list, and so on.
   *
   * @param data The array of values
   * @throws NullPointerException - data is null
   */
   public LinkedAlgorithms(String[] data) {
   }

   /**
   * Constructs a deep copy of the linked list {@code original}
   *
   * @param original The list to be copied
   * @throws NullPointerException - original is null
   */
   public LinkedAlgorithms(LinkedAlgorithms original) {
   }

   /**
   * Returns array with all the elements.
   *
   * @return Array containing all elements.
   */
   public String[] toArray() {
       return null;
   }

   /**
   * Formats the elements in the list using leading and ending brackets (i.e., []), with the values comma separated.
   * There will be one space between each of these but none at the beginning nor at the end.
   * Some examples:
   * if the list is empty, toString() gives []
   * if the list has these three elements in this order: "hello", "world", "everyone", then the result should be
   * [hello, world, everyone]
   */
   @Override
   public String toString() {
       return null;
   }

   /**
   * Returns the number of items in the list
   *
   * @return Number of items in the list
   */
   public int size() {
       return 0;
   }

   /**
   * Determines if two lists contain exactly the same values, in exactly the same
   * order.
   *
   * @return {@code true} if and only if obj is an list that is equivalent to the
   * incoming list.
   */
   public boolean equalsLinkedList(LinkedAlgorithms obj) {
       return false;
   }

   /**
   * Determines if {@code key} is in the linked list.
   *
   * @param key The value to be found
   * @return true if and only if {@code key} is in the list
   */
   public boolean contains(String key) {
       return false;
   }

   /**
   * Determines the index of {@code key}. -1 is returned if the value is not
   * present in the linked list. If {@code key} is present present more than once,
   * the first index is returned.
   *
   * @param key The value to be found
   * @return The index of the {@code key}
   */
   public int find(String key) {
       return 0;
   }

   /**
   * Returns the value of the first element of the list.
   *
   * @return The first element of the list.
   * @throws NoSuchElementException the list is empty
   */
   public String getFirst() {
       return null;
   }

   /**
   * Returns the value of the last element of the list.
   *
   * @return The last element of the list.
   * @throws NoSuchElementException the list is empty
   */
   public String getLast() {
       return null;
   }

   /**
   * Returns the value of the {@code ith} element of the list (0 based).
   *
   * @param i The target index
   * @return The value of the ith element of the list.
   * @throws IndexOutOfBoundsException {@code i} is illegal
   */
   public String getAt(int i) {
       return null;
   }

   /**
   * Adds {@code data} to the beginning of the list. All other values in the list
   * remain but they are "shifted to the right."
   *
   * @param data The value to add to the list
   */
   public void insertFirst(String data) {
   }

   /**
   * Adds {@code data} to the end of the list. All other values in the list remain
   * in their current positions.
   *
   * @param data The value to add to the list
   */
   public void insertLast(String data) {
   }

   /**
   * Adds data to a specific spot in the list. The values in the list remain
   * intact but {@code data} is inserted in the list at position {@code i}. When
   * {@code i=0}, the result is the same as {@code insertFirst}.
   *
   * @param i The target index
   * @param data The value to add to the list
   * @throws IndexOutOfBoundsException {@code i} is illegal
   */
   public void insertAt(int i, String data) {
   }

   /**
   * Adds {@code newData} the position immediately preceding {@code existingData}.
   * If the {@code existingData} appears multiple times, only the first one is
   * used.
   *
   * @param newData The value to add to the list
   * @param existingData The value used to control where insertion is to take
   * place
   * @throws NoSuchElementException {@code existingData} is not in the list
   */
   public void insertBefore(String newData, String existingData) {
   }

   /**
   * Adds {@code newData} the position immediately after {@code existingData}. If
   * the {@code existingData} appears multiple times, only the first one is used.
   *
   * @param newData The value to add to the list
   * @param existingData The value used to control where insertion is to take
   * place
   * @throws NoSuchElementException {@code existingData} is not in the list
   */
   public void insertAfter(String newData, String existingData) {
   }

   /**
   * Removes the first element of the list. The remaining elements are kept in
   * their existing order.
   *
   * @return The value removed from the list
   * @throws NoSuchElementException if the list is empty.
   */
   public String removeFirst() {
       return null;
   }

   /**
   * Removes the last element of the list. The remaining elements are kept in
   * their existing order.
   *
   * @return The value removed from the list
   * @throws NoSuchElementException if the list is empty.
   */
   public String removeLast() {
       return null;
   }

   /**
   * Removes the ith element of the list. The remaining elements are kept in their
   * existing order.
   *
   * @param i The target index
   * @return The value removed from the list
   * @throws IndexOutOfBoundsException i does not represent a legal index
   */
   public String removeAt(int i) {
       return null;
   }

   /**
   * Removes the first occurrence of data in the linked list.
   *
   * @param data The value to be removed.
   * @return {@code true} if and only if {@code data} was removed
   */
   public boolean removeFirstOccurrenceOf(String data) {
       return false;
   }

   /**
   * Removes the all occurrence of {@code data} in the linked list.
   *
   * @param data The value to be removed.
   * @return The number of times {@code data} was removed
   */
   public int removeAllOccurrencesOf(String data) {
       return 0;
   }

   /**
   * Reverses the elements in the incoming linked list.
   */
   public void reverse() {
   }

   /**
   * Puts all the elements in the list to uppercase.
   */
   public void toUpper() {
   }

   /**
   * Returns the concatenation of all strings, from left to right. No extra spaces
   * are inserted.
   *
   * @return Concatenation of all string in the list
   */
   public String getConcatenation() {
       return null;
   }

   /**
   * Returns the alphabetically last value in the list.
   *
   * @return The alphabetically last value in the list
   * @throws NoSuchElementException list is empty
   */
   public String getAlphabeticallyLast() {
       return null;
   }

   /**
   * Returns the index where the alphabetically last value value resides. If this
   * value appears multiple times, the first occurrence is used.
   *
   * @return Index value of where maximum value resides
   * @throws NoSuchElementException list is empty
   */
   public int indexOfAlphabeticallyLast() {
       return 0;
   }

   /*
   * Determines if the two list contain elements that have exactly the same
   * value, with the same list sizes, but with the elements perhaps in different order.
   *
   * @returns true only if the two lists are permutations of one another.
   */
   public boolean anagrams(LinkedAlgorithms other) {
       return false;
   }

   public static void main(String[] args) {
       String[] items = { "hello", "world" };
       LinkedAlgorithms LL1 = new LinkedAlgorithms();
       LinkedAlgorithms LL2 = new LinkedAlgorithms(items);
       LinkedAlgorithms LL3 = new LinkedAlgorithms(LL1);
   }
}

Answer 1

ADT Single Linked List

Finite number of nodes having the same type. Nodes are linked together as in a chain with the help of a field in them. A special variable points to the first element of the chain. A linked list provides an alternative to an array-based structure. It is a collection of nodes that collectively form linear sequence.

Operations:

init_l(cur) – initialise a list
  empty_l(head) – boolean function to return true if list pointed to by head is empty
  atend_l(cur) – boolean function to return true if cur points to the last node in the list
  insert_front(target, head) – insert the node pointed to by target as the first node of the list pointed to by head
  insert_after(target, prev) – insert the node pointed to by target after the node pointed to by prev
  delete_front(head) – delete the first element of the list pointed to by head
  delete_after(prev) – delete the node after the one pointed to by prev

*
Java Program to Implement Singly Linked List
*/

import java.util.*;

/* Class Node */
class Node
{
protected int data;
protected Node link;

/* Constructor */
public Node()
{
link = null;
data = 0;
}
/* Constructor */
public Node(int d,Node n)
{
data = d;
link = n;
}
/* Function to set link to next Node */
public void setLink(Node n)
{
link = n;
}
/* Function to set data to current Node */
public void setData(int d)
{
data = d;
}
/* Function to get link to next node */
public Node getLink()
{
return link;
}
/* Function to get data from current Node */
public int getData()
{
return data;
}
}

/* Class linkedList */
class linkedList
{
protected Node start;
protected Node end ;
public int size ;

/* Constructor */
public linkedList()
{
start = null;
end = null;
size = 0;
}
/* Function to check if list is empty */
public boolean isEmpty()
{
return start == null;
}
/* Function to get size of list */
public int getSize()
{
return size;
}
/* Function to insert an element at begining */
public void insertAtStart(int val)
{
Node nptr = new Node(val, null);
size++ ;
if(start == null)
{
start = nptr;
end = start;
}
else
{
nptr.setLink(start);
start = nptr;
}
}
//====================================================================
/* Function to insert an element at end */
public void insertAtEnd(int val)
{
Node nptr = new Node(val,null);
size++ ;
if(start == null)
{
start = nptr;
end = start;
}
else
{
end.setLink(nptr);
end = nptr;
}
}
/* Function to insert an element at position */
public void insertAtPos(int val , int pos)
{
Node nptr = new Node(val, null);
Node ptr = start;
pos = pos - 1 ;
for (int i = 1; i < size; i++)
{
if (i == pos)
{
Node tmp = ptr.getLink() ;
ptr.setLink(nptr);
nptr.setLink(tmp);
break;
}
ptr = ptr.getLink();
}
size++ ;
}
/* Function to delete an element at position */
public void deleteAtPos(int pos)
{
if (pos == 1)
{
start = start.getLink();
size--;
return ;
}
if (pos == size)
{
Node s = start;
Node t = start;
while (s != end)
{
t = s;
s = s.getLink();
}
end = t;
end.setLink(null);
size --;
return;
}
Node ptr = start;
pos = pos - 1 ;
for (int i = 1; i < size - 1; i++)
{
if (i == pos)
{
Node tmp = ptr.getLink();
tmp = tmp.getLink();
ptr.setLink(tmp);
break;
}
ptr = ptr.getLink();
}
size-- ;
}
/* Function to display elements */
public void display()
{
System.out.print("\nSingly Linked List = ");
if (size == 0)
{
System.out.print("empty\n");
return;
}
if (start.getLink() == null)
{
System.out.println(start.getData() );
return;
}
Node ptr = start;
System.out.print(start.getData()+ "->");
ptr = start.getLink();
while (ptr.getLink() != null)
{
System.out.print(ptr.getData()+ "->");
ptr = ptr.getLink();
}
System.out.print(ptr.getData()+ "\n");
}
}

/* Class SinglyLinkedList */
public class SinglyLinkedList
{
public static void main(String[] args)
{
Scanner scan = new Scanner(System.in);
/* Creating object of class linkedList */
linkedList list = new linkedList();
System.out.println("Singly Linked List Test\n");
char ch;
/* Perform list operations */
do
{
System.out.println("\nSingly Linked List Operations\n");
System.out.println("1. insert at begining");
System.out.println("2. insert at end");
System.out.println("3. insert at position");
System.out.println("4. delete at position");
System.out.println("5. check empty");
System.out.println("6. get size");
int choice = scan.nextInt();
switch (choice)
{
case 1 :
System.out.println("Enter integer element to insert");
list.insertAtStart( scan.nextInt() );
break;
case 2 :
System.out.println("Enter integer element to insert");
list.insertAtEnd( scan.nextInt() );
break;
case 3 :
System.out.println("Enter integer element to insert");
int num = scan.nextInt() ;
System.out.println("Enter position");
int pos = scan.nextInt() ;
if (pos <= 1 || pos > list.getSize() )
System.out.println("Invalid position\n");
else
list.insertAtPos(num, pos);
break;
case 4 :
System.out.println("Enter position");
int p = scan.nextInt() ;
if (p < 1 || p > list.getSize() )
System.out.println("Invalid position\n");
else
list.deleteAtPos(p);
break;
case 5 :
System.out.println("Empty status = "+ list.isEmpty());
break;
case 6 :
System.out.println("Size = "+ list.getSize() +" \n");
break;
default :
System.out.println("Wrong Entry \n ");
break;
}
/* Display List */
list.display();
System.out.println("\nDo you want to continue (Type y or n) \n");
ch = scan.next().charAt(0);
} while (ch == 'Y'|| ch == 'y');
}
}

Save the program by the name SinglyLinkedList.java

Output :