Linked Lists, Stacks, and Queues in Python

A linked list is a linear data structure where elements are stored in nodes and each node points to the next node.

• Singly Linked List
• Doubly Linked List
• Circular Linked List

A stack is a linear data structure that follows the Last In, First Out (LIFO) principle.

A queue is a linear data structure that follows the First In, First Out (FIFO) principle.

Using a list with .append() for push and .pop() for pop.

Using collections.deque() for efficient enqueue and dequeue.

• Insertion
• Deletion
• Traversal

• Push
• Pop
• Peek
• isEmpty

• Enqueue
• Dequeue
• Front
• isEmpty

O(1)

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

class Stack:
    def __init__(self):
        self.items = []

Check if len(stack) == 0.

Check if len(queue) == 0.

In a circular linked list, the last node points back to the first node.

A doubly linked list has two pointers, next and previous, in each node.

O(n)

queue.Queue

A Python list.

.popleft() if using deque.

Using iterative pointers or recursion.

Dynamic size and ease of insertion/deletion.

Random access is not allowed (no direct indexing).

Using Floyd’s Cycle Detection Algorithm (Tortoise and Hare approach).

A queue where each element has a priority associated with it.

Push elements onto one stack and pop from another.

O(1) in deque-based queue.

Prefer using collections.deque to avoid O(n) pop from start.

It happens when you try to push an element into a full stack (limited memory).

When you try to dequeue an element from an empty queue.

• Expression evaluation
• Syntax parsing
• Undo operations in editors

• Scheduling
• Buffer management
• Data streaming

Doubly linked list has two pointers (next and previous), singly linked list has one (next).

Can be traversed both forward and backward.

Push and pop from the head.

Enqueue at the tail and dequeue from the head.

A double-ended queue where insertion and deletion can happen at both ends.

Break at k-th node and reattach the head.

Dummy nodes that simplify edge cases like inserting at head/tail.

Copy the next node’s data into the current node and delete the next node.

Dictionary for O(1) access, doubly linked list for ordering.

Use a dummy node and iteratively merge nodes.

A data structure with multiple layers of linked lists to improve search time.

Use slow and fast pointers.

A queue that can be safely used among multiple threads (e.g., queue.Queue).

Yes, by using two queues and simulating stack behavior.

Find middle, reverse second half, compare both halves.

A linked list where nodes have pointers to child lists.

A queue implemented in a circular buffer to efficiently use storage.

Using an array with modular arithmetic for head and tail.

O(n) — because each node is visited once.

Use two pointers spaced n nodes apart.

Yes, using a static array with circular behavior.

Depends on recursion limit and memory — default recursion depth is 1000.

Use two stacks or maintain auxiliary data structures.

Use two stacks or maintain auxiliary data structures.

• Music playlists
• Image viewers
• Navigation systems

When frequent insertions/deletions are needed.

Recursively visit each level and merge nodes.

A queue with a maximum size limit.

• Browser history
• Undo-redo features
• Task scheduling