Single Linked List

A Singly Linked List is a common data structure used to store and organize data. It consists of a series of nodes, where each node contains two parts: a data field and a reference (pointer) pointing to the next node in the sequence.

The characteristic feature of a singly linked list is that each node has only one pointer, which points to the subsequent node. The last node points to null, indicating the end of the chain.

Below is an example of a singly linked list:

Head Node -> Node 1 -> Node 2 -> Node 3 -> ... -> Tail Node -> null

The head node serves as the starting point of the list, while the tail node marks its ending point. Each node contains a data field for storing specific information and a pointer field pointing to the next node. By traversing through the head node, one can iterate through the entire linked list. To access a specific node within the list, it is necessary to start from the head node and sequentially follow the pointers of each node until the target node is reached.

Insertion and deletion operations in singly linked lists are relatively simple and efficient. When inserting a new node, only the adjacent nodes' pointers need modification; there is no requirement to move other existing nodes. Deleting a node involves modifying the pointer of the preceding node to point directly to the next node of the one being deleted, followed by freeing the memory space occupied by the deleted node.

However, because each node in a singly linked list contains only one pointer, it is impossible to directly access the previous node. Therefore, special attention must be paid when deleting or inserting nodes.

Singly linked lists offer certain advantages under specific scenarios, such as situations where insertion and deletion operations are frequent but random access requirements are low. However, due to the inability to directly access the preceding node, retrieving a predecessor for any given node is cumbersome, and constant-time random access cannot be implemented.

Additionally, there exist other types of linked lists, such as Doubly Linked Lists (Doubly Linked List), which include two pointers in each node—one pointing to the previous node and another pointing to the next node—thereby providing greater flexibility and functionality.

Code Implementation

::: code-tabs
@tab Java

public class SinglyLinkedList<T> {
    // Field used for storing data
    public class Node {
        public T data;
        public Node nextNode;
    }
    
    public Node headNode;
    public int size;
    
    public SinglyLinkedList() {
        headNode = null;
        size = 0;
    }
    
    // Method to check if the list is empty
    public boolean isEmpty() {
        if (headNode == null) return true;
        return false;
    }
    
    // Insert data at the head of the linked list
    public void insertAtHead(T data) {
        Node newNode = new Node();
        newNode.data = data;
        newNode.nextNode = headNode;
        headNode = newNode;
        size++;
    }
    
    // Insert data at the end (tail) of the linked list
    public void insertAtEnd(T data) {
        if (isEmpty()) {
            insertAtHead(data);
            return;
        }
        
        Node newNode = new Node();
        newNode.data = data;
        newNode.nextNode = null;
        
        Node last = headNode;
        while (last.nextNode != null) {
            last = last.nextNode;
        }
        
        last.nextNode = newNode;
        size++;
    }
    
    // Insert data after a specific node value
    public void insertAfter(T data, T previous) {
        Node newNode = new Node();
        newNode.data = data;
        Node currentNode = this.headNode;
        
        while (currentNode != null && !currentNode.data.equals(previous)) {
            currentNode = currentNode.nextNode;
        }
        
        if (currentNode != null) {
            newNode.nextNode = currentNode.nextNode;
            currentNode.nextNode = newNode;
            size++;
        }
    }
    
    // Print the linked list contents to console
    public void printList() {
        if (isEmpty()) {
            System.out.println("List is Empty!");
            return;
        }
        
        Node temp = headNode;
        System.out.print("List : ");
        
        while (temp.nextNode != null) {
            System.out.print(temp.data.toString() + " -> ");
            temp = temp.nextNode;
        }
        
        System.out.println(temp.data.toString() + " -> null");
    }
    
    // Search for a given value in the linked list and return true if found, false otherwise
    public boolean searchNode(T data) {
        Node currentNode = this.headNode;
        while (currentNode != null) {
            if (currentNode.data.equals(data))
                return true;
            currentNode = currentNode.nextNode;
        }
        return false;
    }
    
    // Delete the data at the head of the linked list
    public void deleteAtHead() {
        if (isEmpty())
            return;
        
        headNode = headNode.nextNode;
        size--;
    }
    
    // Remove a specific value from the linked list by its data content
    public void deleteByValue(T data) {
        if (isEmpty())
            return;
            
        Node currentNode = this.headNode;
        Node prevNode = null; 
        
        if(currentNode.data.equals(data)) {
            // Handle deletion of the head node specifically
            deleteAtHead();
            return;
        }
        
        // Traverse the list to locate and remove the specified value
        while (currentNode != null) {
            // Found the data matching the target for removal
            if (!data.equals(currentNode.data)){
                continue; 
            } else {
                prevNode.nextNode = currentNode.nextNode;
                size--;
                return; 
            }
            
            prevNode = currentNode;
            currentNode = currentNode.nextNode;
        }
    }
}

:::