Lists: Singly and Doubly Linked Lists

5.1 Definition of a List and Its Types

List — is a dynamic data structure consisting of elements (nodes), where each node contains data and links to other nodes. Unlike arrays, lists can change their size during program execution.

Important! Here we're not talking about the list class in Python, we're discussing the data structure from algorithm theory.

List types:

• Singly Linked List: Each node contains data and a link to the next node.
• Doubly Linked List: Each node contains data, a link to the next node, and a link to the previous node.

5.2 How Singly Linked Lists Work

Structure of a singly linked list:

• Node: Consists of two parts: data and a link to the next node.
• Head: A pointer to the first node of the list.

How it works:

• Adding a node: Happens by creating a new node and updating the link of the last node to the new node.
• Removing a node: Requires updating the link of the previous node to the next node of the node being removed.

Example implementation:

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

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

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

    def display(self):
        current = self.head
        while current:
            print(current.data, end=" -> ")
            current = current.next
        print("None")

# Example usage:
sll = SinglyLinkedList()
sll.append(1)
sll.append(2)
sll.append(3)
sll.display()  # Output: 1 -> 2 -> 3 -> None

5.3 How Doubly Linked Lists Work

Structure of a doubly linked list:

• Node: Consists of three parts: data, a link to the next node, and a link to the previous node.
• Head: A pointer to the first node of the list.
• Tail: A pointer to the last node of the list (not mandatory, but often used).

How it works:

• Adding a node: Happens by creating a new node and updating the links of the last node and the new node.
• Removing a node: Requires updating the links of the previous and next nodes of the node being removed.

Example implementation:

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

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

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

    def display(self):
        current = self.head
        while current:
            print(current.data, end=" <-> ")
            current = current.next
        print("None")

# Example usage:
dll = DoublyLinkedList()
dll.append(1)
dll.append(2)
dll.append(3)
dll.display()  # Output: 1 <-> 2 <-> 3 <-> None

5.4 Basic Operations

Basic operations: insertion, deletion, search

Insertion:

• Singly Linked List: Inserting a new node at the end of the list requires traversing all nodes to the last one and updating the link of the last node.
• Doubly Linked List: Inserting a new node at the end of the list is similar to the singly linked list, but also requires updating the prev link of the new node to the previous node.

Deletion:

• Singly Linked List: Deleting a node requires traversing the list to the node that needs to be deleted and updating the link of the previous node to the next node of the node being removed.
• Doubly Linked List: Deleting a node requires updating the next and prev links of the neighboring nodes of the node being removed.

Search: Traversing the list from head to tail and comparing each node's data with the desired value. Time complexity — O(n).

5.5 Example Use of Lists

Let's implement a stack using a singly linked list as an example.

A stack can be easily implemented using a singly linked list with push and pop methods for adding and removing elements. It should have 2 methods:

• push — adding a new element to the end of the list
• pop — removing the last element from the end of the list

Example implementation:

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

class Stack:
    def __init__(self):
        self.top = None

    def push(self, data):
        new_node = Node(data)
        new_node.next = self.top
        self.top = new_node

    def pop(self):
        if not self.top:
            return None
        data = self.top.data
        self.top = self.top.next
        return data

    def display(self):
        current = self.top
        while current:
            print(current.data, end=" -> ")
            current = current.next
        print("None")

# Example usage:
stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
stack.display()  # Output: 3 -> 2 -> 1 -> None
print(stack.pop())  # Output: 3
stack.display()  # Output: 2 -> 1 -> None

2

Task

Python SELF EN, level 51, lesson 4

Locked

Singly Linked List

Singly Linked List

Open

2

Task

Python SELF EN, level 51, lesson 4

Locked

Doubly Linked List

Doubly Linked List

Open