Linkedlist – Internal implementation

Internally linkedlist has a private static class called Node, which is used to add the elements, since linkedlist class is implemented as a doubly linkedlist so each node stores the reference of previous node as well along with the next node.

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

How do you add an element in a Linkedlist ?

Answer : using add() method

Internally : What happens when you call add() method ?

In a linked list when you call its add() method to add an element to the list, it internally calls the linklast() method.

public boolean add(E e) {
  linkLast(e);
  return true;
}

Also there are two transient variables called the first and last which are there to hold the reference of first and last nodes of the linkedlist.

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

In this method a new node is created to store the new element and the variable last starts referring to this node. Also there is a condition check if this was the very first node which is being added, if that is the case then the variable first also start pointing to this new node along with the variable last.

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

Other than add() method there are other methods as well to add elements in the linkedlist.

Another one is the addFirst() method

Internally : What happens when you call addFirst() method ?

This method internally calls linkFirst() method.

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.

logical ! isn’t it ?  see the code below.

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

Want to add element at particular index ?

Answer : Use add() with index as argument

Internally : What happens when you call add(int index, E element) method ?/p>

It checks for the index position, then checks if the index if last , in that case it calls linkLast() method otherwise it calls linkBefore() method which shifts already existing element to the right.

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

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

How do you remove element from a LinkedList ?

---

Answer : Using remove() method

Internally : What happens when you call remove() method ?

There are few types :

• remove() : without any index then it removes the first occurrence of the specified element from this list as this method internally calls removeFirst() method which internally calls unlinkFirst(Node(E) f) method where it nullifies item value and its next reference.
• remove(int index) : Removes the element at the specified position in this list. Shifts any subsequent elements to the left (subtracts one from their indices). Returns the element that was removed from the list.
• removeFirst() : is used to remove and return the first element of the list.
• removeLast() : is used to remove and return the last element of the list.

public E remove(int index) {
   checkElementIndex(index);
   return unlink(node(index));
}

    
**
* Unlinks non-null node x.
*/
E unlink(Node<E> x) {
   // assert x != null;
   final E element = x.item;
   final Node<E> next = x.next;
   final Node<E> prev = x.prev;

   if (prev == null) {
       first = next;
   } else {
       prev.next = next;
       x.prev = null;
   }

   if (next == null) {
       last = prev;
   } else {
       next.prev = prev;
       x.next = null;
   }

   x.item = null;
   size--;
   modCount++;
   return element;
}

How do you fetch/get element from a LinkedList ?

---

Answer : Using get() method

Internally : What happens when you call get() method ?

An index is to be passed to get() method to fetch an element from the linkedlist.

public E get(int index) {
  //checkElementIndex() is of type void, it checks for IndexOutOfBoundsException, 
  //based on condition (index>=0 && index<size)
  checkElementIndex(index); 
  return node(index).item;
}

getFirst() and getLast() : fetches the respective first and last elements.

Summary

I hope this article helped you in understanding the internal implementation of the linked list. You can try creating your own.

---