Wednesday, 26 August 2015

How LinkedList class works internally in Java Collections

In Java Collections framework there are two general purpose implementations of the list interface -

Out of these two Arraylist internally uses an array of Object which can be dynamically re-sized.

In this post I'll talk about how LinkedList implementation, provided by Java Collections framework, works internally

Note - Code of LinkedList class used here for reference is from Java 8.

LinkedList class in Java

LinkedList class in Java implements List and Deque interfaces and LinkedList implements it using doubly linkedlist.

Within the LinkedList class there is a private class Node which provides the structure for a node in a doubly linked list. It has item variable for holding the value and two reference to Node class itself for connecting to next and previous nodes.

The Node class from Linked List implementation

private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;
    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

A graphical representation of Linked list with nodes

Here is a graphical representation of a linked list to help you better visualize how actually a node will look like and how it connects with other nodes through next and prev references.
Since reference is stored for both next and previous nodes that is why it is a doubly linked list implementation.

Though there are many methods with in the LinkedList class but here I'll try to explain the internal working of the LinkedList, how references are created and shuffled using these 3 methods -

  • private void linkFirst(E e)
  • void linkLast(E e)
  • public void add(int index, E element)

linkFirst() method

linkFirst() method is used to add an element at the beginning of the list and it is implemented as follows

/**
 * Links e as first element.
 */
private void linkFirst(E e) {
    final Node<E> f = first;
    final Node<E> newNode = new Node<>(null, e, f);
    first = newNode;
    if (f == null)
        last = newNode;
    else
        f.prev = newNode;
    size++;
    modCount++;
}

Here one more important thing to mention is first and last Node class references which always refer to the first and last element of the linked list.

/**
 * Pointer to first node.
 * Invariant: (first == null && last == null) ||
 *            (first.prev == null && first.item != null)
 */
transient Node<E> first;
/**
 * Pointer to last node.
 * Invariant: (first == null && last == null) ||
 *            (last.next == null && last.item != null)
 */
transient Node<E> last;

With this info it is easy to see that in the linkFirst method, when the very first element is inserted into the list first and last both refer to this new node.

In case linked list already contains elements and a new element is inserted at the beginning of the list. Then f will hold the reference to the node which was the first element before this insertion. first will be assigned the reference to the newly created node (first = newNode;). The element which was the first element before this insertion is at second position now so its prev element should store reference of the first node, that's what is happening here f.prev = newNode;

And in the call to the constructor of the node class f is sent as a parameter. If you see in the Node class constructor there is a line this.next = next; that's how the newly created node is storing the reference to the second node.

linkLast() method

linkLast() method is used to insert element as the last element of the list. In that case the node which is currently the last node of the linked list will become the second last node. So the newly created node's prev should store the reference to this second last node and the next of the second last node should store the reference to the node which is the last node now.

/**
 * Links e as last element.
 */
void linkLast(E e) {
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    size++;
    modCount++;
}

Here it is first checking if it is the very first element which is inserted in that case both first and last references point to it. If elements are already there in the linked list then the node which is currently the last node of the linked list will become the second last node now.

See the call to the constructor of the Node class (this.prev = prev;). So the newly created node's prev should store the reference to this second last node and the next of the second last node should store the reference to the node which is the last node now (l.next = newNode;).

add(int index, E element) is used to Insert the specified element at the specified position in this list.

public void add(int index, E element) {
    checkPositionIndex(index);

    if (index == size)
        linkLast(element);
    else
        linkBefore(element, node(index));
}

Here it calls linkBefore method

void linkBefore(E e, Node<E> succ) {
    // assert succ != null;
    final Node<E> pred = succ.prev;
    final Node<E> newNode = new Node<>(pred, e, succ);
    succ.prev = newNode;
    if (pred == null)
        first = newNode;
    else
        pred.next = newNode;
    size++;
    modCount++;
}

I am leaving it to you readers to figure out how linkBefore() method is working. It should be easy based on the explanation already provided for linkFirst() and linkLast() method.

That's all for this topic How Linked List class works internally in Java Collections. If you have any doubt or any suggestions to make please drop a comment. Thanks!


Related Topics

  1. How ArrayList works internally in Java
  2. How HashMap internally works in Java
  3. How to join lists in Java
  4. Difference between ArrayList and LinkedList in Java
  5. List iterator in Java
  6. Java Collections interview questions

You may also like -

2 comments:

  1. awesome explanation, after learning your description for linkFirst() and linkLast() method, I could easily understand linkBefore() method.

    ReplyDelete