In Java, LinkedList is a generic class that extends the AbstractSequentialList and implements List, Queue, and Deque interfaces. It is a part of the Java Collection API Library. It basically is an implementation of a type of linked list data structure that facilitates the storage of elements. The contents of this storage can grow and shrink at run time as per the requirement. Quite visibly, it is not very different from the other List classes, such as ArrayList. But, the point of difference is in how the list is maintained at the core. The article is an attempt to delineate the concept behind the data structure involved and its implementation in Java in a terse manner.
Defining Linked List
Figure 1: A one-dimensional array
A one-dimensional array implies that the elements are stored in a consecutive memory location, organized as a linear list where the size must be defined at the outset of its creation. An array of size, say N, is accessed by its index position through 0 to N-1. Therefore, the first element is represented Array[0], while the last element is Array[N-1].
Now, imagine each array location as a separate “node.” The nodes must be linked in a manner that the next node is accessible from its current node while traversing.
Note that, unlike arrays, the nodes here are not in consecutive memory locations. As a result, there is no way to traverse them consecutively by their indices. Each node must have one or more exclusive parameter that links to the next/previous node.
According to these links arranged, the linked list data structure can be of following types.
Figure 2: The linked list data structure
Traversal: Linear
A singly linked list arranges nodes in a linear fashion where each node is connected to its immediate next node. The last node links to null, which means end of list. Only one-way traversal is possible in this type of list.
Figure 3: A linear transversal
Traversal: Clockwise or Anti-clockwise
The list is made circular by making the last node point to the first node. The disadvantage of a singly linked list is somewhat overcome here because, once the last node is encountered, the link points again to the first node. The problem of getting lost after reaching the last node in the singly list has now a meaningful pointer whereby it can traverse again from the beginning.
Figure 4: A two-way, or doubly linked list, transversal
Traversal: Both Ways/To and Fro
A doubly linked list is yet better because each node links to its immediate previous node as well as to the next node. This makes to and fro traversal from any node except the first and last node possible.
Figure 5: A two-way, circular, or doubly circular transversal
Traversal: Clockwise and Anti-clockwise
Doubly circular is a modification of a doubly linked list by making the last node again link to the first node and, in a similar manner, the first node again linked to the last node. This makes both clockwise and anti-clockwise traversal possible and is the most flexible of all linked list types.
As should be obvious, the implementation becomes increasingly complex from a singly to circular-doubly linked list. So, let’s implement the simplest one (singly linked list) and the most complex one (circular-doubly linked list) in an old-fashioned way without using the LinkedList class from the Java API library. Though it’s a simplistic implementation, this basic idea can be improved further with numerous clever assumptions.
A Quick Example of a Singly Linked List
Here, we create a generic node type class, called SinglyNode. This class contains an information part, called info, and a link part, called next. The information part can be any type of object element whereas the link part must be of its own type. The link part either keeps the connection with another node of the same type or null, if it has nothing to link to.
The use of the Comparable interface is the simplistic example. The following code is superfluous but can effectively used with further assumption and improvement.
package org.mano.llist.example;
public class SinglyNode<NodeType> implements
Comparable<NodeType> {
private NodeType info;
private SinglyNode<NodeType> next;
public SinglyNode(NodeType info) {
super();
this.info = info;
this.next = null;
}
public NodeType getInfo() {
return info;
}
public void setInfo(NodeType info) {
this.info = info;
}
public SinglyNode<NodeType> getNext() {
return next;
}
public void setNext(SinglyNode<NodeType> next) {
this.next = next;
}
@Override
public int compareTo(NodeType obj) {
if (info == obj)
return 1;
else
return 0;
}
}
The SingleLinkedList class contains the logic for adding and removing elements to the list. The SinglyNode type root always holds the beginning of the chain so that we can begin from there. Care should be taken to never lose the beginning of the list. The next code simplifies adding and removing elements from the list in any location by assuming their indices are like an array, though actually there no such concept of indices in the linked list data structure. It is used to denote the location beginning, end, or middle of the linked list.
package org.mano.llist.example;
public class SinglyLinkedList<NodeType> {
private SinglyNode<NodeType> root;
private int count;
public SinglyLinkedList() {
root = null;
count = 0;
}
/*
if position is <=0 then inserts at first,
position>=COUNT inserts at last, else
inserts at the right position location
*/
public int getCount() {
return count;
}
public void addAt(SinglyNode<NodeType> node,
int position) {
if (root == null) {
root = node;
// inserts at the beginning of the list
} else if (position <= 0) {
SinglyNode<NodeType> tmpref = root;
root = node;
root.setNext(tmpref);
} else { // inserts at the end or right position
position = position > count ? count : position;
SinglyNode<NodeType> tmpref = root;
for (int i = 0; i < position - 1; i++) {
tmpref = tmpref.getNext();
}
node.setNext(tmpref.getNext());
tmpref.setNext(node);
}
count++;
}
public void showAll() {
SinglyNode<NodeType> tmpref = root;
while (tmpref != null) {
System.out.print("->" + tmpref.getInfo());
tmpref = tmpref.getNext();
}
System.out.println();
}
public void removeAt(int position) {
position = position > count ? count : position;
if (root == null)
return;
else if (position <= 1) {
root = root.getNext();
} else {
SinglyNode<NodeType> tmpref = root;
for (int i = 0; i < position - 1; i++) {
tmpref = tmpref.getNext();
}
tmpref.setNext(tmpref.getNext().getNext());
}
count--;
}
public static void main(String[] args) {
SinglyLinkedList<Integer> llist =
new SinglyLinkedList<>();
llist.addAt(new SinglyNode<Integer>(11), 0);
llist.addAt(new SinglyNode<Integer>(22), -3321);
llist.addAt(new SinglyNode<Integer>(33), 2);
llist.addAt(new SinglyNode<Integer>(44), 3);
llist.addAt(new SinglyNode<Integer>(77), 88);
llist.addAt(new SinglyNode<Integer>(99), 3);
System.out.println("Count=" + llist.getCount());
llist.showAll();
llist.removeAt(-89);
llist.showAll();
llist.removeAt(1);
llist.showAll();
llist.removeAt(3);
llist.showAll();
}
}
A Quick Example of a Circular Doubly Linked List
This is a circular-doubly implementation. The only difference in the DoublyNode with respect to SinglyNode is the two link pointers, prev and next. The prev links to the node before it and next to the subsequent node. Because it is implemented as circular, the next location of the last node points again to the first node and the prev location of the first node points to the last node.
package org.mano.llist.example;
public class DoublyNode<NodeType>
implements Comparable<NodeType> {
private DoublyNode<NodeType> prev;
private NodeType info;
private DoublyNode<NodeType> next;
public DoublyNode(NodeType info) {
super();
this.info = info;
this.next = null;
this.prev = null;
}
public DoublyNode<NodeType> getPrev() {
return prev;
}
public void setPrev(DoublyNode<NodeType> prev) {
this.prev = prev;
}
public NodeType getInfo() {
return info;
}
public void setInfo(NodeType info) {
this.info = info;
}
public DoublyNode<NodeType> getNext() {
return next;
}
public void setNext(DoublyNode<NodeType> next) {
this.next = next;
}
@Override
public int compareTo(NodeType o) {
return 0;
}
}
Observe in the code that the logic for adding and removing elements by their indices is not very different from its SinglyLinkedList implementation, though apparently it may seem complex.
package org.mano.llist.example;
public class DoublyCircularLinkedList<NodeType> {
private DoublyNode<NodeType> root;
private int count;
public DoublyCircularLinkedList() {
root = null;
count = 0;
}
public int getCount() {
return count;
}
public void addAt(DoublyNode<NodeType> node,
int position) {
if (root == null) {
node.setNext(node);
node.setPrev(node);
root = node;
// inserts at the beginning of the list
} else if (position <= 0) {
DoublyNode<NodeType> tmpref = root;
while (tmpref.getNext() != root)
tmpref = tmpref.getNext();
tmpref.setNext(node);
node.setNext(root);
node.setPrev(tmpref);
root.setPrev(node);
root = node;
// adds at any position except in the beginning
} else {
position = position > count ? count : position;
DoublyNode<NodeType> tmpref = root;
for (int i = 0; i < position - 1; i++) {
tmpref = tmpref.getNext();
}
node.setNext(tmpref.getNext());
node.setPrev(tmpref);
tmpref.getNext().setPrev(node);
tmpref.setNext(node);
}
count++;
}
public void traverseClockwise() {
if (root == null)
return;
DoublyNode<NodeType> tmpref = root;
for (int i = 0; i < count; i++) {
System.out.print("->" + tmpref.getInfo());
tmpref = tmpref.getNext();
}
System.out.println();
}
public void traverseAnticlockwise() {
if (root == null)
return;
DoublyNode<NodeType> tmpref = root.getPrev();
for (int i = 0; i < count; i++) {
System.out.print("->" + tmpref.getInfo());
tmpref = tmpref.getPrev();
}
System.out.println();
}
public void removeAt(int position) {
position = position > count ? count : position;
if (root == null)
return;
else if (position <= 1) {
root.getPrev().setNext(root.getNext());
root.getNext().setPrev(root.getPrev());
root = root.getNext();
} else {
DoublyNode<NodeType> tmpref = root;
for (int i = 0; i < position - 1; i++) {
tmpref = tmpref.getNext();
}
tmpref.setNext(tmpref.getNext().getNext());
tmpref.getNext().setPrev(tmpref);
}
count--;
}
public static void main(String[] args) {
DoublyCircularLinkedList<Integer>
llist = new DoublyCircularLinkedList<>();
llist.addAt(new DoublyNode<Integer>(11), 0);
llist.addAt(new DoublyNode<Integer>(22), -3321);
llist.addAt(new DoublyNode<Integer>(33), 2);
llist.addAt(new DoublyNode<Integer>(44), 3);
llist.addAt(new DoublyNode<Integer>(77), 88);
llist.addAt(new DoublyNode<Integer>(99), 3);
llist.addAt(new DoublyNode<Integer>(66), 2);
llist.addAt(new DoublyNode<Integer>(00), 0);
System.out.println("Count=" + llist.getCount());
llist.traverseClockwise();
llist.traverseAnticlockwise();
System.out.println("------------------------------");
llist.removeAt(-89);
llist.traverseClockwise();
llist.removeAt(1);
llist.traverseClockwise();
llist.removeAt(3);
llist.traverseClockwise();
llist.removeAt(754);
llist.traverseClockwise();
}
}
The Java LinkedList API
The LinkedList class in the Java Collection API library is a doubly linked list implementation of the List and Deque interfaces that form a generic data structure. The LinkedList object allows null to be one of the elements of the list along with its support of all optional list operations. The class provides a method that can be used to traverse the list from beginning to the end by specifying their indices, similar to array access operations. The best part of using this class that it makes using the linked data structure easy without having to worry about the intricacies involved in implementing one from scratch. However, the LinkedList class is nor synchronized. This means, multiple thread access to it must be synchronized explicitly. The simplest way to achieve this is as follows.
List<String> llist=Collections.synchronizedList (new LinkedList<>());
There are many convenient methods in LinkedList such as adding or removing elements to the linked list with the help of a index number, transforming the link list to an array implementation, and so forth. A quick example is given below:
A Quick Example
package org.mano.llist.example;
import java.util.LinkedList;
public class LinkedListDemo {
public static void main(String[] args) {
LinkedList<String> llist=new LinkedList<>();
llist.add("purple");
llist.add("red");
llist.add("green");
llist.add("blue");
llist.add("green");
llist.add("yellow");
System.out.println("Size:"+llist.size());
System.out.println("Contents of the link list "+llist);
llist.addFirst("Black");
llist.addLast("White");
System.out.println("Size:"+llist.size());
System.out.println("Contents of the link list "+llist);
llist.removeLast();
llist.remove(2);
System.out.println("Size:"+llist.size());
System.out.println("Contents of the link list "+llist);
}
}
Conclusion
Apart from its internal representation, the working of a linked list is not much different from the other list classes. The power of the linked list lies is its core representation. Though inserting elements at the beginning and end of the list offers a significant performance improvement, the disadvantage of slow insertion and deletion at the middle of the list outweighs them. It is particularly advantageous to use it in a situation where there is a voluminous addition and deletion of elements at the beginning and at the end of the list. In essence, it is no better than ArrayList and should be used only in specific circumstances; otherwise, ArrayList is better.
