Linked List | Why we learn this data structure
A linked list is a dynamic linear data structure where each element is a separate object connected via pointers. Learn how to implement a linked list in Java — adding, removing, detecting cycles, and more.
Why use Linked List
As I briefly mentioned in an earlier post on data structures, arrays have some disadvantages such as, not being flexible in terms of extending or reducing its size (because it’s a static data structure) which linked lists address.
What is a Linked List
An linked list is a dynamic linear data structure, where each data element is a separate object with its own memory allocation connected to the other objects via pointers. These elements (called nodes) comprise of the data and the reference pointing to the next node. The first node is called the head and the last node has a null reference. The number of nodes comprising the list is not fixed and can be changed on demand.
Linked lists come with their own tradeoffs which one should consider. For example, we can’t access a specific element within a linked list without going through all of the nodes. Also, linked lists are bigger in size compared to arrays as we now store next node’s reference pointer (4 bytes extra on 32-bit CPU) with each element.
Linked List applications
Linked lists are very important in software that deals with an unspecified number of data. A checkout basket of an online store for example. The basket is a list of items a user wants to buy. As we don’t know how many items the user will be buying, we need a dynamic data structure, such as linked lists, for listing all possible items.
Types of Linked Lists
There are two types of linked lists, the singly linked list described above and, the doubly linked list. In the doubly linked list, the nodes in addition to the singly linked list properties hold a reference of their previous node as well.
Linked List Internals
In order to better understand how linked lists work, we need to take a look at its internals and basic functionalities. So roll your sleeves up and lets jump into some code.
The Node class
Firstly, let us have a look at a general implementation of a node class in a singly linked list, shown below, that we’ll be using for this example.
public class LinkedList<T> {
// Reference to the head node
Node head;
// node class
class Node {
// Node data
T data;
// Next node reference
Node next;
// Node constructor
public Node(T data, Node next){
this.data = data;
this.next = next;
}
}
}
Iterating a linked list
Iterating a linked list is done by using the next node reference pointer in each node. The next node reference takes us through the linked list node by node, as it is depicted in the diagram below.
Following is the code to iterate the list and print all nodes.
public class LinkedList<T> {
// Reference to the head node
Node head;
public void printAll(){
// get reference to the head node
Node next = head;
while(next != null){
// print node's data
System.out.println(next.data);
// get reference to the next node
next = next.next;
}
}
...
Adding a new node
There are three basic methods on how we can add new nodes to the list. Adding a new node at the top of the linked list replacing the head. Adding a new node to the tail and also, adding a new node in a specific position relative to another node in the list.
Add to the head
We can replace the head of a linked list by creating a new node and assigning the current head as its next node and then, make that new node the head of the list.
public class LinkedList<T> {
// Reference to the head node
Node head;
public void addToHead(T data){
// create the new Node and add head as its next
Node newNode = new Node(data, head);
// replace head with the new node
head = newNode;
}
...
Add to the tail
To add a new node at the end/tail of the linked list we need to iterate the list and find the last node. Then we assign the last node’s next reference to the new node we want to add.
public class LinkedList<T> {
// Reference to the head node
Node head;
public void addToTail(T data){
// create new node
Node newNode = new Node(data, null);
// Check if head is null and set new node as head
if(head == null){
head = newNode;
return;
}
// get head reference
Node current = head;
// iterate until the last node
while(current.next != null){
current = current.next;
}
// add new node to the tail
current.next = newNode;
}
...
Add after another node
We can also add a new node in a specific position in the linked list relatively to another node. We just need to iterate the list find the node we are looking for and add the new node after that. Or add it to the tail if we can’t find it.
Additionally, we can modify the below code to add a node before another node, etc.
public class LinkedList<T> {
// Reference to the head node
Node head;
public void addAfter(T data, T target){
// create new node
Node newNode = new Node(data, null);
// check if list empty
if(head == null){
// set new node to tail
head = newNode;
return;
}
// check head value
if(head.data == target){
// helper method below to add newNode
head = addAfter(head, newNode);
return;
}
// get head reference
Node current = head;
// iterate nodes
while(current.next != null){
// check node value
if(current.next.data == target){
// helper method below to add newNode
current.next = addAfter(current.next, newNode);
return;
}
// go to next node
current = current.next;
}
// Add to tail
current.next = newNode;
}
// helper method to add a node after another node
private Node addAfter(Node head, Node newNode){
// set newNodes next ref. to head's next ref
newNode.next = head.next;
// set head's next to be the newNode
head.next = newNode;
// return head
return head;
}
...
Remove a node
To remove a specific node from the list, we need to iterate the nodes and find it. We keep a reference to its previous node. Then, we point the previous’s next reference pointer, to the next node of the one we want to remove.
public class LinkedList<T> {
// Reference to the head node
Node head;
public void removeNode(T data){
// check if list empty
if(head == null) return;
// check head's data if equal
// and assign next node as head
if(head.data == data){
head = head.next;
return;
}
// get head reference
Node current = head;
// iterate list
while(current.next != null){
// check next node's data
// skip next node
if(current.next.data == data){
current.next = current.next.next;
return;
}
// go to next node
current = current.next;
}
}
...
Extra
After understanding the basics of linked lists, let’s leave our imagination run free and to play a bit more with this data structure.
Let’s have a look at a cool method for checking and removing duplicates in a linked list.
public class LinkedList<T> {
// Reference to the head node
Node head;
public void removeDuplicates(){
// check if list empty
if(head == null) return;
// chech if single node
if(head.next == null) return;
// get head reference
Node tmp = head;
// iterate list
while(tmp.next != null){
if(tmp.data == tmp.next.data){
// if duplicate remove and check with next
tmp.next = tmp.next.next;
} else {
// or go to next node
tmp = tmp.next;
}
}
}
...
Another cool algorithm is Floyd’s tortoise. This algorithm can check if a singly linked list has a closed cycle. This can be achieved by iterating a list with two pointers that will move in different speed. In this way, if there is a cycle the two pointers will meet at some point in the future.
How easy it is to implement? Let’s see.
public class LinkedList<T> {
// Reference to the head node
Node head;
public boolean hasCycle(){
// check if list empty
if(head == null) return false;
// create slow and fast nodes
Node slow, fast;
slow = fast = head;
// iterate list
while(true){
// get next node
// slow pointer iterates the list node by node
slow = slow.next;
// check if end of the list
if(fast.next == null) return false;
// get reference of a next node always skipping one
fast = fast.next.next;
// check if end of the list
if(fast == null) return false;
// if there is a cycle then the fast and slow
// pointers will meet at some point.
if(fast.equals(slow)) return true;
}
}
...
Performance
Now for the cool part let’s see some stats of linked lists about, operation performance with Big-O notation complexities. Linked list Big-O time complexity is O(n) for Access and Search, whereas, for Insertion and Deletion operations is O(1). The space complexity of a linked list is O(n). Again, if you are not familiar with the Big-O notation, I will be writing a post about it as well, so stay tuned.
Linked lists are a powerful data structure that we can use for many important reasons as we discussed in this post, and we also saw how to use them. I hope you now learned what and why linked lists are so important in computer science. I now encourage you to use linked lists in your own projects and where appropriate in order to become more familiar with them.