Limited Access Data Structures
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 page of the book 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 in order to get to data you want.
A stack and a queue are examples of restricted or limited access data structure where you can only access (add, read, and delete) the element at the front or back position (or both). Access to other positions is forbidden.
By limiting operations we can create really efficient implementations.