Arrays and Linked Lists: Address Calculation, Types and Big-O · অ্যারে ও লিংকড লিস্ট: অ্যাড্রেস নির্ণয়, প্রকারভেদ ও বিগ-ও

1. Arrays: the basic idea

An array is a collection of elements of the same data type stored in contiguous (side-by-side) memory locations and reached by an index (subscript). Because every element has the same size and they sit one after another, the computer can compute where any element is, so arrays give random (direct) access: A[700] costs the same as A[0].

• Lower bound (LB) is the smallest index and upper bound (UB) the largest. C, C++, Java and Python start at 0; pseudocode and some exam questions start at 1 or at any number.
• Number of elements = UB − LB + 1. An array A[−5 … 20] has 20 − (−5) + 1 = 26 elements.
• A classic array has a fixed size set when it is created. Dynamic arrays (C++ vector, Java ArrayList, Python list) grow by copying into a bigger block when full.
• A two-dimensional array is a table of rows and columns, so it is also called a matrix or table array.

2. Address calculation

One dimension. With base address B (the address of the first element), element size w bytes and lower bound LB:

Address of A[i] = B + w × (i − LB)

For a C array (LB = 0) this is B + w × i. Example: int A[], B = 1000, w = 2, LB = −5: A[7] is at 1000 + 2 × (7 + 5) = 1024.

Two dimensions. Memory is one long line, so a table must be laid out in some order:

• Row-major: the whole of row 0, then row 1, and so on. C and C++ use it, and so does Python's NumPy by default. (Java builds a 2-D array as an array of separate row arrays, but exam questions still treat it as row-major.)
• Column-major: the whole of column 0, then column 1, and so on. Fortran, MATLAB and R use it.

For A with rows LB₁ … UB₁ and columns LB₂ … UB₂, let R = UB₁ − LB₁ + 1 (rows) and C = UB₂ − LB₂ + 1 (columns). Then:

Order	Address of A[i][j]	With indices from 0 (m rows, n columns)
Row-major	B + w × [(i − LB₁) × C + (j − LB₂)]	B + w × (i × n + j)
Column-major	B + w × [(j − LB₂) × R + (i − LB₁)]	B + w × (j × m + i)

The memory picture: in row-major you skip whole rows (each C elements long) to reach row i, then step along the row; in column-major you skip whole columns (each R elements long).

Worked example 1 (indices from 0). int M[4][5] (4 rows, 5 columns), base address 2000, w = 4 bytes. Find the address of M[2][3].

1. Row-major: skip 2 full rows of 5 elements = 10 elements, then 3 more: offset 2 × 5 + 3 = 13 elements.
2. Address = 2000 + 4 × 13 = 2052. (A C program printing &M[2][3] − &M[0][0] gives 52 bytes, the same offset.)
3. Column-major: skip 3 full columns of 4 elements = 12 elements, then 2 more: 14 elements.
4. Address = 2000 + 4 × 14 = 2056.

Worked example 2 (any lower bounds). A[−2 … 7][3 … 10], base 500, w = 4. Find A[4][6] in both orders.

1. Rows: R = 7 − (−2) + 1 = 10. Columns: C = 10 − 3 + 1 = 8.
2. Row offset i − LB₁ = 4 − (−2) = 6; column offset j − LB₂ = 6 − 3 = 3.
3. Row-major: 500 + 4 × (6 × 8 + 3) = 500 + 4 × 51 = 704.
4. Column-major: 500 + 4 × (3 × 10 + 6) = 500 + 4 × 36 = 644.

The usual slip is multiplying by the wrong count: row-major multiplies the row offset by the number of columns; column-major multiplies the column offset by the number of rows.

Sparse matrix. A matrix in which most elements are zero. Storing it in full wastes space, so only the non-zero elements are kept, as (row, column, value) triplets in an array, or in a linked list. A plain 2-D array is the wrong choice when, for example, 990 of 1,000 cells are 0.

3. Strings

A string is a sequence of characters, stored as an array of characters. In C a string ends with the null character '\0' (value 0), which takes one extra byte:

• char s[] = "DHAKA"; → sizeof s = 6 bytes (5 letters + '\0'), strlen(s) = 5.
• char t[10] = "DHAKA"; → sizeof t = 10 (the declared size), strlen(t) = 5.

strlen walks the array until it meets '\0', so it costs O(n). Java and Python store the length with the string (O(1) to read) and their strings are immutable: "changing" one makes a new string. With UTF-8 text, as in Bangla, one character can take 1 to 4 bytes, so bytes and characters are not the same count.

4. Linked lists and their types

A linked list is a chain of nodes. Each node holds the data and a pointer (link) to the next node; the nodes can be anywhere in memory. A pointer called head marks the first node, and the last node's next pointer is NULL. A linked list is a linear, dynamic data structure: nodes are created (malloc / new) and freed as needed.

struct node {
    int data;
    struct node *next;     /* a singly linked list node has 2 fields */
};

A structure that holds a pointer to its own type, like struct node, is called a self-referential structure; it is the building block of every linked list and tree. If malloc cannot find memory for a new node (it returns NULL) the list has an overflow; trying to delete from an empty list is an underflow. Some lists start with a header (sentinel) node that holds no real data, so that inserting or deleting at the front needs no special case.

