Python Data Structures - Collections

 

Python Data Structures Beyond Basic Collections: Stack, Queue, Deque, Linked List, Searching and Sorting

Have you ever wondered how a browser remembers the pages you visited, how a printer manages multiple print requests, or how a shopping app sorts products by price?

These activities use ideas from data structures and algorithms.

In Python, you already know basic collections such as lists, tuples, sets, and dictionaries. But as programs become more advanced, you need to understand how to organize, access, search, and arrange data efficiently.

Welcome to this Python Pebbles tutorial, where we will explore six important topics for Class 9–12 students:

• Stack

• Queue

• Deque

• Linked list

• Searching algorithms

• Sorting algorithms

By the end, you will build a small Student Record Manager that uses searching and sorting.

---

1. What Is a Data Structure?

A data structure is a way of organizing and storing data so that a program can use it effectively.

Imagine your school library.

Books are not thrown randomly onto the floor. They are organized so that students and librarians can find them easily.

A computer program also needs a sensible way to organize information.

Examples:

Data Structure	Real-Life Example
Stack	A pile of plates
Queue	Students waiting in a line
Deque	A line where people can join or leave at either end
Linked list	A chain of connected links
Searching	Finding a student's roll number
Sorting	Arranging marks from lowest to highest

Python Pebble: Choosing the right way to organize data can make a program easier to understand and more efficient.

2. Stack – Last In, First Out (LIFO)

What is a Stack?

A stack is a data structure in which the last item added is the first item removed.

This rule is called LIFO — Last In, First Out.

Imagine placing three plates on top of one another.

       ┌───────────┐
       │  Plate C  │  ← Removed first
       ├───────────┤
       │  Plate B  │
       ├───────────┤
       │  Plate A  │
       └───────────┘

You normally remove Plate C first because it is on top.

Stacks are used in:

• Undo operations in text editors

• Browser history navigation

• Function calls

• Expression evaluation

• Backtracking problems

Stack Operations

Operation	Meaning
push	Add an item
pop	Remove the top item
peek	View the top item without removing it
is_empty	Check whether the stack is empty

Python lists can implement a simple stack.

Example 1: Creating a Stack

stack = []

stack.append("Book A")
stack.append("Book B")
stack.append("Book C")

print(stack)

Output:

['Book A', 'Book B', 'Book C']

Here, append() adds an item to the top of our stack.

Example 2: Removing an Item

stack = ["Book A", "Book B", "Book C"]

removed = stack.pop()

print("Removed:", removed)
print("Stack:", stack)

Output:

Removed: Book C
Stack: ['Book A', 'Book B']

The last item added is the first item removed.

Example 3: Complete Stack Program

stack = []

stack.append(10)
stack.append(20)
stack.append(30)

print("Stack:", stack)
print("Top item:", stack[-1])

removed = stack.pop()

print("Removed:", removed)
print("Updated stack:", stack)

Output:

Stack: [10, 20, 30]
Top item: 30
Removed: 30
Updated stack: [10, 20]

Notice that stack[-1] accesses the last element without removing it.

Mini Challenge 1

Create a stack of five subject names.

1. Add five subjects.

2. Display the stack.

3. Remove two subjects.

4. Display the updated stack.

Bonus: Print the last subject without removing it.

---

3. Queue – First In, First Out (FIFO)

What Is a Queue?

A queue is a data structure in which the first item added is the first item removed.

This rule is called FIFO — First In, First Out.

Imagine students waiting at a school canteen.

Front                         Rear
  ↓                             ↓
[Riya] → [Aman] → [Neha] → [Raman]
  ↑
Served first

Riya joined the line first, so she is served first.

Queues are used in:

• Printer job management

• Customer service systems

• Task scheduling

• Network message processing

• Breadth-first search in graphs

Queue Operations

Operation	Meaning
enqueue	Add an item at the rear
dequeue	Remove an item from the front
front	View the first item
is_empty	Check whether the queue is empty

Example 1: A Simple Queue

A Python list can demonstrate a queue for small examples.

queue = []

queue.append("Riya")
queue.append("Aman")
queue.append("Neha")

print(queue)

Output:

['Riya', 'Aman', 'Neha']

To remove the first item:

served = queue.pop(0)

print("Served:", served)
print("Waiting:", queue)

Output:

Served: Riya
Waiting: ['Aman', 'Neha']

