Nitin Jaiswal Nitin Jaiswal - 5 months ago 9
Java Question

LinkedList - Trying to understand implementation

I am learning to solve complex algorithm. For that I came across the implementation for LinkedList. I am trying to understand the above solution. In appendToTail I don't understand while loop and the line after the while loop. In deleteNode I cannot see where the node is deleted.

class Node {
Node next = null;
int data;

public Node(int d) {
data = d;
}

void appendToTail(int d) {
Node end = new Node(d);
Node n = this;
while (n.next != null) {
n = n.next;
}
n.next = end;
}

Node deleteNode(Node head, int d) {
Node n = head;
if (n.data == d) {
return head.next; /* moved head */
}
while (n.next != null) {
if (n.next.data == d) {
n.next = n.next.next;
return head; /* head didn’t change */
}
n = n.next;
}
}
}

Answer

LinkedLists have several implementations. Some keep only a pointer to the head of the list. Others keep track of the tail to accomplish appending to tail in O(1)

This implementation maintains no tail pointer, so you have to iterate through the list starting from the head

1 --> 2 --> null
^
head

So this refers to the head of the list. The while loop moves through the list until it reaches the end or (until the next node pointer in n equals null)

In the above example the loop would terminate here

n  n.next
2   null

The loop would then exit and set:

n.next = end

The new list looks like this:

1 --> 2 --> 3
^
head