Data Structures in Python 🐍2️⃣ Singly Linked List

What is Singly Linked List🤔

🤯➡️🌗➡️🌗️➡️🌗➡️🌗➡️🌗➡️🕳️
Every linked list consists of nodes🌗, each node has two components:
1. Data 🌕 which allows to store an element of data.
2. Next 🌑 which stores a pointer that points from one node to another.
Start of the element is called head🤯, that points to the beginning of the linked list. The last node in a singly linked list points to None🕳️, and that tells you that it’s the end of the linked list.

Implementation 🧑🏻‍💻

We start by creating a class LinkedList

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

1. Insertion

Now we will look at insertion: we can do insertion in different ways like append, prepend or insert after node. To start with insertion we need node.
We will create a class Node🌗.

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

Now we will look at append method

def append(self, data):
    new_node = Node(data)
    if self.head is None:
        self.head = new_node
        return
    current_node = self.head
    while current_node.next:
        current_node = current_node.next
    current_node.next = new_node

Seems good till now 🤔 We need to check the content of the linked list. For this, we will implement a new function print_list method

def print_list(self):
    current_node = self.head
    while current_node:
        print(current_node.data)
        current_node = current_node.next

Now we will look at prepend method where we insert an element at the beginning of the linked list.

def prepend(self, data):
    new_node = Node(data)
    new_node.next = self.head
    self.head = new_node

2. Deletion 🗑️

We will implement deletion by value and deletion by position.
Let’s start by deletion_by_value method.

def deletion_by_value(self, value):
    current_node = self.head

    if current_node and current_node.data == value:
        self.head = current_node.next
        current_node = None
        return

    previous_node = None
    while current_node and current_node.data != value:

        previous_node = current_node
        current_node = current_node.next

    if current_node is None:
        return
    previous_node.next = current_node.next
    current_node = None

We will implement deletion by value and deletion by position.
Let’s start by deletion_by_position method.

def deletion_by_position(self, pos):

    if self.head:
        current_node = self.head
        if pos == 0:
            self.head = current_node.next
            current_node = None
            return

    count = 0
    previous_node = None
    while current_node and count != pos:
        previous_node = current_node
        current_node = current_node.next
        count += 1

    if current_node is None:
        return
    
    previous_node.next = current_node.next
    current_node = None

3. Length 🦒

We will now implement length method to calculate the length or the number of nodes in a given linked list

def length(self):
    current_node = self.head
    length = 0
    while current_node:
        length+=1
        current_node = current_node.next
    return length

4. Node Swap 💫

Now let’s look at the task of swapping nodes, we will swap the nodes that contains specific keys.

def swap_nodes(self, key_1, key_2):
    if key_1 == key_2:
        return

    current_node_1 = self.head
    previous_node_1 = None
    while current_node_1 and current_node_1.data != key_1:
        previous_node_1 = current_node_1
        current_node_1 = current_node_1.next

    current_node_2 = self.head
    previous_node_2 = None
    while current_node_2 and current_node_2.data != key_2:
        previous_node_2 = current_node_2
        current_node_2 = current_node_2.next

    if not current_node_1 or not current_node_2:
        return

    if previous_node_1:
        previous_node_1.next = current_node_2
    else:
        self.head = current_node_2

    if previous_node_2:
        previous_node_2.next = current_node_1
    else:
        self.head = current_node_1

    current_node_1.next, current_node_2.next = current_node_2.next, current_node_1.next

5. Reverse 🔀

let’s reverse a singly linked list now.
🤯➡️🌗➡️🌗️➡️🌗➡️🌗➡️🕳️
🕳️⬅️🌗⬅️🌗⬅️🌗⬅️🌗⬅️🤯

def reverse(self):
    current_node = self.head
    previous_node = None
    while current_node:
        next = current_node.next
        current_node.next = previous_node
        previous_node = current_node
        current_node = next
    self.head = previous_node

Wrapping Up

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

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

    def append(self, data):
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
            return
        current_node = self.head
        while current_node.next:
            current_node = current_node.next
        current_node.next = new_node

    def prepend(self, data):
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node

    def deletion_by_value(self, value):
        current_node = self.head

        if current_node and current_node.data == value:
            self.head = current_node.next
            current_node = None
            return

        previous_node = None
        while current_node and current_node.data != value:

            previous_node = current_node
            current_node = current_node.next

        if current_node is None:
            return
        previous_node.next = current_node.next
        current_node = None

    def deletion_by_position(self, pos):

        if self.head:
            current_node = self.head
            if pos == 0:
                self.head = current_node.next
                current_node = None
                return

        count = 0
        previous_node = None
        while current_node and count != pos:
            previous_node = current_node
            current_node = current_node.next
            count += 1

        if current_node is None:
            return

        previous_node.next = current_node.next
        current_node = None

    def length(self):
        current_node = self.head
        length = 0
        while current_node:
            length+=1
            current_node = current_node.next
        return length

    def swap_nodes(self, key_1, key_2):
        if key_1 == key_2:
            return

        current_node_1 = self.head
        previous_node_1 = None
        while current_node_1 and current_node_1.data != key_1:
            previous_node_1 = current_node_1
            current_node_1 = current_node_1.next

        current_node_2 = self.head
        previous_node_2 = None
        while current_node_2 and current_node_2.data != key_2:
            previous_node_2 = current_node_2
            current_node_2 = current_node_2.next

        if not current_node_1 or not current_node_2:
            return

        if previous_node_1:
            previous_node_1.next = current_node_2
        else:
            self.head = current_node_2

        if previous_node_2:
            previous_node_2.next = current_node_1
        else:
            self.head = current_node_1

        current_node_1.next, current_node_2.next = current_node_2.next, current_node_1.next

    def reverse(self):
        current_node = self.head
        previous_node = None
        while current_node:
            next = current_node.next
            current_node.next = previous_node
            previous_node = current_node
            current_node = next
        self.head = previous_node

    def print_list(self):
        current_node = self.head
        while current_node:
            print(current_node.data)
            current_node = current_node.next

Next Up⏭️: Circular linked list