Types of Linked Lists

Types of Linked Lists

Not all Linked Lists are created equal. Depending on the problem you are trying to solve, you might need a different type of chain.

Let's explore the three most common types of Linked Lists in Data Structures and Algorithms!

1. Singly Linked List

The Singly Linked List is the most basic version. This is the one we have been looking at in previous tutorials.

• Structure: Each Node contains Data and one pointer (Next).
• Direction: You can only travel strictly forward (from Head to Tail).
• End: The Tail node points to NULL.

Pros & Cons

• ✅ Uses the least amount of memory.
• ❌ If you are at the end of the list and want to look at the previous item, you have to start all over again from the Head!

2. Doubly Linked List

The Doubly Linked List fixes the main weakness of the Singly Linked List by giving you the ability to walk backwards.

• Structure: Each Node contains Data and two pointers (Next and Prev).
• Direction: You can travel forward and backward.
• End: The Head's Prev pointer is NULL, and the Tail's Next pointer is NULL.

Real-Life Analogy

Think of your web browser's history. You can click the "Forward" button to go to the next page, but you can also click the "Back" button to return to the previous page instantly.

Pros & Cons

• ✅ Very fast to delete an element or move backwards.
• ❌ Takes up more memory because every Node has to store an extra pointer. More pointers also mean more code complexity when inserting items.

3. Circular Linked List

The Circular Linked List is a chain that never ends.

• Structure: Same as a Singly Linked List (Data + Next pointer).
• Direction: You travel forward continuously.
• End: There is no NULL! The Tail node's Next pointer simply loops all the way back around to the Head.

(Note: You can also create a Doubly Circular Linked List, where both the Next and Prev pointers loop around!)

Real-Life Analogy

Think of a multiplayer board game like Monopoly. Player 1 takes a turn, then Player 2, then Player 3, then Player 4. Who goes after Player 4? It loops right back to Player 1!

Visualizing the Differences

Here is a quick visual reference for how these three structures differ in memory:

The 3 Types: Singly (Forward), Doubly (Both ways), and Circular (Infinite Loop).

Coding a Doubly Linked List Node

Let's look at how the code changes when we upgrade from a Singly Linked List to a Doubly Linked List in Python.

Notice how we just add a self.prev property to the Node class!

class DoublyNode:
    def __init__(self, data):
        self.data = data
        self.next = None  # Points forward
        self.prev = None  # Points backward
# 1. Create Nodes
node1 = DoublyNode("A")
node2 = DoublyNode("B")
# 2. Link them Forward AND Backward!
node1.next = node2
node2.prev = node1

print("Forward link from node1:", node1.next.data)
print("Backward link from node2:", node2.prev.data)