This works, but removing the first item from a large list can be inefficient because the remaining items need to shift.

Example 2: The Recommended Queue Using deque

Python provides a double-ended queue in the collections module.

from collections import deque

queue = deque()

queue.append("Riya")
queue.append("Aman")
queue.append("Neha")

print(queue)

served = queue.popleft()

print("Served:", served)
print("Waiting:", queue)

Output:

deque(['Riya', 'Aman', 'Neha'])
Served: Riya
Waiting: deque(['Aman', 'Neha'])

popleft() efficiently removes an item from the front.

Mini Challenge 2

Create a queue for a school office.

• Add three student names.

• Remove the first student after their work is completed.

• Add one more student.

• Display the queue.

Question: Why should the first student be removed rather than the last student?

---

4. Deque – Insert and Remove at Both Ends

What Is a Deque?

A deque, pronounced “deck,” stands for double-ended queue.

Unlike a standard queue, a deque allows items to be added or removed at both ends.

Imagine a line where people are allowed to enter or leave from either the front or the rear.

Python provides deque through the collections module.

from collections import deque

Important Deque Operations

Operation	Meaning
append(x)	Add x at the right end
appendleft(x)	Add x at the left end
pop()	Remove from the right end
popleft()	Remove from the left end

Example 1: Adding Items at Both Ends

from collections import deque

numbers = deque([20, 30])

numbers.append(40)
numbers.appendleft(10)

print(numbers)

Output:

deque([10, 20, 30, 40])

Example 2: Removing Items at Both Ends

from collections import deque

numbers = deque([10, 20, 30, 40])

print(numbers.pop())
print(numbers.popleft())

print(numbers)

Output:

40
10
deque([20, 30])

Where Are Deques Useful?

Deques are useful when a program needs to add and remove items at either end.

Examples include:

• Sliding-window algorithms

• Recent-item history

• Palindrome checking

• Certain scheduling algorithms

• Implementing stacks and queues

Mini Challenge 3: Palindrome Checker

A palindrome reads the same forwards and backwards.

Examples:

LEVEL
MADAM
RADAR

Try writing a program that:

1. Takes a word from the user.

2. Places its characters into a deque.

3. Compares and removes characters from both ends.

4. Reports whether the word is a palindrome.

Hint: Compare popleft() with pop() until zero or one character remains.

---

5. Linked List – An Introduction

What Is a Linked List?

A linked list is a data structure made of nodes.

Each node stores:

1. Data

2. A reference to the next node

Unlike a Python list, whose elements are stored in a sequence managed by Python, a linked list connects its nodes through references.

Imagine a treasure hunt.

Each clue contains a message and tells you where to find the next clue.

[10 | next] → [20 | next] → [30 | None]

Each box represents a node.

The final node points to None, which indicates that there is no next node.

Creating a Node in Python

We can use a class to define a node.

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

Here:

• data stores the value.

• next stores a reference to the next node.

• None means there is no next node yet.

Example 1: Connecting Three Nodes

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


first = Node(10)
second = Node(20)
third = Node(30)

first.next = second
second.next = third

print(first.data)
print(first.next.data)
print(first.next.next.data)

Output:

10
20
30

We have created three nodes and connected them.

Example 2: Traversing a Linked List

Traversing means visiting each node one by one.

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


first = Node(10)
second = Node(20)
third = Node(30)

first.next = second
second.next = third

current = first

while current is not None:
    print(current.data)
    current = current.next

Output:

10
20
30

The variable current moves from one node to the next until it reaches None.

A Simple Linked List Class

Let's make our code reusable.

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

        current = self.head

        while current.next is not None:
            current = current.next

        current.next = new_node

    def display(self):
        current = self.head

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

        print("None")


numbers = LinkedList()

numbers.append(10)
numbers.append(20)
numbers.append(30)

numbers.display()

Output:

10 -> 20 -> 30 -> None

Linked List vs Python List

Feature	Python List	Singly Linked List
Access by index	Fast, typically O(1)	Requires traversal, O(n)
Add at beginning	Typically O(n)	O(1) if the head is updated
Add at end	Usually amortized O(1) with append()	O(n) in our implementation without a tail reference
Memory layout	Managed sequence of references	Nodes connected by references
Built into Python	Yes	Usually implemented manually for learning

