Arrays, Linked Lists, Stacks: Operations, Analysis & Real-World Use

Arrays: Static vs Dynamic Storage

Definition and Structure

An array is a contiguous memory block storing elements of the same type. Indexing starts at 0 in most languages (e.g., C, Java). Arrays are static (fixed size) or dynamic (resizable, e.g., Python lists).

0   1   2   3   4
|---|---|---|---|---|
| A | B | C | D | E |

• Static Array: Size fixed at declaration (e.g., int arr[5] in C).
• Dynamic Array: Resizes automatically (e.g., Python list.append()).

Operations and Complexity

Worked Example: Insertion in Static Array

Task: Insert X at index 2 in [A, B, C, D] (size = 4). Steps:

1. Shift elements from index 2 to 3 right by 1.
2. Insert X at index 2. State After Each Step:

Step 1: [A, B, C, D] → [A, B, C, D, _] (resize if full)
Step 2: [A, B, D, D, _] (shift C→3, D→4)
Step 3: [A, B, X, D, _] (insert X)

Code (C):

void insertAt(int arr[], int size, int index, int value) {
    for (int i = size; i > index; i--) arr[i] = arr[i-1];
    arr[index] = value;
}

Trace Table:

---

Linked Lists: Dynamic Alternatives

Singly vs Doubly Linked Lists

• Singly Linked List (SLL): Each node has data + next pointer.

Node → | Data | Next → Node → | Data | Next → NULL

• Doubly Linked List (DLL): Adds prev pointer for bidirectional traversal.

Node ←→ | Data | Next → Node ←→ | Data | Next → NULL

Operations and Complexity

*Assumes tail pointer is maintained.

Worked Example: Insertion at Head (SLL)

Task: Insert X at head of A → B → C. Steps:

1. Create new node with data = X, next = NULL.
2. Point new node’s next to current head (A).
3. Update head to new node. State After Each Step:

Step 1: New Node (X) → NULL
Step 2: X → A → B → C
Step 3: Head = X → A → B → C

Code (Python):

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

def insertAtHead(head, data):
    new_node = Node(data)
    new_node.next = head
    return new_node

Trace Table:

---

Stacks: LIFO Discipline

Definition and Use Cases

A stack follows Last-In-First-Out (LIFO). Operations:

• push: Add to top (O(1)).
• pop: Remove from top (O(1)).
• peek: View top element (O(1)).

Real-World Analogy:

• Undo/Redo in eSewa: Each action (e.g., fund transfer) is pushed to a stack. Ctrl+Z pops the last action.
• Call Stack in Programming: Function calls are stacked; the last called function returns first.

Implementation: Array vs Linked List

Worked Example: Expression Evaluation (Postfix)

Task: Evaluate 3 4 2 * 1 5 - / + (postfix notation). Steps:

1. Push 3, 4, 2.
2. Encounter *: Pop 2 and 4, compute 4*2=8, push 8.
3. Push 1, 5.
4. Encounter -: Pop 5 and 1, compute 1-5=-4, push -4.
5. Encounter /: Pop -4 and 8, compute 8/-4=-2, push -2.
6. Final result: -2.

State After Each Step:

Step 1: [3, 4, 2]
Step 2: [3, 8] (after 4*2)
Step 3: [3, 8, 1, 5]
Step 4: [3, 8, -4] (after 1-5)
Step 5: [-2] (after 8/-4)

Code (Python):

def evaluatePostfix(expression):
    stack = []
    for token in expression.split():
        if token.isdigit():
            stack.append(int(token))
        else:
            b = stack.pop()
            a = stack.pop()
            if token == '+': stack.append(a + b)
            elif token == '-': stack.append(a - b)
            elif token == '*': stack.append(a * b)
            elif token == '/': stack.append(a / b)
    return stack.pop()

Trace Table:

---

In the Real World

1. Daraz Order Queue (Priority Queue + Stack)

   • Idea Used: Stacks manage order history (LIFO for "Recently Viewed" or "Last Ordered").
   • How: When a user views products, each item is pushed onto a stack. The most recent item is always at the top, enabling quick access for "Undo View" or recommendations.
   • Example: If a user views Shirt → Pants → Shoes, the stack holds [Shirt, Pants, Shoes]. Popping once shows Shoes as the last viewed.

