Linear Data Structures and Their Types

[Data|Next] -> [Data|Next] -> [Data|NULL]

```

**Doubly Linked List**:
Each node has pointers to both next and previous nodes.
- Bidirectional traversal possible

```

NULL ← [Prev|Data|Next] ↔ [Prev|Data|Next] ↔ [Prev|Data|NULL]

```

**Circular Linked List**:
- Last node points back to the first node
- Forms a circular chain

```

[Data|Next] -> [Data|Next] -> [Data|Next] -|
^ |
|******************\_\_\_******************|

````Honestly, this took me forever to get.

#### **Operations**
**Access**: O(n) - Sequential traversal required.
**Search**: O(n) - Linear search.
- **Insertion**: O(1) - If position known, O(n) - If search required
- **Deletion**: O(1) - If node reference available, O(n) - If search required

#### **Advantages**
Dynamic size.
- Efficient insertion/deletion
Memory allocated as needed.
- No memory waste

#### **Disadvantages**
No random access.
- Extra memory for pointers
- Not cache-friendly
Sequential access only.

#### **Applications**
Implementation of stacks and queues.
- Music playlist (circular linked list)
- Undo functionality in applications
- Memory management

### **3. Stacks**

**Definition**: A linear data structure that follows Last In First Out (LIFO) principle.

#### **Characteristics**
**LIFO**: Last element inserted is first to be removed.
**Top pointer**: Points to the most recently added element.
- **Two main operations**: Push (insert) and Pop (remove) This made me feel confident.

#### **Stack Operations**

**Push**: Add element to top
- Check if stack is full (overflow condition)
- If not full, increment top pointer and add new element
- Time complexity: O(1)

**Pop**: Remove element from top
- Check if stack is empty (underflow condition)
- If not empty, return top element and decrement top pointer
- Time complexity: O(1)

**Peek/Top**: View top element without removing
- Check if stack is empty
- If not empty, return top element without modifying the stack
- Time complexity: O(1)

#### **Implementation Methods**

- **Array-based**: Fixed size, simple implementation
  **Linked list-based**: Dynamic size, more memory overhead. Don't overthink this one.

#### **Applications**

- **Function calls**: Call stack in programming
  **Expression evaluation**: Infix to postfix conversion.
- **Undo operations**: Text editors, browsers
  **Backtracking**: Maze solving, game algorithms.
- **Memory management**: Stack frame allocation

#### **Example: Balanced Parentheses**

**Algorithm for checking balanced parentheses:**
1. Scan the expression from left to right
2. If opening bracket found, push to stack
3. If closing bracket found:
   - Check if stack is empty (unbalanced)
   - Pop from stack and verify if it matches the closing bracket
4. After scanning, stack should be empty for balanced expression

**Example:** For expression "({[]})", the algorithm pushes opening brackets and matches each closing bracket with the most recent opening bracket.

### **4. Queues**

**Definition**: A linear data structure that follows First In First Out (FIFO) principle.

#### **Characteristics**

- **FIFO**: First element inserted is first to be removed
  **Front pointer**: Points to the first element.
  **Rear pointer**: Points to the last element.
- **Two main operations**: Enqueue (insert) and Dequeue (remove)

#### **Queue Operations**

**Enqueue**: Add element to rear
- Check if queue is full (overflow condition)
- If queue is empty, initialize front pointer
- Increment rear pointer and add new element
- Time complexity: O(1)

**Dequeue**: Remove element from front
- Check if queue is empty (underflow condition)
- If not empty, return front element and increment front pointer
- Time complexity: O(1)

#### **Types of Queues**

**Simple Queue**: Basic FIFO queue

**Circular Queue**:

- Rear connects back to front when it reaches end
- Efficient memory utilization
  Avoids false overflow.

**Priority Queue**:
Elements have priorities.

- Higher priority elements dequeued first
- Can be implemented using heaps

**Double-ended Queue (Deque)**:
Insertion and deletion at both ends.

- Combines stack and queue functionality Honestly, this took me forever to get.

But here's where it gets interesting. #### **Applications**
**CPU scheduling**: Process scheduling in OS.

- **Breadth-First Search**: Graph traversal algorithm
  **Print queue**: Managing print jobs.
- **Buffer**: Keyboard buffer, I/O buffers
- **Simulation**: Modeling real-world queues

## **Comparison of Linear Data Structures**

| Structure   | Access | Search | Insert | Delete | Memory         | Use Case             |
| ----------- | ------ | ------ | ------ | ------ | -------------- | -------------------- |
| Array       | O(1)   | O(n)   | O(n)   | O(n)   | Contiguous     | Random access needed |
| Linked List | O(n)   | O(n)   | O(1)   | O(1)   | Non-contiguous | Dynamic size needed  |
| Stack       | O(1)   | O(n)   | O(1)   | O(1)   | Varies         | LIFO operations      |
| Queue       | O(1)   | O(n)   | O(1)   | O(1)   | Varies         | FIFO operations      |

## **Choosing the Right Data Structure**

### **Use Arrays when**:

Need random access to elements.
Memory is limited.

- Performing mathematical operations
- Size is known and fixed

### **Use Linked Lists when**:

- Size varies frequently
  Frequent insertions/deletions.
  Don't need random access.
- Memory isn't a constraint

### **Use Stacks when**:

- Need LIFO behavior
  Implementing recursion.
- Undo/redo operations
  Expression evaluation. I almost got this wrong in my exam.

### **Use Queues when**:

- Need FIFO behavior
  Scheduling algorithms.

I finally understood this during revision week.

- Breadth-first traversal
- Buffer implementation

## **My Preparation Strategy**

**Remember access patterns**: Array (random), Linked List (sequential), Stack (LIFO), Queue (FIFO).
**Time complexities**: Arrays fast for access, Linked Lists fast for insertion/deletion.

- **Memory layout**: Arrays contiguous, Linked Lists scattered
- **Applications**: Connect each structure to real-world examples

### **What They Actually Ask in Exams**

During my exam prep, I noticed these questions keep showing up:

My teacher explained this three times before I got it.

1. So, **"what is the main difference between arrays and linked lists?"**

   - answer: arrays provide random access with contiguous memory; linked lists provide dynamic size with non-contiguous memory
   - _tip: focus on access pattern and memory layout_ honestly, this took me forever to get.

2. **"Which data structure follows LIFO principle?"**

   - Answer: Stack
   - _Tip: Remember LIFO = Last In First Out_

3. **"What are the time complexities for insertion in arrays vs linked lists?"**
   actually, - Answer: Array O(n), Linked List O(1) if position known

   - _Tip: Arrays need shifting, linked lists just pointer manipulation_ This was my weak point during prep.

4. **"Give two applications each of stacks and queues"**

   - Answer: Stack - function calls, undo operations; Queue - CPU scheduling, BFS
   - _Tip: Connect to real-world examples_

5. Well, **"what is a circular queue and why is it useful?"**
   - answer: queue where rear connects to front; prevents false overflow and efficient memory use
   - _tip: emphasize the memory efficiency aspect_

**pro tip from my experience**: when studying linear data structures, always think about the trade-offs. Each structure optimizes for different operations - arrays for access speed, linked lists for modification flexibility, stacks for LIFO operations, and queues for FIFO operations. Here's the thing - understanding these trade-offs helps you choose the right structure for different problems.