Python Linked Lists

Linked lists are like a series of connected boxes, where each box holds a piece of information and points to the next box. Let’s understand how to create and use Linked lists in Python.

Linked Lists Made Simple in Python

They’re a cool way to organize data in Python. Let’s check out how to use linked lists in Python in a simple and friendly way.

What is a Linked List?

Imagine you have a string of boxes and each box stores a number inside. These boxes are a linked list. Instead of standing in a line like arrays, linked list boxes are scattered around, and each box knows where the next one is.

Also Read: Python HeapQ Explained with Examples

Types of Linked Lists

Singly Linked List

Imagine a line of people holding hands. Each person (node) holds the hand of the person in front. This is a single link list. Check on the below code illustrating the simple doubly linked list. Please note the cell in the below code represents a node in the link list.

# Creating a singly linked list
cell1 = Cell(1)
cell2 = Cell(2)
cell3 = Cell(3)
cell1.next = cell2
cell2.next = cell3

Doubly Linked List

Now, picture a line where each person holds hands with the person in front and behind. This is a doubly linked list. The below is a logical representation of a doubly linked list in Python.

# Creating a doubly linked list
cell1 = Cell(1)
cell2 = Cell(2)
cell3 = Cell(3)

cell1.next = cell2
cell2.prev = cell1
cell2.next = cell3
cell3.prev = cell2

Circular Linked List

Imagine a group of people in a circle, holding hands with the person next to them and the last person holding hands with the first. This is a circular linked list.

Here is a simple demonstration of a circular link list in Python.

# Creating a circular linked list
cell1 = Cell(1)
cell2 = Cell(2)
cell3 = Cell(3)

cell1.next = cell2
cell2.next = cell3
cell3.next = cell1

Must Read: How to Create and Use Arrays in Python

Implement Linked Lists in Python

Firstly, before we start, let’s create a helper, the Cell class, which represents each node in our linked list.

class Cell:
    def __init__(self, value):
        self.value = value
        self.next = None

Secondly, we’ll use the above class in all of the examples of this tutorial. We’ll derive other link list classes from it.

Singly Linked List Example

Now, let’s create a simple singly linked list that points from one box to the next.

class SinglyLkdList:
    def __init__(self):
        self.head = None

    def append(self, data):
        new_node = Cell(data)
        if not self.head:
            self.head = new_node
            return
        current = self.head
        while current.next:
            current = current.next
        current.next = new_node

    def disp(self):
        elements = []
        current = self.head
        while current:
            elements.append(current.data)
            current = current.next
        print(" -> ".join(map(str, elements)))

Let’s use this linked list:

sin_list = SinglyLkdList()
sin_list.append(1)
sin_list.append(2)
sin_list.append(3)

sin_list.disp()
# Output: 1 -> 2 -> 3

Doubly Linked List Example

Now, let’s enhance our linked list to remember the person behind too.

class DoublyLkList:
    def __init__(self):
        self.head = None

    def append(self, data):
        new_node = Cell(data)
        if not self.head:
            self.head = new_node
            return
        current = self.head
        while current.next:
            current = current.next
        current.next = new_node
        new_node.prev = current

    def disp(self):
        elements = []
        current = self.head
        while current:
            elements.append(current.data)
            current = current.next
        print(" <-> ".join(map(str, elements)))

Let’s use this doubly linked list:

dob_list = DoublyLkList()
dob_list.append(1)
dob_list.append(2)
dob_list.append(3)

dob_list.disp()
# Output: 1 <-> 2 <-> 3

Circular Linked List Example

Lastly, let’s create a circular linked list, a fun loop of holding hands.

class CircularLkdList:
    def __init__(self):
        self.head = None

    def append(self, data):
        new_node = Cell(data)
        if not self.head:
            self.head = new_node
            new_node.next = self.head
            return
        current = self.head
        while current.next != self.head:
            current = current.next
        current.next = new_node
        new_node.next = self.head

    def disp(self):
        elements = []
        current = self.head
        while True:
            elements.append(current.data)
            current = current.next
            if current == self.head:
                break
        print(" -> ".join(map(str, elements)))

Let’s use this circular linked list:

cir_list = CircularLkdList()
cir_list.append(1)
cir_list.append(2)
cir_list.append(3)

cir_list.disp()
# Output: 1 -> 2 -> 3 -> 1

Common Linked List Operations

In this section, we added Python examples to demonstrate the common linked list operations. You can perform them on the link lists.

Searching in a Linked List

Imagine finding a person in our line of linked boxes. Let’s create a simple way to search for a specific number.

def search_list(self, key):
    current = self.head
    while current:
        if current.data == key:
            return True
        current = current.next
    return False

Deleting from a Linked List

Imagine removing a person from our line. Let’s create a way to delete a specific number.

def del_list_item(self, key):
    current = self.head
    prev = None
    while current:
        if current.data == key:
            if prev:
                prev.next = current.next
            else:
                self.head = current.next
            return
        prev = current
        current = current.next

Reversing a Linked List

Imagine flipping our line of people around. Let’s create a way to reverse our linked list.

def rev_list(self):
    current = self.head
    prev = None
    while current:
        next_node = current.next
        current.next = prev
        prev = current
        current = next_node
    self.head = prev

Pros and Cons of Linked Lists

Pros:

• Dynamic Size: Linked lists can grow or shrink during runtime.
• Easy Insertion/Deletion: Adding or removing elements is efficient.

Cons:

• Random Access is Slow: Accessing an element at a specific index takes time.
• Extra Memory Usage: Each element requires extra space for the pointer.

Use Cases in Python

Here are some common scenarios where linked lists can be useful in Python.

• When Size is Unknown: Linked lists are great when you don’t know the size of your data in advance.
• Frequent Insertions/Deletions: If your program involves a lot of adding or removing elements, linked lists can be more efficient than arrays.

Choosing the Right Type

• Singly Linked List: Use when traversal is mainly forward, and memory efficiency is a concern.
• Doubly Linked List: Use when backward traversal is needed or when insertion/deletion at both ends is frequent.
• Circular Linked List: Use when the data needs to be accessed in a loop.

Before you leave, render your support for us to continue. If you like our tutorials, share this post on social media like Facebook/Twitter.

Happy coding,
TechBeamers.