Stacks, Queues, and Linked Lists in Python
When preparing for python coding interviews, three of the most common data structures you'll need to know are stacks, queues and linked lists interviewers love them because they test your understanding of memory, order of operations and problem-solving.
In this post, we will:
- Explain each data structure in simple terms.
- Show how to implement them from scratch in python.
- Solve a few classic mini-problems you might see in interviews.
Let's dive in đ
đī¸ 1. Stack - LIFO (Last In, First Out)
A stack is like a stack of plates: * You push a plate on top. * You pop a plate from the top. This is called LIFO (Last In, First Out)**.
â Implementation in Python
Python lists already support append()and pop, so we can use them as stack.
class Stack:
def __init__(self):
self.items = []
def push(self, item):
self.items.append(item)
def pop(self):
if self.is_empty():
raise IndexError("Pop from empty stack")
return self.items.pop()
def peek(self):
return self.items[-1] if not self.is_empty() else None
def is_empty(self):
return len(self.items) == 0
def size(self):
return len(self.items)
stack = Stack()
stack.push(10)
stack.push(20)
stack.push(30)
print(stack.items) # [10, 20, 30]
print(stack.pop()) # 30
print(stack.items) # [10, 20]
đĨ 2. Queue - FIFO (First In, First Out)
A queue is like a line at the supermarket: * You enqueue (add) to the back. * You dequeue (remove) from the front. This is called FIFO (First In, First Out).
â
Implementation with collections.deque
Python's deque (double-ended queue) is perfect for queues - efficient at both ends.
from collections import deque
class Queue:
def __init__(self):
self.items = deque()
def enqueue(self, item):
self.items.append(item)
def dequeue(self):
if self.is_empty():
raise IndexError("Dequeue from empty queue")
return self.items.popleft()
def peek(self):
return self.items[0] if not self.is_empty() else None
def is_empty(self):
return len(self.items) == 0
def size(self):
return len(self.items)
queue = Queue()
queue.enqueue('a')
queue.enqueue('b')
queue.enqueue('c')
print(queue.items) # deque(['a', 'b', 'c'])
print(queue.dequeue()) # a
print(queue.items) # deque(['b', 'c'])
đ 3. Linked List - Nodes Connected Together
A linked list is a chain of nodes. Each node has: * Data (the value) * Next (a pointer to the next node) Unlike arrays/lists, linked lists don't need contiguous memory - inserting/removing is fast, but random access is slow.
â Implementations of 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 not self.head:
self.head = new_node
return
current = self.head
while current.next:
current = current.next
current.next = new_node
def delete(self, key):
current = self.head
if current and current.data == key:
self.head = current.next
return
prev = None
while current and current.data != key:
prev = current
current = current.next
if current:
prev.next = current.next
def display(self):
current = self.head
elements = []
while current:
elements.append(str(current.data))
current = current.next
print(" -> ".join(elements))
# Example usage:
ll = LinkedList()
ll.insert_at_end(1)
ll.insert_at_end(2)
ll.insert_at_end(3)
ll.display()
đ§ Mini interview Exercises
Here are some classic problems you can practice using theses data structures:
- Reverse a String using Stack
Push each character, then pop them to reverse the string. - Check for Balanced Parentheses
Use stack to make sure every(has a matching). - Simulate a Print Queue
Use a queue to process print jobs in order. - Reverse a Linked List
A very common interview question - try to implement it iteratively and recursively.
Wrap-Up
- Stacks follow LIFO âĄī¸ great for undo operations, backtracking and parsing.
- Queues follow FIFO âĄī¸ used in scheduling, message processing and BFS (Breadth-First Search).
- Linked lists are fundamental for memory-efficient inserts/deletes. Mastering these implementations will help you crush entry-level Python interviews and strengthen your algorithmic thinking.
đĄ Next step: Try rewriting the linked list to be doubly linked (each node has next and prev) and implement a stack using two queues - both are common interview challenges!