Singly Linked List

Learn about singly linked lists and how they function.

What is a Singly Linked List?

A singly linked list is a linear data structure made up of nodes where each node points to the next node in the sequence. Unlike arrays, linked lists don't store elements in contiguous memory locations, which means they can dynamically grow or shrink as needed.

Each node in a singly linked list has two components:

  1. Data: The actual value stored in the node.
  2. Pointer: A reference (or link) to the next node.

The first node is called the head, and the last node points to null (or None in Python), indicating the end of the list.

Why Use Singly Linked Lists?

Singly linked lists are useful when you need:

  • Dynamic size: They can grow or shrink without worrying about memory allocation.
  • Efficient insertion and deletion: Unlike arrays, there’s no need to shift elements around.

However, they do have drawbacks:

  • Sequential access: You can't directly access elements by index.
  • Extra memory: Each node requires additional space for the pointer.

Operations

Here are the most common operations on a singly linked list:

  • Insertion: Add a new node at the beginning O(1), end O(n), or a specific position O(n).
  • Deletion: Remove a node by its position or value.
  • Traversal: Go through the list to access or modify data O(n).
  • Search: Find an element in the list O(n).

Code Examples

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class SinglyLinkedList:
    def __init__(self):
        self.head = None

    def insert_at_head(self, value):
        new_node = Node(value)
        new_node.next = self.head
        self.head = new_node

    def print_list(self):
        current = self.head
        while current:
            print(current.data, "->", end=" ")
            current = current.next
        print("NULL")

sll = SinglyLinkedList()
sll.insert_at_head(10)
sll.insert_at_head(20)
sll.insert_at_head(30)
sll.print_list()

Problems to Solve

Important Problems on Linked Lists

Resources