Linear ADTs¶

Linear ADTs model an ordered (not sorted) homogenous list of data. There are several common types of linear ADTs that differ in Behaviors.

Common Linear ADTs¶

Characteristics
- Sequential - the elements are ordered in a sequence
- Finite - known number of elements
- Indexable - each element has a unique positional index to allow random access
- Dynamic - the size of the list can change
Behaviors
- add/remove/access by index
- search (find index or pointer by value)
- find size
- check empty
Implementation
- C array (fast access/read by index)
- linked-list (fast add/remove in the middle)

Characteristics
- Finite
- Last-in-first-out (LIFO)
- Dynamic
Behaviors
- push
- pop
- peek/top
- check empty
Implementation
- C array (add/remove at the tail, limited max length)
- linked-list (add/remove at either end, unlimited max length)
Application
- Backtracking algorithm
- Depth-first traversal

Characteristics
- Finite
- First-in-first-out (FIFO)
- Dynamic
Behaviors
- enqueue
- dequeue
- check empty
Implementation
- circular C array (limited max length)
- linked-list (unlimited max length)
Application
- Breadth-first traversal

Characteristics
- Finite
- First-in-first-out (FIFO) and Last-in-first-out (LIFO)
- Dynamic
Behaviors
- enqueue_front, enqueue_back
- dequeue_front, dequeue_back
- check empty
Implementation
- circular C array (limited max length)
- linked-list (unlimited max length)
- vector of vectors (std::deque in C++ STL)

There are many data structures suitable in the implementation of the above ADTs. They should be selected according to the requirements.

C style Array
- Fast indexing
- Slow insertion, or pre-pending
- Fast appending
- Slow to change capacity (with re-allocation and data movement)
- Circular variation (suitable for queue and deque)
Linked-list
- Fast insertion, appending, pre-pending
- Slow indexing
- Complex logics
- More space overhead
Related STL containers and their implementations
- std::array
  - fixed size
  - static C array
- std::vector
  - resizable (slow)
  - dynamic C array
- std::list
  - doubly-linked-list
- std::forward_list
  - singly-linked-list
- std::deque
  - vector of vectors
- std::stack
  - wrapper of other STL containers
- std::queue
  - wrapper of other STL containers