List
Overview
A List is an abstract data type (ADT) that represents an ordered collection of elements. Elements maintain a specific sequence, and duplicates are usually allowed.
Lists define what operations are possible, not how they are implemented.
What Is a List?
A list:
- Preserves insertion order
- Allows positional access
- Can grow or shrink dynamically
- May allow duplicate elements
Concrete implementations include array lists and linked lists.
Core List Operations
| Operation | Description |
|---|---|
| Insert | Add element at a position |
| Delete | Remove element |
| Access | Get element by index |
| Update | Modify element |
| Search | Find element |
| Traverse | Iterate through list |
How It Works
As an ADT:
- The list specifies behavior
- Implementation decides performance
- Indexing is conceptual, not guaranteed efficient
Example
Pseudocode
list.add(10)
list.add(20)
list.addAt(1, 15)
print(list[1]) // 15
Real-world Analogy
A list is like a playlist. Order matters, repeats are fine, and you can insert a song anywhere 🎶.
Time Complexity (Typical)
| Operation | Array List | Linked List |
|---|---|---|
| Access | O(1) | O(n) |
| Insert | O(n) | O(1)* |
| Delete | O(n) | O(1)* |
* When position is known.
Use Cases
- Collections frameworks
- Sequential data storage
- Task queues
- History tracking
Advantages
- Ordered data
- Flexible size
- Simple abstraction
Limitations
- Random access not guaranteed
- Performance varies by implementation
- Not optimized for key-based lookup