ADTs are data types which have certain features and operations, without any explicit implementation. They can be coded however, without any language restriction
The summary of an ADT, which lists its different operations, is known as an ADT signature
Main ADT Types:
- Lists
- Arrays
- Sets
- Stacks
- Queues
- Priority Queues
- Dictionaries
- Graphs
Lists
Definition
Lists are data structures used when the number of elements is unknown.
Link to source
- Lists are without index.
- Traditionally, only the first (head) and the remaining items (tail) can be viewed
- Lists have dynamic size, and can grow or shrink as needed.
- Items are added (to the end) via appending
Arrays
Definition
Link to source
- A data structure with a set length
- Items are accessed via their index, which is a number that stores their location
- They are static (a fixed size)
- Items are added to arrays by overwriting previous value via index
Sets
Definition
Link to source
- Data structure to store unique objects i.e. objects can’t be repeated
- Similar to math sets, union, intersection, difference, etc. can be applied
- Sets can be static or dynamic, but usually dynamic.
Stacks
Definition
Link to source
- A collection of items, which are accessed in Last In First Out (LIFO) order
- Only the top (head) can be viewed (via peek) or returned (via pop)
- Adding new items is referred to as pushing
- Removing items is referred to as popping
- The last item to enter a stack is the first to come out of it
Queues
Definition
Link to source
- A collection of items accessed in First In First Out (FIFO) order
- Only the front can be viewed (similar to stacks)
- Adding items is referred to as enqueuing
- Removing items is referred to as dequeuing
- The first item that was added to a queue is also the first item to leave it
Priority Queues
Definition
Link to source
- A variation of the normal queue ADT, where items are also given a priority/rank
- Priority queues can either be minimum or maximum:
- Minimum PQueues sort elements with the lower priority first
- Maximum PQueues sort elements with the higher priority first
- The same operations of the queue apply here, such as enqueue, dequeue, etc.
Dictionaries
Definition
Link to source
- Also known as associative arrays, dictionaries store items in <key, value> pairs
- The <key> is used to access the <value>
- Generally, dictionaries are considered to be dynamic, i.e. they can grow/shrink
Graphs
Definition
Graphs are ADTs used to represent connected concepts with nodes/vertices and edges. A graph is an ordered pair of nodes and edges, expressed as
Variations of graphs can have different features, which can be used to model other properties. A few include:
Link to source
- Weights
- Direction of edges
- Node and/or edge attributes