Read Also: Difference between ArrayList and LinkedList in Java
LinkedList Internal Implementation in Java
In one-liner, Doubly-linked list implementation of the List and Deque interfaces. But how does doubly-linked list is implemented we will find out below. You can find the LinkedList API here.
What is Node?
The main component of the LinkedList is a Node. In java, internally, java.util.LinkedList class contains a private static class Node.
Structure of Node Class
The node contains the following properties:
1. item: to store the value
2. next: reference to the next node. In other words, it stores the address of the next node.
3. previous: reference to the previous node. In other words, it stores the address of the previous 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 add() method works internally in LinkedList?
As we know that elements in LinkedList are added in a sequential manner. There are many overloaded methods of add() method present in the LinkedList class. But we are focusing on one method add(int index, E element). To understand it, first, we need to learn about the linkLast() method that is also present in LinkedList class.
LinkedList Internal Implementation - first and last Node
There are two different variables first and last in the LinkedList class to hold the reference of the first and last node as shown below.
/** * Pointer to first node. */ transient Node<E> first; /** * Pointer to last node. */ transient Node<E> last;
LinkedList Internal Implementation - linkLast() method
linkLast() method is used to add the element at the last position of the list. The last node before the insertion of the new node is now at the second last position after the addition of the new node. As a result, the newly inserted node previous will contain the reference to the second last node whereas the second last node next will contain the reference to the newly inserted last node.
/** * 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++; }
From the above linkLast() code we can conclude that if we insert the very first element in the LinkedList then both the first and last point to the new Node.
If LinkedList already contains the elements then a new element is inserted at the end of the list. l will hold the reference to the node that was in the last position before the insertion of the new element.
l and element e is passed as the parameters in the constructor of the Node class. If you see the constructor of the Node class then there you will observe this.item = e; and this.prev = l; that's how the newly created node previous contains the reference to the second last node.
(last = newNode;) indicates last will now hold the reference to the newly created Node.
(l.next = newNode;) The node that was the last node before inserting the new element at the end, is now at the second last place. Its next will contain the reference to the newly created node i.e last node.
The LinkedList code used in this post is taken from "JDK 11"
add(int index, E element) method
/** * Inserts the specified element at the specified position in this list. * Shifts the element currently at that position (if any) and any * subsequent elements to the right (adds one to their indices). */ public void add(int index, E element) { checkPositionIndex(index); if (index == size) linkLast(element); else linkBefore(element, node(index)); }
The add(int index, E element) is used to insert the specified element at the specified position in the list.
checkPositionIndex(index) is used to tell if the argument is the index of a valid position for an add operation.
If (index == size) then linkLast() method is called.
One of the parameter is node(index) in the method call to linkBefore(element, node(index));.
node(index) returns the Node(non-null) at the specified element index.
/** * Returns the (non-null) Node at the specified element index. */ Node<E> node(int index) { // some code }
linkBefore() method code is similar to the linkLast() method. The only difference between them is that we are passing an extra node in the method parameter. Also, we have to adjust the next and previous references accordingly. The code for the linkBefore() method is given below:
/** * Inserts element e before non-null Node succ. */ 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++; }
How remove() method works internally in Java?
Similar to the add() method in LinkedList there exists unlinkFirst() and unlinkLast() methods for remove() method. There are many overloaded methods of remove() present in the LinkedList class. But we will look into the simple remove() method as given below:
/** * Retrieves and removes the head (first element) of this list. * @return the head of this list */ public E remove() { return removeFirst(); }
In the above code, removeFirst() is calling unlinkFirst() method internally. It will assign the null values to the first node next reference and element item. Then the second element becomes the new head. Its previous reference becomes null.
How get() method works internally in Java?
Similar to the add() method in LinkedList there exists getFirst() and getLast() methods. The get() method code is as follow:
/** * Returns the element at the specified position in this list. */ public E get(int index) { checkElementIndex(index); return node(index).item; }
Unlike add() or remove() methods there are no overloaded methods for get() in LinkedList class. We have already discussed the node(index) method above. It will return the (non-null) node at the specified element index. item attribute of the Node will be returned by the get(index) method.
That's all for today, please mention in comments in case you have any questions related to internal implementation of LinkedList in Java.