Q. How to create a LinkedList from scratch A. Adding Removing Step 1: The node that stores the data and the reference to the next Node.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
package linked.list; public class Node<E> { E data; Node<E> next; public Node(E data, Node<E> next) { this.data = data; this.next = next; } public E getData() { return data; } public void setData(E data) { this.data = data; } public Node<E> getNext() { return next; } public void setNext(Node<E> next) { this.next = next; } @Override public String toString() { return "data=" + data + ", next=" + next; } } |
Step 2: The LinkedList with add and remove logic.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 |
package linked.list; public class SinglyLinkedList<E> { private Node<E> head, tail; protected long size; public SinglyLinkedList() { super(); this.head = null; this.tail = null; this.size = 0; } public void add(E data) { if (data == null) { throw new NullPointerException("Cannot add null data!!"); } if (!isEmpty()) { // adding subsequent nodes Node<E> current = this.tail; this.tail = new Node<E>(data, null); current.next = this.tail; } else { // adding the first node this.tail = new Node<E>(data, null); this.head = this.tail; } size++; } public boolean remove(E data) { if (isEmpty()) { throw new IllegalStateException("Cannot remove() from an empty list!!"); } boolean hasRemoved = false; //set both pointers to head to start with Node<E> prev = this.head; Node<E> curr = this.head; //loop until last node is reached or data is found while (curr.next != null || curr == this.tail) { //data is found if (curr.data.equals(data)) { // remove the last remaining node if (size == 1) { this.head = null; this.tail = null; } // remove the first node else if (curr.equals(this.head)) { this.head = this.head.next; } // remove the last node else if (curr.equals(this.tail)) { this.tail = prev; this.tail.next = null; } // remove the node in the middle. else { prev.next = curr.next; } size--; hasRemoved = true; break; } //move to next node prev = curr; curr = prev.next; } return hasRemoved; } private boolean isEmpty() { return size == 0; } public Node<E> getHead() { return head; } public Node<E> getTail() { return tail; } public long getSize() { return size; } @Override public String toString() { return "\nhead --> " + head + "\ntail --> " + tail + "\nsize --> " + size; } } |
Removing has 4…
