Arrays and Linked Lists: Singly, Doubly and Circular

An array is a collection of same-type items stored in one continuous block of memory, like numbered lockers 0, 1, 2, 3. Because items sit side by side, the computer jumps straight to any item using its position number, the index. A linked list is also a collection, but each item (a node) lives wherever memory is free, and each node stores the next node's address — like a treasure hunt where each clue points to the next.

These two structures underlie almost every program: student lists, shopping carts, playlists, and game scores. Choosing well decides whether your program runs fast or crawls, and whether it wastes memory.

Key Concepts

• Index: an element's position number; array indexing usually starts at 0, so the first element is A[0].
• Node: one unit of a linked list, holding data plus a pointer to the next node.
• Head: a pointer to the first node; an empty list has head = NULL.
• Singly linked list: each node points only forward to the next node.
• Doubly linked list: each node has next and previous pointers, allowing two-way travel at extra memory cost.
• Circular linked list: the last node points back to the first, forming a ring — ideal for round-robin scheduling.

Formulas

• Element address: address(A[i]) = base + i × element_size. If an int array starts at byte 1000 with 4-byte ints, A[3] is at 1000 + 3 × 4 = 1012.
• Random access: O(1) for arrays — one multiplication and one addition reaches any index.
• Full traversal: O(n) for both structures when visiting all n elements once.
• Middle insertion/deletion: O(n) in an array (elements shift); O(1) in a linked list once at the position (just rewire pointers).
• Assumptions: the O(1) access formula assumes 0-based indexing, fixed-size elements, and contiguous memory.

Worked Example

An integer array marks = {85, 92, 78, 90, 88} starts at address 2000, each int 4 bytes. The address of marks[3] is 2000 + 3 × 4 = 2012, holding the value 90 — found in one calculation. Now store the same marks in a singly linked list with nodes scattered at addresses 5000, 5016, 5032, 5048, 5064: the head points to 5000, whose node stores 85 and the address 5016, and so on, with the last node storing 88 and NULL. To reach the 4th mark you must walk 3 pointers from the head — no formula can jump there. But inserting a new mark between two nodes needs only two pointer changes, while the array would shift elements. This is the core trade-off: instant access versus flexible insertion.

Common Misconceptions

• "Linked lists are always better because they grow." Wrong. If you mostly read by position, an array's O(1) access beats the list's O(n) walk every time.
• "Array insertion is always O(n)." Wrong at the end — appending to an array with free capacity is O(1); only middle insertions force shifting.
• "A doubly linked list is two singly linked lists." Wrong. It is one list where each node carries both a next and a previous pointer.

Real-World Applications

• Arrays: image pixels, audio samples, spreadsheet rows, game boards.
• Singly linked lists: browser history chains, free-memory block lists in operating systems.
• Doubly linked lists: music player next/previous, LRU caches in browsers.
• Circular linked lists: round-robin CPU scheduling, multiplayer turn-based games.

Arrays give instant access by position but rigid size and costly middle insertions. Linked lists give flexible growth and cheap insertions but slow positional access. Match the structure to how your data will actually be used, and your programs will be simpler and faster.