AI Hints
Home›DSA in Python Tutorial›Linked Lists
DSA in Python · Lesson 34 of 132

Linked Lists

Nodes and pointers.

⏱ 2 min read▶ Video at 39:30🎓 Free
Watch this lesson in the DSA in Python courseWatch on YouTube ↗Full DSA in Python course

A list keeps items side by side in memory. A linked list doesn't. Each item lives in its own little box, called a node, and every node holds a pointer to the next one, like a treasure hunt where each clue tells you where the next clue is.

Linked Lists
From the video: Linked Lists
  • Not side by side
  • Each item in its own node
  • Each node points to the next

Array or linked list?

In an array, you can jump to any position instantly, but adding at the front shifts everything. In a linked list it's the opposite. Adding at the front is O of one, you just point a new node at the old first one. But reaching the hundredth item means walking through ninety nine nodes first. That's O of N.

Array: indexO(1)
Array: add at frontO(n)
Linked list: add at frontO(1)
Linked list: indexO(n)

Three nodes

A node is a tiny class with two things, a value, and next, which points to the next node. Here we link three nodes together by hand. The head is the first node. To print them all, we follow the next pointers until we reach none. Run it.

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

head = Node("A", Node("B", Node("C")))

node = head
while node:
    print(node.value, end=" -> ")
    node = node.next
print("None")
Output
A -> B -> C -> None

Summary

A linked list is a chain of nodes, each pointing to the next. Adding at the front is O of one, but finding an item is O of N. Next, we'll build a proper linked list class.

Key takeaways
  • Node: value + next
  • Follow next pointers
  • head is the first node
Next up: Building a Linked List — push, find and print