Question

In Java:

In the SingleLinkedList defined in the textbook Section 2.5 (named KWSingleLinkedList there), add the following methods:

KWSingleLinkedList<String> Names = new KWSingleLinkedList,.();

names.addFirst("Sam");

names.addFirst("Harry");

names.addFirst("Dick");

names.addFirst("Tom");

• Write method indexOf.
• Write the remove method whose method heading follows

/** Remove the first occurrence of element item.
    @param item The item to be removed
    @return true if item is found and removed; otherwise, return false.
*/
public boolean remove(E item)

• Write the following method add

/** Insert a new item before the one at position index, starting at 0
     for the list head. The new item is inserted between the one at
     position index‐1 and the one formerly at position index.
    @param index The index where the new item is to be inserted
    @param item The item to be inserted
    @throws IndexOutOfBoundsException if the index is out of range
*/
public void add(int index, E item)

• Write a main program to test and demonstrate the functions of the class.

Answer 1

public class LinkedListDemo { public static void main(String[] args) { KWSingleLinkedList<String> names = new KWSingleLinkedList(); names.addFirst("Sam"); names.addFirst("Harry"); names.addFirst("Dick"); names.addFirst("Tom"); names.printList(); System.out.println("Removing Harry: " + names.remove("Harry")); names.printList(); System.out.println("Adding Srinu at index 2: "); names.add(2, "Srinu"); names.printList(); } } //Linked list class class KWSingleLinkedList<E> { private Node<E> head = null; //adding a value public void addFirst(E value) { //first node if (head == null) { head = new Node(value); return; } //insert at first Node temp = new Node(value); temp.setNext(head); head = temp; } /** * Print the entire list */ //print the list public void printList() { System.out.println(); System.out.printf("List::: "); Node temp = head; //traverse up to end while (temp != null) { System.out.print(temp.getValue() + " "); //print value temp = temp.getNext(); } System.out.println(); System.out.println(); } /** * Remove the first occurrence of element item. * * @param item The item to be removed * @return true if item is found and removed; otherwise, return false. */ public boolean remove(E item) { //empty list if (head == null) { return false; } //remove at first if (head.getValue().equals(item)) { head = head.getNext(); return true; } Node<E> temp = head; Node<E> prev = null; Node<E> prevToPrev = null; boolean found = false; //traverse to end while (temp != null) { //found value if (temp.getValue().equals(item)) { prevToPrev = prev; //hold pointer to prev of item found = true; } prev = temp; temp = temp.getNext(); if (found) { break; } } //remove item if (prevToPrev != null) { prev.setNext(null); prevToPrev.setNext(temp); return true; } return false; } /** * Insert a new item before the one at position index, starting at 0 * for the list head. The new item is inserted between the one at * position index‐1 and the one formerly at position index. * * @param index The index where the new item is to be inserted * @param item The item to be inserted * @throws IndexOutOfBoundsException if the index is out of range */ public void add(int index, E item) { //throw index bounds exception if invalid index if (index < 0 || index > getSize()) { throw new IndexOutOfBoundsException(); } //add first if index is 0 if (index == 0) { addFirst(item); return; } int count = 0; Node<E> temp = head; Node<E> prev = null; //traverse until count is less than index while (temp != null && count < index) { prev = temp; //hold prev pointer of temp count++; temp = temp.getNext(); } Node<E> newNode = new Node<>(item); //creating new node //inserting at given index prev.setNext(newNode); newNode.setNext(temp); } public int getSize() { Node<E> temp = head; int size = 0; while (temp != null) { size++; temp = temp.getNext(); } return size; } } class Node<T> { private T value; private Node next; public Node(T value) { this.value = value; this.next = null; } public T getValue() { return value; } public Node getNext() { return next; } public void setNext(Node next) { this.next = next; } }