Singly Linked List Data Structure

In this article we are going to learn all about the Singly Linked List and its structure, in which each node points to the next node of the list. We will also see its operations, implementation, advantages, disadvantages and more.

What is Singly Linked List?

A Singly Linked List is a linear (ordered) data structure that contains a collection of elements, and each element is connected to its next element in a sequence.

Each element in a singly linked list is called a Node. The node consists of two fields: a data field and the reference field (address of the next node).

There is a HEAD pointer, which points to the first node of the singly linked list; if the list is empty, it stores NULL. The last node is called the Tail, and it stores NULL in its reference field (next).

A singly linked list can be traversed only in the forward direction because each node contains the address of the next node only.

Operations on Singly Linked List

The following operations can be performed on a singly linked list.

Insertion

A new node can be added at the following positions of the singly linked list.

• Insert a node at the beginning
• Insert a node at the end
• Insert a node at a specific position

Deletion

An existing node can be deleted from the following positions of the singly linked list.

• Delete a node at the beginning
• Delete a node at the end
• Delete a node at a specific position

Traversal

Traversal can be performed only in the forward direction. Start from the head and move through each node using the next pointers till the last node of the singly linked list.

Searching

We can search for a specific node in the singly linked list by comparing each node's data with the key.

Singly Linked List implementation in Java

// Java program to implement a Singly Linked List
class Node {
  public int data;
  public Node next;
  public Node(int data) {
    this.data = data;
    this.next = null;
  }
}

public class SinglyLinkedList {
  // Create a head node which will point to the first node of the list
  Node head;

  // Method to insert a node in the list
  public void insert(int data) {
    Node newNode = new Node(data);
    if (head == null) {
      head = newNode;
      return;
    }
    Node last = head;
    while (last.next != null) {
      last = last.next;
    }
    last.next = newNode;
  }

  // Method to print list
  public void printList() {
    Node node = head;
    while (node != null) {
      System.out.print(node.data + " ");
      node = node.next;
    }
  }

  public static void main(String[] args) {
    SinglyLinkedList list = new SinglyLinkedList();

    // Insert elements in the list
    list.insert(10);
    list.insert(20);
    list.insert(30);
    list.insert(40);
    list.insert(50);

    // Print list elements
    System.out.print("Singly Linked List elements: ");
    list.printList();
  }
}

Singly Linked List elements: 10 20 30 40 50

In the above example, the Node class represents a single element of the linked list, and the SinglyLinkedList class is used to create a linked list, insert a node in the list, and display the elements of the linked list.

Advantages of Singly Linked List

• Dynamic data structure
• No memory wastage
• Easy implementation
• Efficient insertion and deletion operations
• Flexible
• Efficient for large data
• Scalability

Disadvantages of Singly Linked List

A linked list is a very popular and flexible data structure, but it has certain disadvantages as well. Some of the key disadvantages of linked lists are:

• Random access is inefficient
• Additional memory required for pointers
• Potential for memory fragmentation
• Potential for memory leaks