Data Structures: Arrays vs. Linked Lists¶

Data structures are the foundation of programming, and arrays and linked lists—two of the most basic data structures—are used in nearly every program. For beginners, understanding their differences and applicable scenarios helps make more rational choices in future learning. Let’s break down how arrays and linked lists differ in the simplest terms.

Arrays: A “Continuous Row of Seats”¶

Imagine you’re the class monitor counting everyone’s height. You ask students to line up by student ID, with each person (element) in a fixed position—e.g., the first position is Xiaoming, the second is Xiaohong, the third is Xiaogang… This “fixed-line” storage is an array.

Key Features of Arrays:
- Contiguous Storage: All elements occupy a single block of consecutive memory. Each element has a unique “position number” (index, e.g., 0th, 1st, 2nd).
- Random Access: Elements can be accessed directly via index. For example, to get the 3rd element (index 2), you directly locate it in O(1) time (constant time).
- Fixed Size (Initial Allocation): Arrays require predefining a size at creation. For example, declaring an array of length 10 reserves 10 consecutive memory slots. If more space is needed, you must reallocate a larger block and copy existing elements (a time-consuming process).

Linked Lists: A “Scattered Skewer of Haws”¶

If students don’t want to line up (due to limited space), you could ask them to hold a note with the next student’s name: Xiaoming’s note says “Xiaohong”, Xiaohong’s says “Xiaogang”, and so on. Each person (node) is connected via these notes (pointers/references)—this is a linked list.

Key Features of Linked Lists:
- Scattered Storage: Elements can be anywhere in memory. Each node stores data and a pointer/reference to the next node.
- No Random Access: To find the k-th element, you must traverse from the head node using pointers, taking O(n) time (linear time). For example, to find the 3rd element (Xiaogang), you first find Xiaoming (1st) → Xiaohong (2nd) → Xiaogang (3rd).
- Dynamic Expansion: No preallocated fixed-size memory is needed. New nodes can be added anywhere (end or middle) as long as memory is available, making it highly flexible.

Key Differences Comparison¶

Applicable Scenarios¶

• Use Arrays When:
• Frequent index-based access is needed (e.g., fetching map data by coordinates).
• Element count is fixed and known (e.g., storing student grades).

• Operations are primarily “append/delete at the end”.

• Use Linked Lists When:

• Frequent insertions/deletions in the middle are needed (e.g., implementing queues, stacks, or hash tables).
• Element count is uncertain (e.g., dynamic storage of large datasets).
• Random access is not a priority.

Example to Reinforce Understanding¶

Suppose we need a “student linked list” with name and ID, and need to:
1. Add Xiaoming (ID 1)
2. Add Xiaohong (ID 2)
3. Insert Xiaogang (ID 3) between Xiaoming and Xiaohong

Array Implementation:
Arrays have a fixed size. Initially [null, null]. Insert Xiaoming at index 0, Xiaohong at 1. To insert Xiaogang between them, you must shift Xiaoming and Xiaohong right, expanding the array to [null, Xiaoming, Xiaohong, Xiaogang]—inefficient and space-wasting.

Linked List Implementation:
Xiaoming’s pointer points to Xiaohong, and Xiaohong’s points to null. Inserting Xiaogang: just change Xiaoming’s pointer to Xiaogang, and Xiaogang’s pointer to Xiaohong. The list becomes Xiaoming → Xiaogang → Xiaohong—no element movement needed, only pointer changes.

Final Takeaway¶

Arrays and linked lists are not “good or bad”—they’re “fit or not fit”. Understanding their storage and operation differences helps write efficient code. For beginners, practice with arrays (e.g., storing student scores) and linked lists (e.g., dynamic list operations) to master their core distinctions.