Data Structures and Algorithms

Add the following functions to the class LinkedList ( The code must be syntactically correct.)

Insert functions into code

1. int getLength(): returns the number of items in a LinkedList holding integer data type.
2. boolean search (int element) : searches for the element in the LinkedList and returns true if found, otherwise false is returned.
   1. Implement the search function iteratively
   2. Use recursion to implement the search function

// file: SinglyLinkedListDemoApp.java

public class SinglyLinkedListDemoApp { public static void main(String[] args) { LinkedList numList = new LinkedList(); Node nodeA = new Node(66); Node nodeB = new Node(99); Node nodeC = new Node(44); Node nodeD = new Node(95); Node nodeE = new Node(42); Node nodeF = new Node(17);

numList.append(nodeB); // Add 99 numList.append(nodeC); // Add 44, make the tail numList.append(nodeE); // Add 42, make the tail

numList.prepend(nodeA); // Add 66, make the head

numList.insertAfter(nodeC, nodeD); // Insert 95 after 44 numList.insertAfter(nodeE, nodeF); // Insert 17 after tail (42)

// Output list System.out.print("List after adding nodes: "); numList.printList();

// Remove the tail node, then the head node numList.removeAfter(nodeE); numList.removeAfter(null);

// Output final list System.out.print("List after removing nodes: "); numList.printList(); } }

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

// file: SinglyLinkedList.java

class Node { public int data; public Node next;

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

class LinkedList { private Node head; private Node tail; public LinkedList() { head = null; tail = null; } public void append(Node newNode) { if (head == null) { head = newNode; tail = newNode; } else { tail.next = newNode; tail = newNode; } } public void prepend(Node newNode) { if (head == null) { head = newNode; tail = newNode; } else { newNode.next = head; head = newNode; } } public void printList() { Node node = head; while (node != null) { System.out.print(node.data + " "); node = node.next; } System.out.println(); } public void insertAfter(Node currentNode, Node newNode) { if (head == null) { head = newNode; tail = newNode; } else if (currentNode == tail) { tail.next = newNode; tail = newNode; } else { newNode.next = currentNode.next; currentNode.next = newNode; } } public void removeAfter(Node currentNode) { if (currentNode == null && head != null) { // Special case: remove head Node succeedingNode = head.next; head = succeedingNode; if (succeedingNode == null) { // Last item was removed tail = null; } } else if (currentNode.next != null) { Node succeedingNode = currentNode.next.next; currentNode.next = succeedingNode; if (succeedingNode == null) { // Remove tail tail = currentNode; } } } }