Python Pebble: Linked lists are excellent for learning how nodes and references work. For everyday Python programming, built-in lists are often the simpler choice.

Mini Challenge 4

Extend the linked list program to:

1. Add the numbers 5, 15, 25, and 35.

2. Display all nodes.

3. Count how many nodes exist.

Bonus: Write a method that searches for a particular value.

---

6. Searching Algorithms

What Is Searching?

Searching means finding whether a particular item exists in a collection and, if needed, identifying its position.

Imagine looking for your name in a class register.

A computer can use different searching algorithms depending on how the data is organized.

We will learn:

• Linear search

• Binary search

6.1 Linear Search

Linear search checks each element one by one until the target is found or the collection ends.

It works on both sorted and unsorted collections.

Example

numbers = [15, 8, 23, 42, 16]

target = 42
found = False

for i in range(len(numbers)):
    if numbers[i] == target:
        print("Found at index:", i)
        found = True
        break

if not found:
    print("Not found")

Output:

Found at index: 3

Remember that Python indexes start at zero.

The first element is at index 0, the second at index 1, and so on.

Linear Search as a Function

def linear_search(items, target):
    for index, item in enumerate(items):
        if item == target:
            return index

    return -1


numbers = [15, 8, 23, 42, 16]

print(linear_search(numbers, 42))
print(linear_search(numbers, 100))

Output:

3
-1

Here, -1 means that the target was not found.

Time Complexity

In the worst case, linear search may inspect every element.

Its time complexity is O(n), where n is the number of elements.

---

6.2 Binary Search

Binary search is a faster searching method, but there is one important condition:

The data must be sorted.

Imagine finding a word in a dictionary. Instead of reading every word, you open near the middle and decide which half to search.

Binary search follows the same idea.

Example

Sorted list:

[10, 20, 30, 40, 50, 60, 70]

Suppose we want to find 60.

1. Check the middle element: 40.

2. Since 60 is greater than 40, ignore the left half.

3. Check the middle of the remaining section: 60.

4. The target is found.

Python Program

def binary_search(items, target):
    low = 0
    high = len(items) - 1

    while low <= high:
        mid = (low + high) // 2

        if items[mid] == target:
            return mid

        elif items[mid] < target:
            low = mid + 1

        else:
            high = mid - 1

    return -1


numbers = [10, 20, 30, 40, 50, 60, 70]

print(binary_search(numbers, 60))
print(binary_search(numbers, 25))

Output:

5
-1

Time Complexity

Binary search halves the remaining search area at each step.

Its time complexity is O(log n).

For large sorted collections, this can be much faster than linear search.

Linear Search vs Binary Search

Feature	Linear Search	Binary Search
Requires sorted data	No	Yes
Method	Check items one by one	Repeatedly halve the search range
Worst-case time	O(n)	O(log n)
Best for	Small or unsorted data	Large, sorted data

Mini Challenge 5

Write a program that searches for a student's roll number in this list:

roll_numbers = [101, 105, 108, 112, 120, 125, 130]

First use linear search.

Then use binary search.

Question: Why must the list be sorted before using binary search?

---

7. Sorting Algorithms

What Is Sorting?

Sorting means arranging data in a particular order.

Examples:

• Marks from lowest to highest

• Prices from lowest to highest

• Names in alphabetical order

• Scores from highest to lowest

Python provides built-in sorting tools, but understanding sorting algorithms helps you learn how they work.

We will explore:

• Bubble sort

• Selection sort

• Insertion sort

• Python's built-in sorting

7.1 Bubble Sort

Bubble sort repeatedly compares adjacent elements and swaps them when they are in the wrong order.

Think of larger values gradually moving towards the end of the list.

Example

Original list:

[5, 3, 8, 2]

First pass:

• Compare 5 and 3: swap.

• Compare 5 and 8: no swap.

• Compare 8 and 2: swap.

The list becomes:

[3, 5, 2, 8]

After further passes, the list becomes:

[2, 3, 5, 8]

Python Program

def bubble_sort(numbers):
    numbers = numbers.copy()
    n = len(numbers)

    for i in range(n):
        swapped = False

        for j in range(0, n - i - 1):
            if numbers[j] > numbers[j + 1]:
                numbers[j], numbers[j + 1] = (
                    numbers[j + 1], numbers[j]
                )
                swapped = True

        if not swapped:
            break

    return numbers


