Linked Lists

🔗 What is a Linked List?

A Linked List is a dynamic data structure where elements (nodes) are connected through pointers. Unlike arrays, elements aren't stored in consecutive memory locations.


# Simple linked list node
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

# Create nodes
node1 = Node(10)
node2 = Node(20)
node3 = Node(30)

# Link them together
node1.next = node2
node2.next = node3

# Traverse: 10 -> 20 -> 30 -> None
current = node1
while current:
    print(current.data, end=" -> ")
    current = current.next
print("None")

Dynamic

Size

O(1)

Insert/Delete

Nodes

Structure

Lesson 1: Simple Linked List

Create a basic linked list with essential operations:

Basic Linked List


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

class LinkedList:
    def __init__(self):
        self.head = None
    
    def append(self, data):
        """Add element to end"""
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        
        current = self.head
        while current.next:
            current = current.next
        current.next = new_node
    
    def prepend(self, data):
        """Add element to beginning"""
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node
    
    def delete(self, data):
        """Remove first occurrence of data"""
        if not self.head:
            return
        
        if self.head.data == data:
            self.head = self.head.next
            return
        
        current = self.head
        while current.next:
            if current.next.data == data:
                current.next = current.next.next
                return
            current = current.next
    
    def display(self):
        """Print all elements"""
        elements = []
        current = self.head
        while current:
            elements.append(str(current.data))
            current = current.next
        print(" -> ".join(elements) + " -> None")
    
    def size(self):
        """Get number of elements"""
        count = 0
        current = self.head
        while current:
            count += 1
            current = current.next
        return count

# Example usage
ll = LinkedList()
ll.append(10)
ll.append(20)
ll.prepend(5)
ll.display()  # 5 -> 10 -> 20 -> None

ll.delete(10)
ll.display()  # 5 -> 20 -> None
print(f"Size: {ll.size()}")  # 2

Lesson 2: Types of Linked Lists

➡️

Singly Linked

Each node points to next node

Simple Forward only

↔️

Doubly Linked

Nodes have next and previous pointers

Bidirectional More memory

🔄

Circular Linked

Last node points back to first

No null end Continuous

🔗

Circular Doubly

Combines circular and doubly features

Complex Full navigation

Lesson 3: Doubly Linked List

Navigate in both directions:

Doubly Linked List


class DoublyNode:
    def __init__(self, data):
        self.data = data
        self.next = None
        self.prev = None

class DoublyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None
    
    def append(self, data):
        """Add to end"""
        new_node = DoublyNode(data)
        if not self.head:
            self.head = self.tail = new_node
        else:
            new_node.prev = self.tail
            self.tail.next = new_node
            self.tail = new_node
    
    def prepend(self, data):
        """Add to beginning"""
        new_node = DoublyNode(data)
        if not self.head:
            self.head = self.tail = new_node
        else:
            new_node.next = self.head
            self.head.prev = new_node
            self.head = new_node
    
    def display_forward(self):
        """Print from head to tail"""
        elements = []
        current = self.head
        while current:
            elements.append(str(current.data))
            current = current.next
        print("Forward: " + " <-> ".join(elements))
    
    def display_backward(self):
        """Print from tail to head"""
        elements = []
        current = self.tail
        while current:
            elements.append(str(current.data))
            current = current.prev
        print("Backward: " + " <-> ".join(elements))

# Example usage
dll = DoublyLinkedList()
dll.append(10)
dll.append(20)
dll.prepend(5)

dll.display_forward()   # Forward: 5 <-> 10 <-> 20
dll.display_backward()  # Backward: 20 <-> 10 <-> 5

Lesson 4: Useful Operations

Essential linked list operations:

Common Operations


class LinkedList:
    def __init__(self):
        self.head = None
    
    def find(self, data):
        """Search for element"""
        current = self.head
        position = 0
        while current:
            if current.data == data:
                return position
            current = current.next
            position += 1
        return -1  # Not found
    
    def get_at(self, index):
        """Get element at index"""
        current = self.head
        for i in range(index):
            if not current:
                return None
            current = current.next
        return current.data if current else None
    
    def reverse(self):
        """Reverse the linked list"""
        prev = None
        current = self.head
        
        while current:
            next_node = current.next
            current.next = prev
            prev = current
            current = next_node
        
        self.head = prev
    
    def remove_duplicates(self):
        """Remove duplicate elements"""
        if not self.head:
            return
        
        seen = set()
        current = self.head
        prev = None
        
        while current:
            if current.data in seen:
                prev.next = current.next
            else:
                seen.add(current.data)
                prev = current
            current = current.next
    
    def merge_sorted(self, other_list):
        """Merge two sorted linked lists"""
        dummy = Node(0)
        current = dummy
        
        p1, p2 = self.head, other_list.head
        
        while p1 and p2:
            if p1.data <= p2.data:
                current.next = p1
                p1 = p1.next
            else:
                current.next = p2
                p2 = p2.next
            current = current.next
        
        # Add remaining elements
        current.next = p1 or p2
        
        # Create new list with merged result
        result = LinkedList()
        result.head = dummy.next
        return result

# Example usage
ll = LinkedList()
for val in [3, 1, 4, 1, 5]:
    ll.append(val)

print(f"Find 4: position {ll.find(4)}")  # 2
print(f"Element at index 2: {ll.get_at(2)}")  # 4

ll.remove_duplicates()
ll.display()  # 3 -> 1 -> 4 -> 5 -> None

ll.reverse()
ll.display()  # 5 -> 4 -> 1 -> 3 -> None

Practice Project: Music Playlist

Create a music playlist using linked lists:

Music Playlist


class Song:
    def __init__(self, title, artist):
        self.title = title
        self.artist = artist
        self.next = None
    
    def __str__(self):
        return f"{self.title} by {self.artist}"

class Playlist:
    def __init__(self, name):
        self.name = name
        self.head = None
        self.current = None
    
    def add_song(self, title, artist):
        """Add song to end of playlist"""
        new_song = Song(title, artist)
        if not self.head:
            self.head = new_song
            self.current = new_song
        else:
            current = self.head
            while current.next:
                current = current.next
            current.next = new_song
        print(f"Added: {new_song}")
    
    def play_current(self):
        """Play current song"""
        if self.current:
            print(f"♪ Now playing: {self.current}")
        else:
            print("No song selected")
    
    def next_song(self):
        """Move to next song"""
        if self.current and self.current.next:
            self.current = self.current.next
            print(f"Next: {self.current}")
        else:
            print("End of playlist")
    
    def restart(self):
        """Go back to first song"""
        self.current = self.head
        if self.current:
            print(f"Restarted: {self.current}")
    
    def show_playlist(self):
        """Display all songs"""
        print(f"\n=== {self.name} ===")
        current = self.head
        index = 1
        while current:
            marker = "► " if current == self.current else "  "
            print(f"{marker}{index}. {current}")
            current = current.next
            index += 1
        print()

# Example usage
my_playlist = Playlist("My Favorites")

# Add songs
my_playlist.add_song("Bohemian Rhapsody", "Queen")
my_playlist.add_song("Hotel California", "Eagles")
my_playlist.add_song("Stairway to Heaven", "Led Zeppelin")

# Show playlist
my_playlist.show_playlist()

# Play songs
my_playlist.play_current()
my_playlist.next_song()
my_playlist.next_song()
my_playlist.show_playlist()

# Restart
my_playlist.restart()
my_playlist.show_playlist()