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

---

Core Concepts & Definitions

1. Arrays

An array is a contiguous memory allocation of fixed-size elements of the same data type. It is the simplest and most commonly used data structure.

Key Properties

• Index-based access: Elements are accessed via indices (0 to n-1).
• Fixed size: Cannot grow or shrink dynamically (unless resized manually).
• Random access: Any element can be accessed in O(1) time.

Visual: Array Structure

Caption: Array storing 5 elements with index-based access.

Operations & Time Complexity

---

2. Linked Lists

A linked list is a non-contiguous data structure where elements (nodes) are linked via pointers. Each node contains:

• Data (value)
• Next (pointer to the next node)

Types of Linked Lists

1. Singly Linked List: Only next pointer.
2. Doubly Linked List: next and prev pointers.
3. Circular Linked List: Last node points back to the first.

Visual: Singly Linked List (Initial State)

Caption: Singly linked list with 3 nodes (A → B → C).

Operations & Time Complexity

Worked Example: Insertion at Head (Singly Linked List)

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

1. Create new node X with next = current head (A).
2. Update head to X.

Final State: Caption: After inserting X at head.

---

3. Stacks

A stack is a LIFO (Last-In-First-Out) data structure supporting:

• Push: Add to the top.
• Pop: Remove from the top.
• Peek: View top element without removal.

Implementations

1. Array-based: Fixed size, efficient but limited.
2. Linked List-based: Dynamic size, no overflow.

Visual: Stack Operations (Array-Based)

Caption: Stack after push(D) and pop().

Operations & Time Complexity

Worked Example: Stack with Linked List

Task: Push 1, 2, 3; then pop twice. Trace:

Code Implementation (C):

typedef struct Node {
    int data;
    struct Node* next;
} Node;

void push(Node** top, int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = value;
    newNode->next = *top;
    *top = newNode;
}

int pop(Node** top) {
    if (*top == NULL) return -1; // Underflow
    Node* temp = *top;
    int val = temp->data;
    *top = (*top)->next;
    free(temp);
    return val;
}

---

In the Real World

1. eSewa (Nepal):

   • Stacks are used in transaction processing. When a user pays for a bill (e.g., electricity), the payment request is pushed onto a stack. The system processes it (LIFO) to ensure the most recent transactions are handled first, reducing delays for urgent payments.

2. Pathao (Ride-Hailing App):

   • Linked Lists manage driver availability. New drivers joining the pool are added to the end of a doubly linked list, while the app quickly accesses the nearest available driver (O(1) for head operations).

3. NTC (Nepal Telecommunications):

   • Queues (built on linked lists) handle call routing. Incoming calls are enqueued, and agents dequeue them in FIFO order. However, priority queues (a variant) ensure emergency calls (e.g., 100) are processed immediately.

4. Khalti (Digital Wallet):

   • Arrays store transaction histories for quick access. When a user checks their last 10 transactions, the app retrieves them in O(1) time via array indexing.

5. Daraz (E-Commerce):

   • Stacks manage undo operations. If a user accidentally adds an item to cart, Daraz uses a stack to revert the last action (LIFO).

---

Comparisons & Trade-offs

---

Applications in Nepalese Context

1. Bank Loan Processing (Nabil Bank, Global IME):

   • Stacks manage loan approval queues. High-priority loans (e.g., education) are pushed first and processed immediately (LIFO ensures urgency).

2. Kathmandu Traffic Management (NTC, Smart City Projects):

   • Linked Lists model traffic routes. New routes are added dynamically, and the system efficiently reroutes vehicles during congestion (doubly linked lists allow backward traversal for alternative paths).

3. NEPSE (Stock Exchange):

   • Arrays store daily stock prices for quick retrieval. Traders access historical data in O(1) time to analyze trends.

---

Exam Tip

1. Definitions:

   • Always define stack as "LIFO" and linked list as "non-contiguous nodes with pointers."
   • For doubly linked list, mention both next and prev pointers.

2. Diagrams:

   • Must draw:
     • Array with indices.
     • Singly/doubly linked list before and after operations (insertion/deletion).
     • Stack push/pop steps (show top pointer movement).
   • Label clearly: Use arrows for pointers, highlight changed nodes.

3. Time Complexity:

   • Memorize O(1) for stack operations and O(n) for array insertions/deletions (unless at the end).
   • For linked lists, emphasize O(1) for head operations and O(n) for tail operations (singly).

4. Common Pitfalls:

   • Stack overflow: Occurs when pushing to a full array-based stack.
   • Dangling pointers: Forgetting to update next/prev during deletion (leads to memory leaks).
   • Circular references: In doubly linked lists, ensure prev of head and next of tail are null.

5. Code Snippets:

   • Exams may ask for pseudocode or C/Java code for:
     • Insertion/deletion in linked lists.
     • Stack operations (push/pop/peek).
   • Trace tables (like above) are often required for algorithm steps.

---

Pro Tip: Practice drawing linked lists by hand—examiners check for correctness in pointer updates! For stacks, always show the top pointer moving.