data = [5, 3, 8, 2]

print(bubble_sort(data))

Output:

[2, 3, 5, 8]

Bubble sort has worst-case time complexity O(n²).

It is useful for learning, but it is generally not the best choice for sorting large datasets.

---

7.2 Selection Sort

Selection sort repeatedly finds the smallest remaining element and places it in the next position.

Example

Original list:

[29, 10, 14, 37, 13]

Steps:

1. Find the smallest value, 10, and place it first.

2. Find the smallest value among the remaining elements, 13.

3. Continue until the list is sorted.

Result:

[10, 13, 14, 29, 37]

Python Program

def selection_sort(numbers):
    numbers = numbers.copy()
    n = len(numbers)

    for i in range(n):
        min_index = i

        for j in range(i + 1, n):
            if numbers[j] < numbers[min_index]:
                min_index = j

        numbers[i], numbers[min_index] = (
            numbers[min_index], numbers[i]
        )

    return numbers


data = [29, 10, 14, 37, 13]

print(selection_sort(data))

Output:

[10, 13, 14, 29, 37]

Selection sort has worst-case time complexity O(n²).

---

7.3 Insertion Sort

Insertion sort builds a sorted section one element at a time.

Imagine arranging playing cards in your hand. You pick up a card and insert it into the correct position among the cards already arranged.

Example

Original list:

[5, 2, 4, 1]

The list is gradually arranged until it becomes:

[1, 2, 4, 5]

Python Program

def insertion_sort(numbers):
    numbers = numbers.copy()

    for i in range(1, len(numbers)):
        key = numbers[i]
        j = i - 1

        while j >= 0 and numbers[j] > key:
            numbers[j + 1] = numbers[j]
            j -= 1

        numbers[j + 1] = key

    return numbers


data = [5, 2, 4, 1]

print(insertion_sort(data))

Output:

[1, 2, 4, 5]

Insertion sort has worst-case time complexity O(n²). It can perform well on small or nearly sorted lists.

---

7.4 Python's Built-in Sorting

In real projects, Python's built-in sorting is usually the best starting point.

Using sort()

marks = [78, 92, 65, 88, 73]

marks.sort()

print(marks)

Output:

[65, 73, 78, 88, 92]

sort() changes the original list.

Using sorted()

marks = [78, 92, 65, 88, 73]

result = sorted(marks)

print("Original:", marks)
print("Sorted:", result)

Output:

Original: [78, 92, 65, 88, 73]
Sorted: [65, 73, 78, 88, 92]

sorted() returns a new sorted list.

Sorting in Descending Order

marks = [78, 92, 65, 88, 73]

print(sorted(marks, reverse=True))

Output:

[92, 88, 78, 73, 65]

Sorting Names Alphabetically

students = ["Riya", "Aman", "Neha", "Raman"]

print(sorted(students))

Output:

['Aman', 'Neha', 'Raman', 'Riya']

Python Pebble: Learn how algorithms work, but use Python's built-in sorting for most everyday applications.

Sorting Algorithm Comparison

Algorithm	Average/Worst-Case Time	Main Idea
Bubble sort	O(n²)	Compare adjacent elements
Selection sort	O(n²)	Select the smallest remaining element
Insertion sort	O(n²)	Insert into the sorted section
Python's built-in sort	O(n log n) worst case	Efficient, adaptive sorting

---

8. Searching and Sorting Together

Searching and sorting are often used together.

Imagine a teacher has marks for 10 students.

The teacher wants to:

1. Arrange the marks from lowest to highest.

2. Find whether a student scored 85.

3. Display the position of that score in the sorted list.

Complete Example

marks = [72, 85, 63, 91, 78, 85]

sorted_marks = sorted(marks)

print("Sorted marks:", sorted_marks)

target = 85

index = sorted_marks.index(target)

print("First occurrence of 85 is at index:", index)

Output:

Sorted marks: [63, 72, 78, 85, 85, 91]
First occurrence of 85 is at index: 3

Remember: .index() returns the first occurrence, and indexes start at zero.

If you use binary search instead, remember to provide sorted data.

---

9. Master Project – Student Record Manager

Now let's combine searching and sorting in a practical program.

Project Requirements

Create a program that:

1. Stores student names and marks.

2. Displays all students.

3. Sorts students by marks.

4. Searches for a student by name.