2. eSewa Transaction Logs (Stack for Undo)

   • Idea Used: Stacks implement undo operations for transactions.
   • How: Each transaction (e.g., bill payment) is pushed onto a stack. Users can pop() to reverse the last action. For example:
     • Push: Payment of Rs. 500 to NTC.
     • Pop: Reverts the payment and releases funds.
   • Trace:

     Step 1: [] → [Payment1]
     Step 2: [Payment1] → [Payment1, Payment2]
     Step 3: Pop → [Payment1] (undo Payment2)
     

3. Pathao Driver Assignment (Queue)

   • Idea Used: Queues manage driver availability (FIFO for ride requests).
   • How: When a ride is requested, Pathao’s system assigns the oldest available driver (front of the queue) to minimize wait time. Drivers join the queue when they become free.
   • Example: Queue state after 3 drivers sign in:

     [Driver1, Driver2, Driver3]
     

     • First request → Driver1 is assigned (dequeued).
     • New driver Driver4 joins → [Driver2, Driver3, Driver4].

4. Bank Loan Amortization (Stack for Interest Calculation)

   • Idea Used: Stacks model loan repayment schedules (LIFO for interest vs principal).
   • How: Each monthly payment is split into interest (top of stack) and principal (remaining stack). The bank pops the interest first, then the principal.
   • Example: Loan of Rs. 10,000 at 10% annual interest (Rs. 83.33/month interest for 1st year).
     • Stack after 1st payment:

       [Principal: 9,916.67]
       [Interest: 83.33] ← Popped first
       

     • Total payment = Rs. 100 (Rs. 83.33 interest + Rs. 16.67 principal).

---

Comparison Table: Arrays vs Linked Lists vs Stacks

---

Exam Tip

1. Diagrams Are Mandatory:

   • For arrays/linked lists, always draw the before/after state of operations (insert/delete).
   • For stacks, show the stack’s state after each push/pop in postfix evaluation or recursion.

2. Time Complexity Questions:

   • Memorize the O(1) vs O(n) rules for arrays/linked lists/stacks.
   • Example Question: "What is the time complexity of inserting an element at the end of a singly linked list if the tail pointer is not maintained?" Answer: O(n) (must traverse from head to find the tail).

3. Code Traces:

   • Examiners often ask to trace code step-by-step. Use tables like the ones above to show variable changes.
   • Example:

     def reverseStack(stack):
         if not stack: return
         top = stack.pop()
         reverseStack(stack)
         insertAtBottom(stack, top)
     

     Trace for reverseStack([1, 2, 3]):

     Call Stack	Stack State
     reverseStack([1,2,3])	[1,2] (pop 3)
     reverseStack([1,2])	[1] (pop 2)
     reverseStack([1])	[] (pop 1)
     insertAtBottom([],1)	[1]
     insertAtBottom([1],2)	[2,1]
     insertAtBottom([2,1],3)	[3,2,1]

4. Real-World Applications:

   • 1 mark is often given for linking concepts to Nepalese software (e.g., Daraz queues, eSewa stacks).
   • Example Answer: "A stack is used in eSewa’s undo feature because it follows LIFO, ensuring the most recent transaction is reversed first. This matches the user’s expectation of undoing the last action."

5. Common Pitfalls:

   • Off-by-one errors in array indexing (remember arr[0] is the first element).
   • Forgetting to update pointers in linked lists (e.g., not setting new_node.next).
   • Stack overflow: Mention this in questions about recursion depth (e.g., "What happens if the stack size exceeds the call stack limit?").

---

Practice Questions (Exam-Style)

1. Short Answer:

   • Draw the state of a doubly linked list after inserting 5 between 3 and 7 in 1 → 3 → 7 → 9.
   • What is the time complexity of searching for an element in an unsorted array? Justify.

2. Code Trace:

   • Given the following C code, trace the stack operations for push(1); push(2); pop(); push(3);.

     void push(int x) { stack[top++] = x; }
     int pop() { return stack[--top]; }
     

   • Show the stack state after each operation.

3. Application:

   • How would you use a queue to manage customer service tickets in a bank like Nabil Bank? Draw the queue state after 3 customers arrive and 1 is served.

4. Algorithm Design:

   • Write a Python function to reverse a singly linked list using a stack. Include a trace table for the list A → B → C.