How LinkedList Class Works Internally in Java

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

• ArrayList
• LinkedList

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

• To read more about how ArrayList works internally in Java refer this post- How ArrayList works internally in Java

In this post I'll talk about LinkedList internal implementation in Java Collections framework.

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

Table of contents

1. Internal implementation of LinkedList class in Java
2. Graphical representation of Java LinkedList with nodes
3. Java LinkedList internal implementation - linkFirst() method
4. Java LinkedList internal implementation - linkLast() method
5. Java LinkedList internal implementation - add(int index, E element) method

Internal implementation of LinkedList class in Java

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

In the implementation of the LinkedList class in Java 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;
  }
}

Graphical representation of Java LinkedList 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)

Java LinkedList internal implementation - linkFirst() method

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

/**
 * 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.

Java LinkedList internal implementation - 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;).

Java LinkedList internal implementation - add(int index, E element) method

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++;
}

And node(index) parameter with in the linkBefore() method is call to the following method to get the existing Node at the given index-

/**
* Returns the (non-null) Node at the specified element index.
*/
Node<E> node(int index) {
 // assert isElementIndex(index);

  if (index < (size >> 1)) {
    Node<E> x = first;
    for (int i = 0; i < index; i++)
      x = x.next;
    return x;
  } else {
    Node<E> x = last;
    for (int i = size - 1; i > index; i--)
      x = x.prev;
    return x;
  }
}

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 LinkedList Class Works Internally in Java. If you have any doubt or any suggestions to make please drop a comment. Thanks!

>>>Return to Java Advanced Tutorial Page | Return to Java Collections Framework Tutorial Page>>>

---

Related Topics

1. How HashMap Works Internally in Java
2. How HashSet Works Internally in Java
3. Difference Between ArrayList And LinkedList in Java
4. ListIterator in Java
5. Java Collections Interview Questions And Answers

You may also like-

1. How to Convert Array to ArrayList in Java
2. Difference between HashMap and ConcurrentHashMap in Java
3. static import in Java
4. finally Block in Java Exception Handling
5. Interface Static Methods in Java
6. Method reference in Java 8
7. Java Program to Find First Non-Repeated Character in a Given String
8. Synchronization in Java - Synchronized Method And Block