Arrays & Linear Data Structures: ADTs, Arrays, Linked Lists, and Linear Search

TAKEAWAYS

• An ADT defines a data type’s behavior without implementation details (e.g., Stack as a LIFO structure).
• Arrays store contiguous elements by index but waste space if sparse; linked lists dynamically allocate nodes but use extra pointers.
• Linear search scans sequentially (O(n)), while binary search (not covered here) splits the array (O(log n)).
• Doubly linked lists allow bidirectional traversal, while circular linked lists loop back to the head.
• Applications include eSewa’s transaction queues (FIFO), Daraz’s order lists (dynamic resizing), and Pathao’s driver assignment (linked lists for flexible routing).
• Time complexity is critical: arrays offer O(1) access but fixed size; linked lists offer O(1) insertions/deletions but O(n) access.

1. Abstract Data Types (ADTs)

An ADT is a mathematical model describing what a data structure does, not how it’s implemented. It defines:

• A set of values (e.g., integers for an array).
• A set of operations (e.g., push(), pop() for a stack).
• Preconditions (e.g., stack not empty before pop()).
• Postconditions (e.g., pop() removes the top element).

Example ADTs in this unit:

Why use ADTs?

• Abstraction: Hide implementation (e.g., use a stack without knowing if it’s an array or linked list).
• Reusability: Write code once, adapt later (e.g., swap array for a linked list).
• Correctness: Specify behavior clearly (e.g., "a queue must follow FIFO").

2. Arrays

An array is a contiguous block of memory storing elements of the same type, accessed by index.

Key Properties

• Fixed size: Resizing requires copying elements (O(n) time).
• Random access: array[i] is O(1).
• Wastes space: Sparse arrays (e.g., calendar with few events) use extra memory.

Operations

Example: Dynamic Array Resizing When an array is full, it doubles its capacity to amortize O(1) insertions.

sequenceDiagram
    participant User
    participant Array
    User->>Array: Insert(5) (capacity=2, size=2)
    Array-->>User: Resize to 4 (capacity doubles)
    User->>Array: Insert(6) (now fits)
    User->>Array: Insert(7) (capacity=4, size=3)
    Array-->>User: Resize to 8 (capacity doubles)

Worked Example: eSewa Transaction Log eSewa stores transactions in an array of size 1000. After 1000 transactions, it resizes to 2000 to avoid frequent reallocations.

transactions = [None] * 1000  # Initial capacity
transactions.append("Payment1")  # Size=1, capacity=1000
# ... after 1000 inserts:
transactions = transactions + [None] * 1000  # New capacity=2000

3. Linked Lists

A linked list stores elements in non-contiguous nodes, each with:

• Data (value).
• Pointer (next node’s address).

Types

Operations

Figure: Singly Linked List Insertion

Initial: A <-> B <-> C
After inserting 1 at head:
1 <-> A <-> B <-> C

Worked Example: Daraz Order Queue Daraz uses a singly linked list to process orders dynamically:

1. Prepend a new order (O(1)).
2. Traverse to find the oldest order (O(n)).
3. Delete after processing (O(1) if node is known).

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

# Insert at head (newest order)
def prepend(head, order_id):
    new_node = OrderNode(order_id)
    new_node.next = head
    return new_node

# Process oldest order (delete head)
def process_order(head):
    if head:
        return head.next  # Remove head
    return None

4. Linear Search

Definition: Sequentially checks each element until the target is found or the list ends.

Algorithm

flowchart TD
    A["Start at index 0"] --> B{"Element == target?"}
    B -- Yes --> C["Return index"]
    B -- No --> D["Increment index"]
    D --> B

Time Complexity

• Best case: O(1) (target is first element).
• Average/Worst case: O(n) (target is last or absent).

Worked Example: Searching Pathao Drivers Pathao’s app searches for a driver with ID 12345 in a linked list:

def linear_search(head, target):
    current = head
    index = 0
    while current:
        if current.data == target:
            return index
        current = current.next
        index += 1
    return -1  # Not found

Trace Table:

5. Comparison: Arrays vs. Linked Lists

In the Real World

1. eSewa’s Transaction Log

   • Idea: Uses an array to store transactions (fixed size initially).
   • Why: Fast random access for audits; resizes dynamically to avoid overflow.
   • Real Example: After 10,000 transactions, eSewa doubles its array capacity to 20,000.

2. Daraz’s Order Processing

   • Idea: Orders are stored in a singly linked list for dynamic insertion/deletion.
   • Why: New orders arrive frequently; linked lists handle growth without resizing.
   • Worked Example: A new order is prepended to the list (O(1)), while processing starts from the head (oldest order).

3. Pathao’s Driver Assignment

   • Idea: Drivers are managed in a doubly linked list to allow quick insertion/deletion in both directions.
   • Why: Drivers can be added/removed from the front (new drivers) or middle (reassigned drivers).
   • Real Example: If Driver A is reassigned, Pathao’s system deletes A from its current node and inserts A into a new node in the available pool (O(1) for both).

Exam Tip

• Focus on ADT definitions: Exams often ask to explain an ADT (e.g., "Define an array as an ADT").
• Compare arrays and linked lists: Highlight trade-offs (e.g., "Arrays have O(1) access but waste space").
• Trace algorithms: For linear search, show the step-by-step traversal (like the Pathao driver example above).
• Time complexity: Memorize O(1), O(n), and O(log n) for key operations (e.g., array access is O(1), linked list search is O(n)).
• Real-world links: Connect concepts to apps (e.g., "eSewa uses arrays for transactions; Daraz uses linked lists for orders").