Introduction to Data Structures

TL;DR

Data structures organize and store data efficiently. Common types include stacks, queues, and linked lists. Understanding these will help you manage and manipulate data more effectively.

1. The Mental Model

Data structures are ways to arrange data so you can access and use it easily. Think of them as tools that help you manage data's complexity. Using the right data structure makes programming and data handling simpler.

2. The Core Material

What are Data Structures?

Photo by Pixabay on Pexels

Data structures are specialized formats for organizing, processing, and storing data. They enable efficient data retrieval and modification.

Stacks

A stack follows a Last In, First Out (LIFO) principle. Imagine it like a stack of plates; the last plate you add is the first one you take off.

Basic Operations:
- Push: Add an item to the top of the stack.
- Pop: Remove the item from the top of the stack.
- Peek: View the item on top without removing it.

Code Example:

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

    def push(self, item):
        self.items.append(item)

    def pop(self):
        return self.items.pop() if not self.is_empty() else None

    def peek(self):
        return self.items[-1] if not self.is_empty() else None

    def is_empty(self):
        return len(self.items) == 0

# Example usage
stack = Stack()
stack.push(1)
stack.push(2)
print(stack.pop())  # Output: 2

Queues

A queue follows a First In, First Out (FIFO) principle. You can think of it like a line of people waiting for coffee.

Basic Operations:
- Enqueue: Add an item to the back of the queue.
- Dequeue: Remove the item from the front of the queue.
- Front: View the item at the front without removing it.

Code Example:

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

    def enqueue(self, item):
        self.items.append(item)

    def dequeue(self):
        return self.items.pop(0) if not self.is_empty() else None

    def front(self):
        return self.items[0] if not self.is_empty() else None

    def is_empty(self):
        return len(self.items) == 0

# Example usage
queue = Queue()
queue.enqueue(1)
queue.enqueue(2)
print(queue.dequeue())  # Output: 1

Linked Lists

Photo by Jan van der Wolf on Pexels

A linked list is a collection of nodes where each node contains data and a reference to the next node. It's like a chain where each link points to the next.

Basic Operations:
- Insert: Add a node to the list.
- Delete: Remove a node from the list.
- Traverse: Access each node in the list.

Code Example:

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 not self.head:
            self.head = new_node
            return
        last_node = self.head
        while last_node.next:
            last_node = last_node.next
        last_node.next = new_node

    def display(self):
        current_node = self.head
        while current_node:
            print(current_node.data, end=" -> ")
            current_node = current_node.next
        print("None")

# Example usage
linked_list = LinkedList()
linked_list.append(1)
linked_list.append(2)
linked_list.display()  # Output: 1 -> 2 -> None

Mermaid Diagram:

graph TD;
    A["Data Structures"] --> B["Stacks"];
    A --> C["Queues"];
    A --> D["Linked Lists"];
    B --> E["Push"];
    B --> F["Pop"];
    C --> G["Enqueue"];
    C --> H["Dequeue"];
    D --> I["Insert"];
    D --> J["Delete"];

3. Worked Example

Let's say you want to manage a playlist of songs. You could use a stack to manage playback history, allowing you to go back to the last played song.

Code Implementation:

class PlaylistStack(Stack):
    def __init__(self, songs):
        super().__init__()
        for song in songs:
            self.push(song)

    def play_previous(self):
        return self.pop()

# Example usage
playlist = PlaylistStack(['Song A', 'Song B', 'Song C'])
print(playlist.play_previous())  # Output: 'Song C'
print(playlist.play_previous())  # Output: 'Song B'

4. Key Takeaways

• Stacks operate in a LIFO manner; queues operate in a FIFO manner.
• Linked lists consist of nodes and can be singly or doubly linked.
• Using the right data structure can optimize your code and improve performance.
• Each data structure has typical use cases based on its characteristics.

Common Mistakes to Avoid

Photo by KATRIN BOLOVTSOVA on Pexels

• Mixing up the operations of stacks and queues.
• Forgetting to check if a data structure is empty before performing operations.
• Not properly managing memory, especially with linked lists.

5. Now Try It

Create your own implementation of a queue in Python. Add methods to enqueue, dequeue, and display the queue. Aim to successfully enqueue three items, dequeue one, and then display your remaining items. Success means you'll have a fully functional queue that correctly handles these operations.

============================================================