For the class LinkedList<E> from \"LinkedList.java\"), add the following methods
ID: 3757795 • Letter: F
Question
For the class LinkedList<E> from "LinkedList.java"), add the following methods:
public void insertAfter(int k, E e) -- inserts the item 'e' AFTER the node at index k (where k is 0-based). For example, if the list contained [4, 8, 2, 7] and insertAfter(1, 9) is called, the method changes the list to [4, 8, 9, 2, 7]. The method also throws an IndexOutOfBoundsException if the index is out of range (k < 0 || k >= size()).
public boolean findMove(E e) -- Receives a value to be searched ('e') in the list, and returns true if the value exists in the list, or false otherwise. IN ADDITION, if the value exists in the list, the list node which has the value is physically moved to the front of the list. For example, if the list contained [4, 7, 2, 8] and findMove(2) is called in this list, the method returns true and the list changes to [2, 4, 7, 8].
Note that you must accomplish this task ONLY by manipulating the Node references; NO new node should be created, nor should you delete a node and add a new node.
public Iterator<E> iterator(int index) -- returns an iterator starting at the specified position ('index') in the list. The specified index is 0-based.
code
Explanation / Answer
Please find the required solution:
import java.util.Iterator;
public class LinkedList<E extends Comparable<E>> implements Iterable<E> {
// instance data members of list
private Node head; // reference to the first node
private int N; // number of elements stored in the list
/*******************
* nested class Node
*******************/
private class Node {
// instance data members of Node
public E item;
public Node next;
// constructors for Node
public Node() {
item = null;
next = null;
}
public Node(E e, Node ptr) {
item = e;
next = ptr;
}
}// end class Node
/***************************
* nested class ListIterator
***************************/
private class ListIterator implements Iterator<E> {
// instance data member of ListIterator
private Node current;
// constructors for ListIterator
public ListIterator() {
current = head; // head in the enclosing list
}
public boolean hasNext() {
return current != null;
}
public E next() {
E ret = current.item;
current = current.next;
return ret;
}
public void remove() { /* omitted because optional */
}
}// end class ListIterator
/***** back to class LinkedList *******/
public LinkedList() {
head = null;
N = 0;
}
public Iterator<E> iterator() {
return new ListIterator();
}
public void add(E e) {
// First check the parameter is null.. if so, throw an exception.
if (e == null)
throw new NullPointerException();
// The element is pushed in the front, and N is incremented.
head = new Node(e, head);
++N;
}
public void append(E newItem) {
if (newItem == null)
throw new NullPointerException();
// (*) special case
if (head == null) {
head = new Node(newItem, null);
N++;
} else { // (*) general case
// Step 1: declare ptr and bring it to the last node in the list
Node ptr;
for (ptr = head; ptr.next != null; ptr = ptr.next) {
}
// Step 2: add a new node at the end of the list
ptr.next = new Node(newItem, null);
++N;
}
}
public void remove(E e) {
if (e == null)
throw new NullPointerException();
// (*) special case (2/one node with e)
if (head != null && head.item.equals(e)) {
head = null;
N--;
} else { // (*) general case (3) -- this also covers the case for empty
// list
Node temp;
// Step 1: bring temp to one node before the node with e.
for (temp = head; temp != null && !temp.next.item.equals(e); temp = temp.next) {
} // empty body
// Step 2: if temp is still in the list, then remove
if (temp != null) {
temp.next = temp.next.next;
--N;
}
}
}
public int size() {
return N;
}
public String toString() {
String ret = "";
for (Node ptr = head; ptr != null; ptr = ptr.next) {
ret = ret + ptr.item + " ";
}
return ret;
}
public boolean isEmpty() {
return N == 0;
}
// ********************************************
// WRITE YOUE CODE BELOW
// ********************************************
public void insertAfter(int k, E e) {
int currentPositon = 0;
Node ptr = head;
for (; ptr != null; ptr = ptr.next) {
if (k == currentPositon)
break;
currentPositon++;
}
Node tempNode = ptr.next;
Node insertNode = new Node(e, null);
ptr.next = insertNode;
insertNode.next = tempNode;
}
public boolean findMove(E e) {
for (Node ptr = head; ptr != null; ptr = ptr.next) {
if (ptr.item.equals(e)) {
return true;
}
}
return false;
}
// ----------------------------
// main()
// ----------------------------
public static void main(String[] args) {
}
}