5. Displays the highest-scoring student.

Python Program

students = [
    {"name": "Riya", "marks": 88},
    {"name": "Aman", "marks": 76},
    {"name": "Neha", "marks": 95},
    {"name": "Raman", "marks": 82},
    {"name": "Arjun", "marks": 91}
]


def display_students(records):
    for student in records:
        print(student["name"], "-", student["marks"])


def sort_by_marks(records):
    return sorted(
        records,
        key=lambda student: student["marks"]
    )


def search_student(records, name):
    for student in records:
        if student["name"].lower() == name.lower():
            return student

    return None


print("All Students:")
display_students(students)

print("\nSorted by Marks:")
display_students(sort_by_marks(students))

name = input("\nEnter student name to search: ")
result = search_student(students, name)

if result is not None:
    print("Found:", result["name"], result["marks"])
else:
    print("Student not found")

topper = max(students, key=lambda student: student["marks"])

print("\nTopper:", topper["name"], topper["marks"])

Example output for a search for Neha:

All Students:
Riya - 88
Aman - 76
Neha - 95
Raman - 82
Arjun - 91

Sorted by Marks:
Aman - 76
Raman - 82
Riya - 88
Arjun - 91
Neha - 95

Enter student name to search: Neha
Found: Neha 95

Topper: Neha 95

Master Challenge

Extend the project by adding:

• A menu-driven interface.

• A stack to store the last few operations.

• A queue for students waiting to be processed.

• A deque to maintain a recent-history list.

• A linked list to store student records for practice.

• Linear and binary search options.

• Sorting by name or marks.

• Input validation for marks between 0 and 100.

For a more realistic application, you can keep student records in a list of dictionaries. Use a linked list as a separate exercise to understand node-based data structures.

---

10. Practice Questions

Level 1 – Concepts

1. What is a data structure?

2. What does LIFO stand for?

3. What does FIFO stand for?

4. Which data structure allows insertion and removal at both ends?

5. What information does a node in a singly linked list contain?

6. What is the difference between linear and binary search?

7. Why must data be sorted before binary search?

8. What is the purpose of sorting?

9. What does pop() do when used on a list as a stack?

10. What is the difference between sort() and sorted()?

Level 2 – Coding

11. Write a stack program that pushes five integers and pops two.

12. Create a queue using collections.deque.

13. Create a deque and add an item to each end.

14. Create three linked-list nodes and connect them.

15. Write a function for linear search.

16. Write a function for binary search on sorted data.

17. Implement bubble sort.

18. Implement selection sort.

19. Implement insertion sort.

20. Sort student records by marks using sorted().

Level 3 – Thinking Challenges

21. Which data structure would you choose for an undo feature? Explain why.

22. Which data structure would you use for a printer queue?

23. Why can binary search be faster than linear search?

24. Why is a linked list not as convenient as a Python list for accessing the element at index 100?

25. Which sorting algorithm would you choose for a small, nearly sorted list, and why?

26. How could a deque help check whether a word is a palindrome?

27. What happens when you pop from an empty list?

28. How would you avoid searching a student record list repeatedly?

29. How would you modify the Student Record Manager to sort marks in descending order?

30. Why should an algorithm's time complexity matter when working with thousands of records?

---

11. Quick Revision Table

Topic	Key Idea	Python Tool
Stack	Last In, First Out	list.append(), list.pop()
Queue	First In, First Out	collections.deque
Deque	Operations at both ends	appendleft(), popleft()
Linked list	Nodes connected by references	Classes and references
Linear search	Check items one by one	Loop
Binary search	Repeatedly halve sorted search range	Loop and indexes
Bubble sort	Compare adjacent elements	Nested loops
Selection sort	Select the smallest remaining item	Nested loops
Insertion sort	Insert into sorted section	Loop
Built-in sorting	Efficient general-purpose sorting	sort(), sorted()

---

12. Python Pebble

A good programmer knows how to store data. A great programmer also understands how to access, search, and organize it efficiently.

Stacks help manage the latest item first. Queues process items in arrival order. Deques work at both ends. Linked lists teach you how nodes connect. Searching finds information, and sorting organizes it.

Start with small examples, trace each step by hand, and then write your own programs.

Your next step: Complete the Student Record Manager, test it with different data, and experiment with the time complexity of your searching and sorting algorithms.