Limited Access Data Structures
- Explain what is meant by the limited-access data structure.
An array is a random-access data structure, where each element can be accessed directly and in constant time. Random access is critical to many algorithms, for example, to binary search.
- A typical illustration of random access is a book — each book page can be reached independently of others.
A linked list is a sequential-access data structure, where each element can be accessed only by traversing the list.
- A typical illustration of sequential access is a roll of paper or tape — all prior material must be unrolled to get to the data you want.
A stack and a queue are examples of restricted or limited-access data structures. You can only access (add, read, and delete) the element at the front or back position (or both). Access to other parts is forbidden.
By limiting operations, we can create very efficient implementations.