🎓 A1Learner
🔍
0 of 100 lessons completed

DSA Linked Lists

A linked list is a chain of nodes that holds values in order. Each node holds one value and a link to the next node.

One node

A node stores a value in value and the next node in next. A lone node points to None.

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

node = Node(7)
print(node.value)
print(node.next)

Link three nodes

Setting next joins two nodes into a chain. The first node is the head.

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

first = Node(10)
second = Node(20)
third = Node(30)
first.next = second
second.next = third
print(first.value)
print(first.next.value)
print(first.next.next.value)

Walk the chain

A while loop follows next until it reaches None. Each step moves to the next node.

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


def build(values):
    head = None
    tail = None
    for value in values:
        node = Node(value)
        if head is None:
            head = node
            tail = node
        else:
            tail.next = node
            tail = node
    return head


def render(head):
    parts = []
    node = head
    while node is not None:
        parts.append(str(node.value))
        node = node.next
    parts.append("None")
    return " -> ".join(parts)

head = build([4, 8, 15])
node = head
while node is not None:
    print(node.value)
    node = node.next

Example

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


def build(values):
    head = None
    tail = None
    for value in values:
        node = Node(value)
        if head is None:
            head = node
            tail = node
        else:
            tail.next = node
            tail = node
    return head


def render(head):
    parts = []
    node = head
    while node is not None:
        parts.append(str(node.value))
        node = node.next
    parts.append("None")
    return " -> ".join(parts)

head = build([4, 8, 15, 16, 23])
print(render(head))
length = 0
visits = 0
node = head
while node is not None:
    length += 1
    visits += 1
    node = node.next
print("Length:", length)
print("Visits:", visits)

Key points

  • Node: one link in the chain, holding a value and a next link
  • Head: the first node, and the only entry point to the chain
  • The last node's next link holds None, which marks the end
  • Walking the chain means following next links from the head
  • A linked list holds its values in nodes linked in order, not in fixed slots

In this example, build links five nodes into one chain. render walks the chain and joins the values with arrows. The counting loop then walks the chain again and counts one visit per node. The visit count equals the length, so reaching every value costs one step per node.

Note

Python has no built-in linked list type, so the Node class is the whole structure.

Try it Yourself

Edit the code, then press Run.

Running is simulated · Python Playground

Exercise

What does the next link of the last node hold?