Linked Lists, Stacks and Queues

7.1Linked Lists

• Its size is dynamic.
• It does not require contiguous memory locations.
• Types include singly, doubly, and circular linked lists.

7.2Node Structure

Each node has two parts:

• Data — the value stored in the node.
• Pointer — a reference to the next node.

7.3Singly Linked List

A singly linked list can be traversed in one direction. The head points to the first node, and the last node’s next pointer is None.

7.4Insertion at the Front

1. Create a new node.
2. Point its next to the current head.
3. Update the head to the new node.

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

7.5Insertion in the Middle

1. Traverse to the node just before the desired position.
2. Point the new node’s next to the current node’s next.
3. Point the current node’s next to the new node.

def insert_middle(self, position, data):
    if position < 0:
        print("Invalid position.")
        return

    new_node = Node(data)
    if position == 0:
        new_node.next = self.head
        self.head = new_node
        return

    temp = self.head
    for _ in range(position - 1):
        if temp is None:
            print("Position out of bounds.")
            return
        temp = temp.next

    if temp is None:
        print("Position out of bounds.")
        return

    new_node.next = temp.next
    temp.next = new_node

7.6Insertion at the End

1. Traverse to the last node.
2. Update the last node’s next to the new node.

while last.next:
    last = last.next
last.next = new_node

7.7Insertion in a Singly Linked List

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


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

    def insert_at_end(self, data):
        new_node = Node(data)

        # If list is empty
        if self.head is None:
            self.head = new_node
            return

        # Traverse till the last node
        current = self.head
        while current.next is not None:
            current = current.next

        # Insert at the end
        current.next = new_node

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


if __name__ == "__main__":
    ll = LinkedList()
    ll.insert_at_end(10)
    ll.insert_at_end(20)
    ll.insert_at_end(30)
    ll.insert_at_end(40)
    ll.traverse()

7.8Deletion in a Singly Linked List

def delete_front(self):
    if self.head is None:
        return
    self.head = self.head.next

def delete_key(self, key):
    if self.head is None:
        return False
    if self.head.data == key:
        self.head = self.head.next
        return True

    temp = self.head
    while temp.next and temp.next.data != key:
        temp = temp.next
    if temp.next is None:
        return False
    temp.next = temp.next.next
    return True

def delete_end(self):
    if self.head is None:
        return
    if self.head.next is None:
        self.head = None
        return

    temp = self.head
    while temp.next.next:
        temp = temp.next
    temp.next = None

7.9Doubly and Circular Linked Lists

Doubly linked list

• Each node contains data, a next pointer, and a previous pointer.
• It allows traversal in both directions.
• The first node’s previous pointer is None, and the last node’s next pointer is None.

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

Circular linked list

• It is similar to a singly linked list, but the last node’s next points back to the head.
• There are no None values in the list.
• It can be singly or doubly circular.

7.10Advantages, Disadvantages and Exercises

7.11Stack Data Structure

Elements are added and removed from the same end, called the top.

7.12Stack Operations

• Push — add an element to the top of the stack.
• Pop — remove and return the top element of the stack.
• Peek — view the top element without removing it.
• IsEmpty — check whether the stack is empty.
• IsFull — check whether the stack is full for a fixed-size stack or array implementation.

7.13Stack Operations: Algorithms

if S.top == S.size
    error(overflow)
else S.top = S.top + 1
    S[S.top] = x

if STACK-EMPTY(S)
    error(underflow)
else S.top = S.top - 1
    return S[S.top + 1]

if S.top == 0
    return TRUE
else return FALSE

7.14Queue Data Structure

• Elements are added and removed from both ends.
• Elements are added at the rear (tail).
• Elements are removed from the front (head).

7.15Queue Operations

• Enqueue — add an element at the rear.
• Dequeue — remove an element from the front.
• Peek/Front — retrieve the front element without removing it.
• IsEmpty — check whether the queue is empty.
• IsFull — check whether the queue is full for an array implementation.

7.16Circular Queue Operations

In a circular queue, location 1 immediately follows location n: the queue wraps around.

7.17Queue Applications and Abstract Data Types

Applications of queues

• CPU scheduling and disk scheduling.
• Buffer management.
• Handling packets in routers.
• Ticketing queues.

Abstract Data Types