Mastering Data Structures and Algorithms in Python: A Complete Guide (Part 2)

Part 2: Linear Data Structures - Linked Lists, Stacks, and Queues

Linked Lists

Linked lists are fundamental linear data structures where each element is a separate object called a node. Nodes are connected together using pointers.

Singly Linked Lists

In a singly linked list, each node contains data and a reference (link) to the next node in the sequence:

<!-- Example: Singly Linked List in Python -->
<h3>Example: Singly Linked List in Python</h3>

<p>Python implementation of a singly linked list:</p>

<pre><code>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
        last = self.head
        while last.next:
            last = last.next
        last.next = new_node

    def print_list(self):
        current = self.head
        while current:
            print(current.data, end=' ')
            current = current.next

# Example usage
linked_list = LinkedList()
linked_list.append(1)
linked_list.append(2)
linked_list.append(3)
linked_list.print_list()  # Output: 1 2 3
</code></pre>

Doubly Linked Lists

In a doubly linked list, each node contains data and references (links) to both the next and previous nodes:

<!-- Example: Doubly Linked List in Python -->
<h3>Example: Doubly Linked List in Python</h3>

<p>Python implementation of a doubly linked list:</p>

<pre><code>class Node:
    def __init__(self, data):
        self.data = data
        self.prev = None
        self.next = None

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

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

    def print_list(self):
        current = self.head
        while current:
            print(current.data, end=' ')
            current = current.next

# Example usage
doubly_linked_list = DoublyLinkedList()
doubly_linked_list.append(1)
doubly_linked_list.append(2)
doubly_linked_list.append(3)
doubly_linked_list.print_list()  # Output: 1 2 3
</code></pre>

Circular Linked Lists

A circular linked list is a variation of linked lists where the last node points back to the first node:

<!-- Example: Circular Linked List in Python -->
<h3>Example: Circular Linked List in Python</h3>

<p>Python implementation of a circular linked list:</p>

<pre><code>class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

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

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

    def print_list(self):
        if self.head is None:
            return
        temp = self.head
        while True:
            print(temp.data, end=' ')
            temp = temp.next
            if temp == self.head:
                break

# Example usage
circular_linked_list = CircularLinkedList()
circular_linked_list.append(1)
circular_linked_list.append(2)
circular_linked_list.append(3)
circular_linked_list.print_list()  # Output: 1 2 3  (circular)
</code></pre>

Implementation and Operations

Operations on linked lists include insertion, deletion, traversal, and searching, all of which are essential for understanding and implementing linked list algorithms.

Stacks

Introduction to Stacks

A stack is a linear data structure that follows the Last In, First Out (LIFO) principle. Elements are added and removed from the top of the stack.

<!-- Example: Stack Implementation using List in Python -->
<h3>Example: Stack Implementation using List in Python</h3>

<p>Python implementation of a stack using lists:</p>

<pre><code># Stack implementation using lists
stack = []

# Push operation
stack.append(1)
stack.append(2)
stack.append(3)

# Pop operation
print(stack.pop())  # Output: 3
print(stack.pop())  # Output: 2
print(stack.pop())  # Output: 1
</code></pre>

Implementing Stacks using Arrays and Linked Lists

Stacks can be implemented using arrays (lists) or linked lists, with each approach having its advantages based on specific requirements and performance considerations.

Applications of Stacks in Algorithmic Problems

Stacks are used in various algorithmic problems such as expression evaluation, backtracking, and parsing, demonstrating their versatility and practical utility.

Queues

Introduction to Queues

A queue is a linear data structure that follows the First In, First Out (FIFO) principle. Elements are added at the rear (enqueue) and removed from the front (dequeue) of the queue.

<!-- Example: Queue Implementation using Collections.deque in Python -->
<h3>Example: Queue Implementation using Collections.deque in Python</h3>

<p>Python implementation of a queue using collections.deque:</p>

<pre><code>from collections import deque

# Queue implementation using deque
queue = deque()

# Enqueue operation
queue.append(1)
queue.append(2)
queue.append(3)

# Dequeue operation
print(queue.popleft())  # Output: 1
print(queue.popleft())  # Output: 2
print(queue.popleft())  # Output: 3
</code></pre>

Implementing Queues using Arrays and Linked Lists

Similar to stacks, queues can be implemented using arrays (lists) or linked lists, with each implementation offering specific advantages depending on usage scenarios.

Types of Queues: FIFO, Priority Queues

FIFO queues prioritize elements based on their arrival order, while priority queues prioritize elements based on their assigned priority levels, enabling efficient management of tasks and data processing.

Conclusion

Understanding linear data structures like linked lists, stacks, and queues is essential for building foundational knowledge in Data Structures and Algorithms. These structures form the backbone of many algorithmic solutions and are crucial for efficient data management and manipulation.