Linked list data structure

Oct 19, 2024

—

1. Introduction

A Linked List is a linear data structure where elements (nodes) are stored in a sequence, and each node holds two components: the data and a reference to the next node. Unlike arrays, linked lists don’t need to be stored in contiguous memory locations, making insertions and deletions easier.

In this tutorial, we will explore linked lists using Java, covering different types, basic operations, and how to implement a linked list in Java.

A Linked List consists of nodes where each node contains two fields:

Data: Stores the element or value.
Next: Stores the reference (or pointer) to the next node in the list.

Since each node has to store the reference to the next node in addition to the data, linked list consumes more memory than an array.

The items are not stored next to each other in the memory, so there is no random indexing.

Linked list is used to implement more complex data structures such as stacks and queues.

2. Types of Linked Lists

Singly Linked List: Each node points to the next node, and the last node points to null, indicating the end.
Doubly Linked List: Each node has two references, one to the next node and one to the previous node.
Circular Linked List: The last node points back to the first node, forming a circle.

3. Basic Operations on Linked Lists

Insertion: Adding a new node at the beginning, end, or at a specific position.
Deletion: Removing a node from the beginning, end, or a specific position.
Traversal: Visiting each node to access its data.
Search: Finding if a specific element exists in the linked list.

Add node at the beginning

function insertBeginning(List list, Node newNode){
	newNode.next := list.firstNode
	list.firstNode := newNode
}

Add node at the end of linked list

node := list.firstNode
while node not null
	(do something with node data)
	node := node.next

newNode.next := node.next
node.next := newNode

Remove head node in the linked list

We can insert new items to the beginning of the data structure in O(1) constant running time.
We can insert new items to the end of the data structure in O(n) linear running time.
Adding item at the beginning of the list is comparatively fast in comparison the adding item to the end of the linked list.
Removing the first item of the linked list is easy because we just have to update the references – in O(1) constant running time complexity.
Manipulating arbitrary item has O(N) running time. If we have to do several of these operations then linked list is not the best possible option.

4. Running time complexity of operations

Find first item (head node)	O(1)
Search for arbitrary item	O(N)
Insert item to the beginning	O(1)
Insert item to the arbitrary position	O(N)
Removing first item	O(1)
Removing arbitrary item	O(N)

5. Pros of linked list

Dynamic Size: Linked lists are not fixed in size like arrays. They can grow or shrink dynamically by allocating or deallocating memory as needed, which is useful when the size of data is unknown or constantly changing.
Efficient Insertions and Deletions: Insertions and deletions, especially at the beginning or middle of the list, are efficient. Unlike arrays, where shifting elements is required for these operations, linked lists only need to adjust pointers.
No Wasted Memory: Memory is allocated as needed. There’s no need to pre-allocate memory (like with arrays), preventing memory wastage if the size requirement is smaller than expected.
Efficient Memory Usage for Large Data Sets: For applications with frequent insertions and deletions, linked lists are more memory-efficient than arrays. There’s no need to resize the list, reducing memory fragmentation.
Flexible Node Arrangement: The elements in a linked list are not stored contiguously in memory. This is an advantage in situations where memory is fragmented, and allocating large contiguous blocks would be inefficient.

6. Cons of Linked list

Memory Overhead: Each node in a linked list requires extra memory to store the pointer/reference to the next. This overhead can become significant, especially in applications where memory is a concern.
No Random Access: Linked lists do not support random access to elements. To access a particular element, you need to traverse the list from the head, making access times proportional to the position of the element (O(n) complexity), unlike arrays that allow direct access with O(1) time complexity.
Sequential Access Only: Elements must be accessed sequentially, meaning that finding an element or accessing elements by index is inefficient compared to arrays.
Poor Cache Locality: In linked lists, elements are not stored contiguously in memory, which leads to poor cache locality. This makes access times slower as compared to arrays, where elements are stored sequentially and can benefit from caching.
Increased Complexity in Implementation: While conceptually simple, linked lists involve more complex code for basic operations (like insertions and deletions) due to the need to manage node connections. This adds complexity compared to arrays, where operations can be more straightforward.
More Difficult to Reverse Traversal (in Singly Linked List): In a singly linked list, traversing the list in reverse is not possible without extra effort (like storing the nodes in a stack). For reverse traversal, doubly linked lists are preferred but come with additional memory costs.
Higher Latency for Large Lists: As the linked list grows, the time taken to traverse the list increases linearly. Accessing elements in the middle or at the end of a large list can be slow, especially compared to arrays where accessing any element is instant.

7. Linked lists in Java

In a singly linked list, we typically maintain a reference only to the first node (called the head). As a result, inserting an item at the end of the list requires traversing the entire list to find the last node, leading to an O(N) time complexity.

However, Java’s LinkedList implementation also keeps a reference to the last node. This means that both inserting and removing items from the end of the list can be done in constant time O(1), as there’s no need to traverse the entire list to locate the last node.

8. Array vs linked list

