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

Building a Linked List

Push, find and print.

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

Let's wrap our nodes in a class, with methods for the common jobs. Add to the front, find a value, and print the whole list.

Building a Linked List
From the video: Building a Linked List
  • Wrap nodes in a class
  • Add, find, print
  • Your own data structure

A LinkedList class

The Node class is the same as before, so we import it. The list only needs to remember its head. Push front makes a new node that points to the old head, and becomes the new head. That's O of one. Find walks along the nodes until it sees the value. That's O of N. And the string method joins the values with arrows. Run it.

linked_list.pypython
from node import Node
class LinkedList:
    head = None
    def push_front(self, value):
        self.head = Node(value, self.head)
    def find(self, value):
        node = self.head
        while node and node.value != value: node = node.next
        return node is not None
    def __str__(self):
        out, node = "", self.head
        while node: out, node = out + f"{node.value} -> ", node.next
        return out + "None"

lst = LinkedList()
for v in [3, 2, 1]: lst.push_front(v)
print(lst)
print(lst.find(2), lst.find(9))
Output
1 -> 2 -> 3 -> None
True False
Also uses node.py
class Node:
    def __init__(self, value, next=None):
        self.value = value
        self.next = next

def show(head):
    vals = []
    while head:
        vals.append(str(head.value))
        head = head.next
    print(" -> ".join(vals))

Python and linked lists

Python doesn't have a built in linked list, because its lists and deques cover nearly every need. So why learn them? Because linked lists teach you to think in pointers, they appear constantly in interviews, and they're the building blocks of trees and graphs, coming up later.

keyvalue
Built in?no, use list or deque
Why learnthinking in pointers
Interviewsvery common
Leads totrees and graphs

Summary

Our linked list keeps a head, pushes to the front in O of one, and finds values in O of N. Next, deleting a node from the middle.

Key takeaways
  • self.head
  • push_front is O(1)
  • find is O(n)
Next up: Deleting Nodes — re-pointing around a node