01. Linear List
The linear list is one of the most fundamental and commonly used structures in data structures. Understanding it will help you learn stacks, queues, strings, and more.
1. Basic Concepts
- Linear List: A finite sequence of n data elements of the same data type
- Features: Has a unique first and last element; except for the first and last, each element has exactly one predecessor and one successor
2. Storage Structure Comparison
| Storage Type | Contiguous Address | Supports Random Access | Insert/Delete Efficiency | Space Utilization |
|---|---|---|---|---|
| Array List | Yes | Yes | Low | Low |
| Linked List | No | No | High | High |
- Array List: Uses a group of contiguous memory units to store linear list elements in order
- Linked List: Each node contains a data field and a pointer field, connected by pointers
3. Animation Demo
4. Common Pitfalls
When inserting/deleting in an array list, you need to move all subsequent elements; in a linked list, you only need to modify pointers. Don’t get confused!
5. Typical Applications of Linear Lists
- As the basis for stacks, queues, strings, and other data structures
- Task queues, browsing history, shopping carts, undo/redo in text editors, etc.
| Application Scenario | Recommended Structure |
|---|---|
| Frequent random access | Array List |
| Frequent insertions/deletions | Linked List |
Exercises
- Briefly describe the definition and main features of a linear list.
- What are the advantages and disadvantages of array lists and linked lists?
- What is the basic idea of insertion and deletion operations in a singly linked list?
- How to traverse a linear list?
- What are some typical applications of linear lists?
Reference Answers
1. Definition & Features
A linear list is an ordered sequence of n data elements, with a unique first and last element, and one-to-one relationships between elements.
2. Pros & Cons of Array List and Linked List
Array List: Fast search, slow insert/delete, low space utilization;
Linked List: Fast insert/delete, slow search, high space utilization
3. Singly Linked List Insert/Delete
Insert: The new node points to the successor, the predecessor points to the new node;
Delete: The predecessor points to the successor of the deleted node
4. Traversal Implementation
Array List: Loop by index;
Linked List: Visit each node via pointer
5. Typical Applications
Stacks, queues, strings, search, sort, merge, etc.