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.

Try list, stack, queue, and deque operations in our ADT Explorer.

Common Linear ADTs

List

• 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)

Stack

• 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

Queue

• 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

Deque

• 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)

Data Structures to Implement Linear ADTs

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