Singly Linked List

DSA · Linked Lists

Theory

A linked list stores elements in nodes, where each node holds a value and a pointer to the next node. Nodes do not need to be contiguous in memory, so inserting or deleting at the head is O(1) without shifting anything. The trade-off is that reaching the kth element requires walking from the head, which is O(n), and each node uses extra memory for its pointer.

Why we use it

Linked lists make insertions and deletions cheap when you already have a reference to the position, and they grow without reallocating.

When to use it

Use them for queues and stacks, LRU caches (with a hash map), undo histories, and as building blocks in interview problems. Prefer arrays when you need fast random access.

How it works

  1. head -> node -> node -> None
  2. Each node stores data and next
  3. Traverse? Yes: current = head; while current: visit, current = current.next. No: -.
  4. Reach None: end of list

Syntax

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

Insert at head  O(1)
Search / access O(n)
Delete (given previous node) O(1)

Example

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

class LinkedList:
    def __init__(self):
        self.head = None
    def push_front(self, val):
        node = Node(val)
        node.next = self.head
        self.head = node
    def to_list(self):
        out, cur = [], self.head
        while cur:
            out.append(cur.val)
            cur = cur.next
        return out

ll = LinkedList()
for v in [30, 20, 10]:
    ll.push_front(v)
print("List:", " -> ".join(str(x) for x in ll.to_list()))

Key points

DSA topics

Introduction to DSA

Arrays and Searching

Sorting Algorithms

Linked Lists

Stacks and Queues

Hashing

Trees

Heaps

Graphs

Algorithm Techniques

Classic Algorithms

Dynamic Programming

T
Tech Town
Log InSign Up Free
Home SQL Python DSA Power BI Snowflake Databricks Spark Gen AI Practice Problems Contest Blog

Data Structures & Algorithms

The complete DSA roadmap: theory, why and when to use every structure and algorithm, Big O complexity, and Python code you can run right here in the browser.

{{ sectionCount }}
Sections
{{ topicCount }}
Topics
Free
Forever
Hands-on practice Practice DSA Online 251 problems across 13 patterns, with hidden tests and step-by-step optimal solutions. Start practising →
Section {{ sec.num }}

{{ sec.label }}

DSA  /  {{ current.sectionLabel }}  /  {{ current.name }}

{{ current.name }}

Theory

{{ current.def }}

Why we use it

{{ current.why }}

When to use it

{{ current.when }}

Flowchart — how {{ current.name }} works
{{ nd.text }}
{{ nd.text }}
◇ {{ nd.text }}
Yes → {{ nd.yes }}
No → {{ nd.no }}
Step-by-step visualisation
{{ cell.v }}
{{ cell.i }} {{ cell.tag }}
Step {{ vizStepLabel }}: {{ vizNote }}
■ comparing ■ swapping / moving ■ done / found ■ out of range
Complexity & Pseudocode
{{ current.syntax }}
Example Code
{{ current.example }}
▶ Try It Live — runs real Python 3 in your browser (first run loads the engine)
{{ liveOutput }}
{{ liveError }}
Key Points — click to check off as you learn
  • {{ pt.mark }} {{ pt.text }}

Share this topic