ADTs are data types which have certain features and operations, without any explicit implementation. They can be coded however, without any language restriction
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