Linear Structures

🚂 The Train Station of Data: Linear Structures

Imagine you’re running a magical train station where different types of trains carry passengers in a straight line. Each train type has its own special way of loading and unloading people. Welcome to the world of Linear Data Structures!

🎯 What Are Linear Data Structures?

Think of a line of kids waiting for ice cream. Each kid stands behind another - one after one. That’s “linear” - things arranged in a straight line order.

In computers, we store data the same way - one piece after another, like beads on a string!

graph TD
    A["🔵 First"] --> B["🟢 Second"]
    B --> C["🟡 Third"]
    C --> D["🔴 Fourth"]

📦 Abstract Data Types (ADT)

What’s an ADT?

Imagine a vending machine. You press a button, and a snack comes out. You don’t need to know HOW the machine works inside - you just know WHAT it does!

Abstract Data Type = What it does, not how it works

Real Example: A List is an ADT. It says:

• ✅ Add items
• ✅ Remove items
• ✅ Find items
• ❓ How? That’s decided later!

📊 Arrays: The Numbered Lockers

The Story

Picture a row of numbered lockers at school - Locker 0, Locker 1, Locker 2… Each locker holds ONE thing, and you find it using its number!

┌─────┬─────┬─────┬─────┬─────┐
│  🍎 │  🍌 │  🍇 │  🍊 │  🍓 │
├─────┼─────┼─────┼─────┼─────┤
│  0  │  1  │  2  │  3  │  4  │
└─────┴─────┴─────┴─────┴─────┘

Key Features

Simple Code Example

# Create array of fruits
fruits = ["apple", "banana",
          "grape", "orange"]

# Get fruit at position 2
print(fruits[2])  # grape

# Change fruit at position 0
fruits[0] = "mango"

⚡ Speed

• Finding item by number: Super fast! ⚡
• Adding item at end: Fast!
• Adding item in middle: Slow 🐢 (must shift everything!)

🎈 Dynamic Arrays: The Magic Expanding Backpack

The Story

What if your backpack could grow bigger when you need more space? That’s a Dynamic Array!

Start with a small bag. When it’s full, POOF - it doubles in size automatically!

graph LR
    A["📦 Size 4"] -->|Full!| B["📦📦 Size 8"]
    B -->|Full!| C["📦📦📦📦 Size 16"]

How It Works

1. Start small (say, space for 4 items)
2. Fill it up (add 4 items)
3. Need more? Create bigger array (usually 2x)
4. Copy everything to new, bigger space
5. Continue adding!

Simple Example

# Python list = dynamic array!
backpack = []

# Keep adding - it grows!
backpack.append("book")
backpack.append("pencil")
backpack.append("snack")
backpack.append("toy")
# Still adding? No problem!
backpack.append("water")

Array vs Dynamic Array

🔤 Strings: The Letter Necklace

The Story

Imagine making a friendship bracelet with letter beads. Each bead is ONE letter, and together they spell a word!

"HELLO" =
┌───┬───┬───┬───┬───┐
│ H │ E │ L │ L │ O │
└───┴───┴───┴───┴───┘
  0   1   2   3   4

A String is just an array of characters (letters, numbers, symbols)!

Why Strings Are Special

• 📝 Store names: "Alice"
• 💬 Store messages: "Hello World!"
• 🔢 Even numbers as text: "123"

Simple Example

# Create a string
name = "HELLO"

# Get letter at position 1
print(name[1])  # E

# Count letters
print(len(name))  # 5

✂️ String Operations: Playing with Words

Common Operations

Think of string operations like word games!

1. Concatenation (Joining)

Stick two strings together like connecting train cars!

first = "Hello"
second = "World"
together = first + " " + second
# "Hello World"

2. Finding Length

Count the beads on your bracelet!

word = "Python"
print(len(word))  # 6

3. Slicing (Cutting)

Take a piece of the string!

text = "RAINBOW"
piece = text[0:4]  # "RAIN"

4. Finding

Where is this letter hiding?

word = "BANANA"
pos = word.find("N")  # 2

5. Replacing

Swap letters like trading cards!

old = "cat"
new = old.replace("c", "b")
# "bat"

Operations Summary

🔗 Linked Lists: The Paper Chain

The Story

Remember making paper chains for decorations? Each link holds onto the next one. If you want to find the 5th link, you start at the first and follow the chain!

graph LR
    A["📧 Data + →"] --> B["📧 Data + →"]
    B --> C["📧 Data + →"]
    C --> D["📧 Data + ✖"]

How It’s Different from Arrays

The Node: Building Block

Each piece of the chain is called a Node. It has:

• 📦 Data (the actual value)
• ➡️ Pointer (arrow to next node)

Node = [ Data | Next → ]

➡️ Singly Linked Lists: One-Way Street

The Story

Imagine a one-way street. Cars can only go forward! Each car knows only about the car in front of it.

graph LR
    HEAD["HEAD 🏁"] --> A["10"]
    A --> B["20"]
    B --> C["30"]
    C --> NULL["NULL ⛔"]

Parts of Singly Linked List

• HEAD: The starting point (first node)
• Nodes: Each box with data
• NULL: The end (no more nodes)

Simple Operations

Adding at Beginning (Fast! ⚡)

New node → points to old HEAD
HEAD now points to new node

Before: HEAD → [10] → [20] → NULL
After:  HEAD → [5] → [10] → [20] → NULL

Finding a Value (Walk the chain 🚶)

Start at HEAD, check each node until found!

Code Example

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

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

    def add_front(self, data):
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node

Pros and Cons

↔️ Doubly Linked Lists: Two-Way Street

The Story

Now imagine a two-way street! Each car knows about the car in front AND behind. You can go forward OR backward!

graph LR
    NULL1["NULL ⛔"] --> A
    A["10"] --> B["20"]
    B --> A
    B --> C["30"]
    C --> B
    C --> NULL2["NULL ⛔"]

The Double Node

Each node now has THREE parts:

• ⬅️ Previous pointer (who’s behind me?)
• 📦 Data (the value)
• ➡️ Next pointer (who’s ahead?)

Node = [ ← Prev | Data | Next → ]

Compared to Singly Linked

Simple Visualization

HEAD                           TAIL
 ↓                              ↓
NULL ← [A] ↔ [B] ↔ [C] ↔ [D] → NULL

Code Example

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

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

When to Use What?

🎯 Quick Comparison: All Linear Structures

*Fast most of the time, slow when resizing

🌟 Summary: Your New Friends

You’ve just met some amazing data structures:

1. 📦 Arrays - Numbered lockers, fast access
2. 🎈 Dynamic Arrays - Magic growing backpacks
3. 🔤 Strings - Letter necklaces
4. ✂️ String Ops - Word games and tricks
5. 🔗 Linked Lists - Paper chains
6. ➡️ Singly Linked - One-way streets
7. ↔️ Doubly Linked - Two-way streets

Each one is special and perfect for different jobs. Now you know when to use which train at your data station! 🚂

Remember: The best programmers don’t memorize everything - they understand WHY things work. You’re already on your way! 🚀