LinkedList Internal Implementation in Java

June 21, 2022

LinkedList Internal Implementation in Java

In the post ArrayList Internal Implementation in Java we have already seen the internal implementation details of one of the implementation of the List interface – ArrayList. In this post we’ll see LinkedList internal implementation in Java which is another implementation of the List interface

Questions that may come up for How LinkedList works internally in Java are as follows-

How does LinkedList class store its element.
Is LinkedList class in Java implemented as a singly linked list or a doubly linked list.
What happens when element is added to the LinkedList. Since it is a LinkedList so what is the implementation for adding element at the first position or at the last.
How does remove() method works in LinkedList.
How does get() method work in LinkedList.

In this post let’s try to answer these questions by looking into the internal implementation of LinkedList in Java.

How does LinkedList class store its element

Internally LinkedList class in Java uses objects of type Node to store the added elements. Node is implemented as a static class with in the LinkedList class. Since LinkedList class is implemented as a doubly linked list so each node stores reference to the next as well as previous nodes along with the added element.

Node class code in JDK 10

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

Is it a doubly linked list

As already shown Java LinkedList class is implemented as a doubly linked list and each node stores reference to the next as well as previous nodes.

How add() method works in a LinkedList

Since it is a linked list so apart from regular add() method to add sequentially there are addFirst() and addLast() methods also in Java LinkedList class.

There are also separate variables for holding the reference of the first and last nodes of the linked list.

/**
* Pointer to first node.
*/
transient Node<E> first;

/**
* Pointer to last node.
*/
transient Node<E> last;

If you call the regular add() method or addLast() method, internally linkLast() method is called. In this method a new node is created to store the added element and the variable last starts referring to this node (as this new node becomes the last node). There is also a check to see if it is the very first insertion in that case this node is the first node too.

linkLast() method implementation in the LinkedList class

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

If you call addFirst() method internally linkFirst() method is called. In this method a new node is created to store the added element and the variable first starts referring to this node (as this new node becomes the first node). There is also a check to see if it is the very first insertion in that case this node is the last node too. If it is not the first node then the previous "first" node now comes at the second position so its prev reference has to refer to the new node.

LinkFirst() method implementation 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++;
}

There is also an add() method to add element at a specific index. If that method is called then the already existing element at the passed index has to be shifted right.

How remove() method works in Java LinkedList class

Just like add() method for removing an element from the LinkedList apart from regular remove() method (where index or the element is passed) there are also removeFirst() and removeLast() methods.

When remove() method is called then the reference of the nodes at the left and right of the removed nodes have to be changed so that next of the node at left starts referring to the node at the right and the prev of the node at right starts referring to the node at the left of the node to be removed.

Following image will help you understand what actually is needed to be done. Here middle node has to be removed.

How get() method works in Java LinkedList class

In the case of get() method again there are getFirst() and getLast() methods too. In case of get() method it has to get the node for the passed index and return the node.item.

public E get(int index) {
  checkElementIndex(index);
  return node(index).item;
}

In case of getFirst() and getLast() reference is also stored in the first and last variables so just need to return the value first.item or last.item.

That's all for the topic LinkedList Internal Implementation in Java. If something is missing or you have something to share about the topic please write a comment.

You may also like

KnpCode

June 21, 2022