Feature/Operation	Array	Linked List
Memory Allocation	Contiguous block of memory	Non-contiguous memory, each node stored separately
Size	Fixed size (static) or dynamic (resizable)	Dynamic size, grows and shrinks as needed
Memory Overhead	Minimal, stores only the data	High, stores data + pointer(s) for each node
Cache Performance	High (better cache locality due to contiguity)	Low (poor cache locality due to scattered nodes)
Resizing	Requires reallocation and copying (for dynamic arrays)	Automatic resizing, no need for copying
Best for	Scenarios requiring fast access and indexing	Scenarios requiring frequent insertions/deletions
Use Cases	Lookup tables, matrices, stable-size collections	Stacks, queues, dynamic lists, frequent updates

9. Applications of Linked Lists

Dynamic Memory Allocation:
- Linked lists are widely used for dynamic memory allocation. In scenarios where memory needs to be allocated or deallocated frequently, such as in operating systems, linked lists provide flexibility without the need for resizing (unlike arrays).
- Example: Heap memory management.
Implementing Stacks and Queues:
- Linked lists are used to implement abstract data types like stacks and queues, where elements are frequently inserted or deleted. In a linked list, operations such as push or enqueue and pop or dequeue can be efficiently performed in O(1) time.
Graph Representation:
- Adjacency lists in graph theory are often implemented using linked lists. Each vertex of the graph points to a linked list containing its neighboring vertices, making it an efficient way to represent sparse graphs.
- Example: Graph traversal algorithms (DFS, BFS).
Handling Collisions in Hash Tables:
- In hash tables, collisions occur when two keys hash to the same index. Linked lists are used in separate chaining, where each bucket contains a linked list of key-value pairs that hash to the same index.
Undo/Redo Functionality in Applications:
- Linked lists can be used to implement undo/redo functionality in text editors or other software. Each action is stored as a node in the list, and users can move back or forward through the list of actions.
Music or Video Playlists:
- Linked lists can be used to manage playlists where each song or video is a node, and users can move forward or backward through the playlist.
Job Scheduling and Task Management:
- Linked lists can be used in job scheduling systems to manage tasks dynamically, where tasks are added, executed, and removed based on priority or completion.

10. Program – Implementation of Linked list

Node.java

public class Node<T extends Comparable<T>>{
    private T data;
    private Node<T> nextNode;

    public Node(T data){
        this.data = data;
    }

    public T getData() {
        return data;
    }

    public void setData(T data) {
        this.data = data;
    }

    public Node<T> getNextNode() {
        return nextNode;
    }

    public void setNextNode(Node<T> nextNode) {
        this.nextNode = nextNode;
    }

    @Override
    public String toString() {
        return "Node{" +
                "data=" + data +
                '}';
    }
}

List.java

public interface List<T> {
    public void insert(T data);
    public void remove(T data);
    public void traverse();
    public int size();
}

LinkedList.java

public class LinkedList<T extends Comparable<T>> implements List<T>{
    private Node<T> root;
    private int numOfItems;

    @Override
    public void insert(T data) {
        if(root == null){
            // this is the first item in the linked list
            root = new Node<>(data);
        } else {
            // not the first item in the list
            insertBeginning(data);
        }
    }

    private void insertBeginning(T data){
        Node<T> newNode = new Node<>(data);
        newNode.setNextNode(root);
        root = newNode;
    }

    private void insertEnd(T data, Node<T> node){
        // keep searching for last node
        if(node.getNextNode() != null){
            insertEnd(data, node.getNextNode());
        } else {
            Node<T> newNode = new Node<>(data);
            node.setNextNode(newNode);
        }
    }

    @Override
    public void remove(T data) {
        if(root == null) return;

        //we want to remove the first node (root)
        if(root.getData().compareTo(data) == 0){
            root = root.getNextNode();
        } else {
            remove(data, root, root.getNextNode());
        }
    }

    private void remove(T data, Node<T> previousNode, Node<T> actualNode){
        while(actualNode != null){
            if(actualNode.getData().compareTo(data) == 0){
                numOfItems--;
                previousNode.setNextNode(actualNode.getNextNode());
                actualNode = null;
                return;
            }
            previousNode = actualNode;
            actualNode = actualNode.getNextNode();
        }
    }

    @Override
    public void traverse() {
        if(root == null) return;
        Node<T> actualNode = root;

        while(actualNode != null){
            System.out.println(actualNode);
            actualNode = actualNode.getNextNode();
        }
    }

    @Override
    public int size() {
        return 0;
    }
}

Test.java

public class Test {
    public static void main(String[] args){
        LinkedList<String> names = new LinkedList<>();

        names.insert("first");
        names.insert("second");
        names.insert("third");
        System.out.println("Linked list after insert: ");
        names.traverse();
        names.remove("second");
        System.out.println("Linked list after remove: ");
        names.traverse();

    }
}

Output

Linked list after insert: 
Node{data=third}
Node{data=second}
Node{data=first}
Linked list after remove: 
Node{data=third}
Node{data=first}