Arrays & Linked Lists
Arrays and linked lists are two of the most fundamental linear data structures in computer science. An array stores elements in contiguous memory locations with O(1) random access; a linked list connects scattered nodes via pointers with O(1) insertion and deletion.
This guide covers array fundamentals, linked list types (singly, doubly, circular), operations complexity comparison, memory layout, advanced topics like cycle detection and sentinel nodes, code walkthroughs, and a 10-question practice quiz.
Array vs Linked List: Insertion Comparison
Array (Contiguous Memory)
Contiguous memory block
Linked List (Pointer-Linked)
Pointer-linked nodes
1Introduction
Data structures are fundamental building blocks in computer science, providing efficient ways to organize and store data. Among the most basic yet powerful linear data structures are arrays and linked lists. While both store collections of elements in a sequential manner, their underlying memory models, performance characteristics, and ideal use cases differ significantly.
Understanding these two structures is essential because they underpin nearly every higher-level data structure. Stacks, queues, hash tables, and even graphs are typically implemented on top of arrays or linked lists. Choosing the right structure for a given problem is a core skill tested in technical interviews and university exams alike.
In real-world systems, the choice between arrays and linked lists can have dramatic performance implications. Database engines use arrays (B-trees) for cache-efficient index lookups. Operating system schedulers use linked lists for process queues where frequent insertion and removal are critical. Understanding the trade-offs lets you make informed architectural decisions.
2Key Definitions
Essential terms for understanding arrays and linked lists at the university level.
Data Structure
A way of organizing and storing data for efficient access and modification
Abstract Data Type (ADT)
A mathematical model specifying operations without implementation details (e.g., List, Stack)
Array
Elements stored at contiguous memory locations, accessed by integer index
Linked List
Elements (nodes) linked by pointers, stored at non-contiguous memory locations
Node
Building block of a linked list containing data and pointer(s) to neighboring nodes
Head / Tail
First and last nodes of a linked list; head is the entry point for traversal
Contiguous Memory
Sequential, adjacent memory addresses; arrays require contiguous allocation
Random Access
Ability to access any element directly in O(1) time using an index
Sequential Access
Accessing elements by traversing from the beginning one by one; characteristic of linked lists
Pointer / Reference
Variable storing a memory address; the “glue” connecting linked list nodes
Dynamic Memory Allocation
Allocating memory at runtime (not compile time); linked lists use this extensively
Null Pointer
Special pointer value indicating no valid memory address; marks end of a linked list
Index / Subscript
Integer identifying an element's position in an array; typically zero-based
Traversal
Visiting each element in a data structure exactly once to perform some operation
Sentinel Node
A dummy node used to simplify edge cases in linked list operations
Cache Locality
Tendency for contiguous data to be loaded into CPU cache together; arrays benefit from this
3Array Fundamentals
An array is a collection of elements of the same data type stored in contiguous memory locations, accessed via an integer index. The address of any element can be calculated directly: address(arr[i]) = base_address + i * sizeof(element).
Key Characteristics
Advantages
- O(1) random access via index calculation
- Cache-friendly due to contiguous memory (spatial locality)
- Memory efficient for data itself (no pointer overhead)
- Simple, predictable memory layout
Disadvantages
- Fixed size (resize requires O(n) copy)
- O(n) insertion/deletion in the middle (shifting)
- Potential wasted space if partially filled
- Requires large contiguous memory block
Address Calculation
How O(1) Access Works
Base address: 0x1000
Element size: 4 bytes (int)
arr[3] address: 0x1000 + 3 * 4 = 0x100C
Direct arithmetic means any element is accessible in constant time, regardless of array size.
Types of Arrays
One-dimensional arrays store a simple sequence of elements. Multi-dimensional arrays (2D matrices, 3D tensors) are arrays of arrays, used for tables, images, and scientific computing. Dynamic arrays (Python list, Java ArrayList, C++ vector) automatically resize by allocating a larger block and copying elements, providing amortized O(1) append.
4Linked List Types
A linked list stores elements in nodes scattered throughout memory, connected by pointers. Unlike arrays, linked lists are dynamic in size and excel at insertions and deletions.
Singly Linked List
Each node contains data and a next pointer. Traversal is forward-only. The last node's next pointer is null.
Head → [10|next] → [20|next] → [30|null]
Doubly Linked List
Each node contains prev pointer, data, and next pointer. Allows bidirectional traversal. More memory per node but O(1) deletion of a known node.
null ← [prev|10|next] ↔ [prev|20|next] ↔ [prev|30|next] → null
Circular Linked List
The last node's next pointer points back to the head, forming a circle. Can be singly or doubly linked. Useful for round-robin scheduling and circular buffers.
Head → [10|next] → [20|next] → [30|next] → (back to Head)
Care must be taken to avoid infinite loops during traversal.
Advantages and Disadvantages
Advantages
- Dynamic size — grows and shrinks at runtime
- O(1) insertion/deletion if position is known
- No wasted pre-allocated space
- Efficient for frequent middle modifications
Disadvantages
- O(n) sequential access — no random access
- Extra memory for pointers in each node
- Poor cache locality — scattered memory
- Reverse traversal hard (singly linked)
5Operations Comparison
The fundamental trade-off: arrays provide O(1) access but O(n) insertion/deletion; linked lists provide O(1) insertion/deletion (at known positions) but O(n) access.
| Operation | Array | Singly LL | Doubly LL |
|---|---|---|---|
| Access (by index) | O(1) | O(n) | O(n) |
| Search (by value) | O(n) | O(n) | O(n) |
| Insert at head | O(n) | O(1) | O(1) |
| Insert at tail | O(1)* | O(n)† | O(1)‡ |
| Insert at middle | O(n) | O(n) | O(n) |
| Delete at head | O(n) | O(1) | O(1) |
| Delete at tail | O(1) | O(n) | O(1)‡ |
| Delete at middle | O(n) | O(n) | O(n) |
* Amortized O(1) for dynamic arrays † O(1) if tail pointer maintained ‡ With tail pointer
6Advanced Topics
Floyd's Cycle Detection (Tortoise & Hare)
A cycle occurs when a node's next pointer references an earlier node. Floyd's algorithm uses two pointers: slow (moves 1 step) and fast (moves 2 steps). If they meet, a cycle exists. Time: O(n), Space: O(1).
Sentinel (Dummy) Nodes
A sentinel node is a dummy placeholder (often at the head) that eliminates special-case handling for empty lists and head operations. Code becomes simpler and less error-prone since you never need to check if head == null.
Cache Performance & Spatial Locality
Array: Excellent Locality
Contiguous elements are loaded into CPU cache together. Iterating through an array hits the L1/L2 cache frequently, making traversal very fast in practice.
Linked List: Poor Locality
Nodes scattered in memory cause frequent cache misses. Each pointer dereference may require loading a new cache line from main memory, significantly slowing traversal.
Dynamic Arrays: Bridging the Gap
Dynamic arrays (Python list, Java ArrayList, C++ vector) combine array benefits with resizing capability. When capacity is exceeded, a new array (typically 2x size) is allocated and elements are copied. Append is amortized O(1): most appends are O(1), with occasional O(n) resizes averaged across all operations.
7Code Walkthroughs
Array Access by Index
arr = [10, 20, 30, 40] print(arr[2]) # Output: 30
Line 1: Declares an array with 4 elements stored in contiguous memory.
Line 2: Accesses element at index 2 in O(1) time using address calculation: base + 2 * sizeof(int).
Key insight: Arrays provide O(1) random access by index through direct address arithmetic.
Linked List Traversal
def traverse(head):
curr = head
while curr:
print(curr.val)
curr = curr.nextLine 2: Start at the head node — the only entry point to the list.
Lines 3–4: Visit each node, printing its value. The while curr check stops at null (end of list).
Line 5: Follow the next pointer to advance to the subsequent node.
Key insight: Linked lists require sequential traversal — no random access is possible.
Insert Element into Array
def insert(arr, idx, val):
# Shift elements right from end to idx
for i in range(len(arr)-1, idx-1, -1):
arr[i+1] = arr[i]
arr[idx] = val
return arrLine 2: Elements must be shifted right to make room — this is why array insertion is O(n).
Line 3: Iterate backwards from the last element to the insertion index.
Line 5: Place the new value at the target index after all shifts are complete.
Key insight: Array insertion requires shifting all subsequent elements, making it O(n) in the worst case.
Reverse a Singly Linked List
def reverse(head):
prev, curr = None, head
while curr:
next_node = curr.next # Save next
curr.next = prev # Reverse link
prev = curr # Advance prev
curr = next_node # Advance curr
return prevLine 2: Initialize prev to None (new tail) and curr to head.
Line 4: Save curr.next before overwriting it — otherwise we lose the rest of the list.
Line 5: Point current node backward to prev — this reverses the link direction.
Line 8: After the loop, prev points to what was the last node — the new head.
Key insight: Reversing a linked list requires a single pass with three pointers — prev, curr, and next.
Merge Two Sorted Linked Lists
def merge(l1, l2):
dummy = ListNode(0)
curr = dummy
while l1 and l2:
if l1.val <= l2.val:
curr.next = l1
l1 = l1.next
else:
curr.next = l2
l2 = l2.next
curr = curr.next
curr.next = l1 or l2
return dummy.nextLine 2: A dummy/sentinel node simplifies the merge by providing a stable starting point.
Lines 5–10: Compare the heads of both lists, attach the smaller node, and advance that list's pointer.
Line 12: After one list is exhausted, attach the remainder of the other list directly.
Key insight: Merging two sorted lists takes linear time and constant extra space using a dummy node pattern.
Detect Cycle in Linked List (Floyd's Algorithm)
def hasCycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next # Move 1 step
fast = fast.next.next # Move 2 steps
if slow == fast:
return True
return FalseLine 2: Initialize two pointers at the head — slow (tortoise) and fast (hare).
Lines 4–5: Slow advances one node, fast advances two nodes per iteration.
Line 6: If they meet, a cycle exists. If fast reaches null, there is no cycle.
Key insight: Floyd's tortoise and hare algorithm detects cycles in O(n) time with O(1) space.
8Memory Aids
“Fixed number of rooms, all next to each other. You know exactly which room by its number. Adding a room in the middle means demolishing and rebuilding the whole section.”
“Each clue tells you where to find the next clue. Clues can be anywhere. Easy to add or remove a clue — just change what the previous one points to. But you must follow the chain to find a specific clue.”
“Array's weakness is linked list's strength (insertion/deletion). Linked list's weakness is array's strength (random access).”
Array = Access Anywhere O(1). Linked List = Linked Locations O(n) access.
“No pointers, no linked list. Pointers are the glue that holds nodes together. Break a pointer link and you lose the rest of the list.”
“Array = books on one shelf (grab the next one instantly). Linked list = books scattered across a library (walk to each one).”
9Common Mistakes
Accessing array[size] instead of array[size-1]
Arrays are zero-indexed. The last valid index is size - 1. Accessing array[size] causes an index out of bounds error or undefined behavior.
Repeatedly inserting/deleting in the middle of an array
Each middle insertion costs O(n) due to shifting. If your use case requires frequent middle modifications, a linked list is the better choice.
Accessing current.next.data when current.next is None
Always check for null before dereferencing a pointer. This is the most common linked list bug: if current.next: ... before accessing current.next.data.
Forgetting to update head when inserting at the beginning or deleting the first node
If the head reference is lost, the entire list becomes unreachable. Always update the head pointer when modifying the first node.
Failing to update all necessary pointers during insertion or deletion
When inserting, set the new node's next pointer before updating the predecessor's next pointer. Reversing this order loses the rest of the list. For doubly linked lists, remember to update both next and prev.
Not handling empty lists, single-node lists, or head/tail operations
Linked list operations often require special handling for: empty lists, single-element lists, insertion/deletion at the head, and insertion/deletion at the tail. Test all these cases.
Not freeing deleted linked list nodes in manual-memory languages
In C/C++, every new must have a corresponding delete. When removing nodes, free the memory before losing the reference. In garbage-collected languages (Python, Java) this is handled automatically.
Believing “List” is an array or a linked list
“List” is an Abstract Data Type (ADT) specifying operations. Arrays and linked lists are concrete data structures that implement the List ADT. The distinction matters for exam questions and design discussions.
Frequently Asked Questions
- When should I use an array versus a linked list?
- Use an array (or dynamic array) when you know the approximate data size, need frequent random access (e.g., data[i]), prioritize cache performance, or insertions mostly happen at the end. Use a linked list when data size changes frequently, you need frequent insertions or deletions in the middle, sequential access is acceptable, and memory usage needs to be precisely minimal with no pre-allocation of unused space.
- What is a dynamic array and how does it relate to arrays and linked lists?
- A dynamic array (like std::vector in C++, ArrayList in Java, or Python's list) is an array that can grow or shrink. Internally, it's still stored in contiguous memory. When it runs out of space, a larger array is allocated (typically double the size), and all elements are copied. This makes insertion at the end amortized O(1), but individual resizes are O(n). It bridges the gap between fixed-size arrays and fully dynamic linked lists.
- Why are arrays considered cache-friendly and linked lists not?
- Arrays store elements contiguously in memory. When the CPU accesses an element, the cache loads a block of surrounding memory (spatial locality), so subsequent accesses to nearby elements are fast. Linked list nodes are scattered in memory, so each access may cause a cache miss, requiring the CPU to fetch from slower main memory.
- What is the difference between an ADT and a data structure?
- An Abstract Data Type (ADT) is a conceptual model that defines operations without specifying implementation (e.g., List, Stack, Queue). A data structure is a concrete implementation specifying how data is stored and operations carried out (e.g., Array, Singly Linked List, Hash Table). A "List" is an ADT; both "Array" and "Linked List" are data structures that can implement it.
- Can a linked list be multi-dimensional like an array?
- Not directly. A linked list is inherently a 1D linear structure. However, you can create a "list of lists" where each node's data field points to another linked list, effectively simulating multi-dimensional storage. This is more complex to manage than a traditional multi-dimensional array.
- Are there other linear data structures besides arrays and linked lists?
- Yes, but most are built on top of arrays or linked lists. Stacks (LIFO) are typically implemented with dynamic arrays or singly linked lists. Queues (FIFO) use circular arrays or singly linked lists. Deques (double-ended queues) use doubly linked lists or dynamic arrays with efficient operations at both ends.
Practice Quiz
Test your understanding of arrays and linked lists — select the correct answer for each question.
1.Which of the following operations has a time complexity of O(1) in an array?
2.What is a primary advantage of linked lists over arrays?
3.What distinguishes a doubly linked list from a singly linked list?
4.How do arrays and linked lists differ in memory allocation?
5.What is Floyd's cycle detection algorithm used for?
6.What is the time complexity of inserting an element at the beginning of an array?
7.What is a sentinel (dummy) node in linked list implementations?
8.What is the time complexity of traversing an entire linked list of n nodes?
9.When is a linked list generally preferred over an array?
10.What happens when a node's next pointer points to an earlier node in the list?
Study Tips
- Draw memory diagrams: Sketch arrays as contiguous blocks and linked lists as scattered nodes with arrows. Visualizing pointer connections builds intuition for insertion, deletion, and traversal.
- Implement from scratch: Code a singly linked list with insert, delete, search, and reverse operations. Then implement a dynamic array with resizing. Nothing cements understanding like writing the code yourself.
- Compare operations side-by-side: For each operation (access, insert, delete), trace through both the array and linked list versions to internalize the complexity differences.
- Practice edge cases: Empty structures, single-element structures, and head/tail operations are where most bugs hide. Test these systematically.