The goal of this lab is to get familiar with implementing methods of a LinkedList.

In this lab, you need to implement some supporting methods in the LinkedList class. The first method public void insertAfter(int givenData, int newData) inserts a Node with newData after the Node with givenDatain the linked list.

The second method public void remove(int current) removes the Node that contains current from the LinkedList. You need to make sure your program handles the special case of deleting the head of the list.

Next, the method public int length() computes the length of the linked list. The last method public int get(int index) returns the item in the list specified by the index. You need to make sure your program handles the cases where the index is out of the range. In those cases, return -1.

The template contains the required code to test your implementation. So go ahead and find the comment //Your code here. You need to add codes for the specified methods only.

Sample Input/Output 11 23 31 -1 37 41 should output the following:

The list contains: [11, 23, 31] The length of the list is 3 Inserting a new node after the first node. Now the list contains:[11, 37, 23, 31] Inserting new data after the third node. Now the list contains:[11, 37, 23, 41, 31] The length of the list is 5 Removing the second element: Now the list contains:[11, 23, 41, 31] Removing the head Now the list contains:[23, 41, 31]

Code:

Node.java

class Node{ int data; Node next; public Node(int data){ this.data = data; } }

LinkedListTest.java

import java.util.Scanner;

public class LinkedListTest{ public static void main(String args[]){ LinkedList linkedList = new LinkedList(); Scanner input = new Scanner(System.in); //System.out.println("Enter the data for the linked list:"); System.out.println("Appending nodes to the list:"); while(true){ int data = Integer.parseInt(input.next()); if(data == -1) break; linkedList.append(data); } System.out.print("The list contains: "); linkedList.print(); System.out.printf("The length of the list is %d%n", linkedList.length()); System.out.println("Inserting a new node after the first node."); int newData = Integer.parseInt(input.next()); linkedList.insertAfter(linkedList.get(0), newData); System.out.print("Now the list contains:"); linkedList.print(); System.out.println("Inserting a new data after the third node."); newData = Integer.parseInt(input.next()); linkedList.insertAfter(linkedList.get(2), newData); System.out.print("Now the list contains:"); linkedList.print(); System.out.printf("The length of the list is %d%n", linkedList.length()); System.out.println("Removing the second element:"); linkedList.remove(linkedList.get(1)); System.out.print("Now the list contains:"); linkedList.print(); System.out.println("Removing the head"); linkedList.remove(linkedList.get(0)); System.out.print("Now the list contains:"); linkedList.print(); } }

LinkedList.java

public class LinkedList { Node head;

// inserts data to the end of the list only using the head pointer public void append(int data){ Node newNode = new Node(data); if(head == null){ head = newNode;

} else { Node currentNode = head; while(currentNode.next != null){ currentNode = currentNode.next; } currentNode.next = newNode; } } // inserts data to the beginning of the list public void prepend(int data){ if(head == null){ Node newNode = new Node(data); head = newNode; return; } Node newNode = new Node(data); newNode.next = head; head = newNode; } // print the linked list elements public void print() { Node currentNode = head; System.out.printf("["); while (currentNode.next != null) { System.out.printf("%d, ", currentNode.data); currentNode = currentNode.next; } System.out.printf("%d]%n", currentNode.data); } // insert a new data after the given one public void insertAfter(int givenData, int newData){ Node currentNode = head; while(currentNode != null) { // check if given data found // if found then insert new data if(currentNode.data == givenData){ Node t = new Node(newData); t.next = currentNode.next; currentNode.next = t; return; } currentNode = currentNode.next; } // if given data not found if (currentNode ==null) { System.out.println("Given Node not found"); } } } // Removes the Node with the given data public void remove(int current) { // if head is null if (head == null) { return; } // if we need to remove first node else if (head.data == current) { Node t = head.next; head.next = null; head = t; return; } // else scan for desire node Node prevNode = null; Node currentNode = head; while(currentNode != null) { // if desire node found the remove it if (currentNode.data == current) { prevNode.next = currentNode.next; currentNode.next = null; } //else go for next node prevNode = currentNode; currentNode = currentNode.next; }

} // counts the length of the list public int length(){ // Your code here

} // get an item from the list specified by the index public int get(int index){ // Your code here } }