Python Tutorial

Python Control Flow

Python OOP

Python File Handling

Python DSA

Python Linked Lists

❮ Previous Next ❯

Python Linked Lists

A Linked List is a linear data structure, but unlike an array, its elements are not stored at contiguous memory locations. Instead, the elements are linked using pointers. Each element, called a Node, is composed of two parts:

  1. Data: The value stored in the node.
  2. Next: A reference (or "pointer") to the next node in the sequence. The last node's next pointer is typically None, indicating the end of the list.

Linked Lists vs. Arrays/Lists

The key difference lies in memory allocation and its consequences.

Feature Array / Python List Linked List
Memory Contiguous (elements are neighbors) Non-contiguous (elements can be anywhere)
Access O(1) - Fast random access by index O(n) - Slow, must traverse from the head
Insertion/Deletion O(n) - Slow (elements must be shifted) O(1) - Fast (if at head/tail or known node)
Size Dynamic (but can be costly to resize) Dynamic (easy to grow/shrink one node at a time)

Implementing a Linked List in Python

To build a linked list, we first need a Node class and then a LinkedList class to manage the nodes.

1. The Node Class

This is the basic building block.

Node Class

class Node:
    def __init__(self, data):
        self.data = data  # The data held by the node
        self.next = None  # The pointer to the next node

2. The LinkedList Class

This class will manage the overall structure, starting with the head of the list.

LinkedList Class with Methods

class LinkedList:
    def __init__(self):
        self.head = None # The list is initially empty
    // Method to add a new node at the end of the list
    def append(self, data):
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
            return
        last_node = self.head
        while last_node.next:
            last_node = last_node.next
        last_node.next = new_node
    // Method to print the list
    def print_list(self):
        current_node = self.head
        while current_node:
            print(current_node.data, end=" -> ")
            current_node = current_node.next
        print("None")


// --- Usage ---
llist = LinkedList()
llist.append("A")
llist.append("B")
llist.append("C")


llist.print_list() # Output: A -> B -> C -> None

Types of Linked Lists: The one shown above is a **Singly Linked List**. There are also **Doubly Linked Lists**, where each node has a pointer to the `next` and `previous` node, and **Circular Linked Lists**, where the last node points back to the first node.

Exercise

?

What is the main disadvantage of a linked list compared to a Python list?

❮ Previous Next ❯