Singly Linked List

A Singly Linked List is a type of linked list in which every node has only one pointer: next. Traversal is only possible from front to back.

Node Implementation

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

Insert at Head

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

    def insert_head(self, data):
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node

Insert at Tail

    def insert_tail(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        curr = self.head
        while curr.next:
            curr = curr.next
        curr.next = new_node

Insert at a Specific Position

    def insert_at(self, data, pos):
        if pos == 0:
            self.insert_head(data)
            return
        curr = self.head
        for i in range(pos - 1):
            if not curr:
                raise IndexError("Position exceeds list length")
            curr = curr.next
        new_node = Node(data)
        new_node.next = curr.next
        curr.next = new_node

Delete Node

    def delete(self, data):
        if not self.head:
            return
        if self.head.data == data:
            self.head = self.head.next
            return
        curr = self.head
        while curr.next:
            if curr.next.data == data:
                curr.next = curr.next.next
                return
            curr = curr.next

Traverse and Search

    def traverse(self):
        result = []
        curr = self.head
        while curr:
            result.append(curr.data)
            curr = curr.next
        return result

    def search(self, target):
        curr = self.head
        idx = 0
        while curr:
            if curr.data == target:
                return idx
            curr = curr.next
            idx += 1
        return -1

Time Complexity

Usage Example

sll = SinglyLinkedList()
sll.insert_tail(10)
sll.insert_tail(20)
sll.insert_head(5)
print(sll.traverse())   # [5, 10, 20]
sll.delete(10)
print(sll.traverse())   # [5, 20]

A Singly Linked List can only be traversed in one direction. If you need two-way traversal, use a Doubly Linked List.