Type	Links in each node	Fields per node (minimum)	Can move	Last node points to
Singly linked	next	2 (data, next)	Forward only	NULL
Doubly linked	prev and next	3 (prev, data, next)	Both ways	NULL
Circular singly	next	2	Forward, round and round	The first node
Circular doubly	prev and next	3	Both ways, round and round	The first node (and the first node's prev points to the last)

Uses: singly lists for stacks, queues and the chains of a hash table; doubly lists for browser back/forward, undo and the LRU cache; circular lists for round-robin CPU scheduling and repeating playlists.

Inserting into a doubly linked list between nodes P and Q changes 4 links: the new node's prev (to P) and next (to Q), P's next and Q's prev. Inserting at the head changes the new node's next, the old head's prev and the head pointer itself.

5. Costs: the Big-O table

n is the number of elements.

Operation	Array	Singly linked list	Doubly linked list
Access the k-th element	O(1)	O(n)	O(n)
Search an unsorted list	O(n)	O(n) (n comparisons in the worst case)	O(n)
Search a sorted list	O(log n) with binary search	O(n): no random access, so no binary search	O(n)
Insert at the beginning	O(n): shift everything	O(1)	O(1)
Insert at the end	O(1) if there is room (amortised O(1) for a dynamic array)	O(n); O(1) with a tail pointer	O(1) with a tail pointer
Insert after a node you already hold	O(n) shifting	O(1)	O(1)
Delete the first element	O(n) shifting	O(1)	O(1)
Delete the last element	O(1)	O(n): you need the node before it, even with a tail pointer	O(1) with a tail pointer
Delete a node you hold a pointer to	O(n) shifting	O(n) to find its predecessor (see trick 3 in section 8)	O(1)
Count the elements	O(1) (size known)	O(n) unless a counter is kept	O(n) unless a counter is kept

Worked example 3: n sorted insertions. Insert n numbers one by one into an empty linked list, keeping it sorted. In the worst case each new number belongs at the end, so the k-th insertion walks past all k − 1 nodes already there. Total comparisons = 0 + 1 + … + (n − 1) = n(n − 1)/2, which is Θ(n²). (A simulation for n = 10 counts 45 = 10 × 9/2.)

A queue on a singly linked list keeps two pointers: enqueue at the rear (O(1): link the new node after the tail) and dequeue at the front (O(1): move head forward). Doing it the other way round (adding at the front, removing at the rear) makes dequeue Θ(n), because the node before the rear must be found by walking from the head.

6. Array vs linked list

Point	Array	Linked list
Memory	One contiguous block	Nodes scattered, joined by pointers
Size	Fixed when created (static)	Grows and shrinks at run time (dynamic)
Access	Random (direct), O(1)	Sequential, O(n)
Insert or delete in the middle	O(n), elements shift	O(1) once the place is found
Extra memory	None per element	One pointer (singly) or two (doubly) per node
Cache behaviour	Very good: neighbours are adjacent	Poor: nodes are scattered
Wasted space	Unused slots if declared too big	None, apart from the pointers
Binary search	Possible when sorted	Not practical
Good for	Lookup by index, matrices, fixed tables	Frequent insertions and deletions, queues, unknown sizes

7. Classic linked-list questions

The functions below were compiled and run together on the list 10 → 20 → 30 → 40 → 50.

/* reverse in place: O(n) time, O(1) extra space */
struct node *reverse(struct node *head) {
    struct node *prev = NULL, *cur = head, *next;
    while (cur != NULL) {
        next = cur->next;          /* remember the rest of the list */
        cur->next = prev;          /* turn this link around */
        prev = cur;                /* step forward */
        cur = next;
    }
    return prev;                   /* the old last node is the new head */
}

/* middle: slow moves 1 step, fast moves 2 */
struct node *middle(struct node *head) {
    struct node *slow = head, *fast = head;
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;                   /* for an even length: the second middle */
}

/* Floyd's cycle detection: returns 1 if there is a loop */
int has_cycle(struct node *head) {
    struct node *slow = head, *fast = head;
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) return 1;
    }
    return 0;
}

/* print in reverse order with recursion */
void print_reverse(struct node *p) {
    if (p == NULL) return;
    print_reverse(p->next);        /* print the rest first */
    printf("%d ", p->data);        /* then this node */
}

Results: reverse turns 10 20 30 40 50 into 50 40 30 20 10; middle returns 30 (and for six nodes, 60 50 40 30 20 10, it returns the second middle, 30); print_reverse on 50 40 30 20 10 prints 10 20 30 40 50; has_cycle returns 0, and 1 after the last node is linked back into the list.

Reversing, step by step. Three pointers walk the list. At each node: save next, point the node back at prev, then move prev and cur one step on. When cur becomes NULL, prev is the new head. Every node is visited once: O(n) time, O(1) extra memory.

Cycle trace. List 1 → 2 → 3 → 4 → 5 → 6, with 6 linked back to 3. After each step (slow, fast): (2, 3), (3, 5), (4, 3), (5, 5): they meet at node 5 after 4 steps, so there is a loop. Inside a loop the fast pointer gains one node per step on the slow one, so it must catch it; without a loop it reaches NULL. Floyd's method needs only two pointers, O(1) memory, against O(n) for remembering visited nodes in a hash set.

8. Tricky exam cases

1. Array of a complete binary tree. Store the tree level by level. With indices from 0, the children of node i are at 2i + 1 and 2i + 2 and its parent at ⌊(i − 1)/2⌋. With indices from 1, the children are at 2i and 2i + 1 and the parent at ⌊i/2⌋. Read which convention the question uses.
2. Sum of v[i][j] = i − j over an n × n array is 0: every pair (i, j) is matched by (j, i) with the opposite sign, and the diagonal is 0.
3. Deleting a node of a singly linked list when you only have a pointer to it (and it is not the last node) takes O(1): copy the next node's data into it, then unlink the next node. It fails for the last node, which has no successor to copy.
4. "Access methodology in an array" is random (direct) access; a linked list is sequential.
5. Removing 11 from 3, 5, 7, 11, 13, 17: a linked list needs no data movement (one link changes), while an array must shift 13 and 17 left.
6. Array vs structure: an array holds many values of the same type reached by index; a structure (struct) groups values of different types reached by member name.