DSA — Linear DS

Singly Linked List

Nodes connected by pointers. Efficient O(1) head insertion/deletion but no random access. Foundation for stacks, queues, and more.

— min read

O(n)Access

O(1)Insert Head

O(n)Search

Node→Traversal

✓Dynamic

Interactive List

Modify the list to see O(1) vs O(n) operations.

How It Works

Python Code

Complexity

Practice

Node Structure

A node contains its value and a pointer (next) to the following node.

Insert Head

Simply point the new node's next to current head. Constant time O(1).

Traversal

Start from head and follow next pointers until null. Linear time O(n).

Delete Node

Update previous node's next to skip the deleted node. O(n) to find, O(1) to delete.

Python — SLL Implementation

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

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

    def push_front(self, val):  # O(1)
        node = Node(val)
        node.next = self.head
        self.head = node

    def append(self, val):  # O(n)
        node = Node(val)
        if not self.head:
            self.head = node
            return
        curr = self.head
        while curr.next:
            curr = curr.next
        curr.next = node

    def pop_front(self):  # O(1)
        if not self.head:
            return None
        val = self.head.val
        self.head = self.head.next
        return val

    def find(self, val):  # O(n)
        curr = self.head
        while curr:
            if curr.val == val:
                return True
            curr = curr.next
        return False

Operation	Time	Space
Access	`O(n)`	`O(1)`
Insert Head	`O(1)`	`O(1)`
Insert Tail	`O(n)`	`O(1)`
Delete Head	`O(1)`	`O(1)`
Delete Tail	`O(n)`	`O(1)`
Search	`O(n)`	`O(1)`

Tip: Keep a tail pointer to make append O(1). This is commonly done in practice for queues.

Progress0 / 8 solved

#01Reverse Linked ListGoogle

#02Middle of the Linked ListAmazon

#03Linked List CycleMeta

#04Remove Linked List ElementsEasy

#05Palindrome Linked ListMicrosoft

#06Intersection of Two Linked ListsAmazon

#07Remove Nth Node From EndMeta

#08Merge Two Sorted ListsGoogle

← Arrays & Strings Doubly Linked List →