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 LinkedList internal implementation in Java Collections framework.
Note- Code of LinkedList class used here for reference is from Java 10.
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!
Related Topics
-
How HashMap Works Internally in Java
-
How HashSet Works Internally in Java
-
Difference Between ArrayList And LinkedList in Java
-
ListIterator in Java
-
Java Collections Interview Questions And Answers
You may also like-
-
How to Convert Array to ArrayList in Java
-
Difference between HashMap and ConcurrentHashMap in Java
-
static import in Java
-
finally Block in Java Exception Handling
-
Interface Static Methods in Java
-
Method reference in Java 8
-
Java Program to Find First Non-Repeated Character in a Given String
-
Synchronization in Java - Synchronized Method And Block
