A data structure is a format for organizing, managing, and storing data so that it can be efficiently accessed or modified. A data structure is a concrete representations of data, whereas abstract data types define the logical form of the data type. Understanding the performance a data structure provides relies upon analysis of the algorithm’s computational complexity.
Some data structures provide better performance than others for a particular application.
Data structures are classified into two categories:
A structure where elements are arranged sequentially and attached to their next and previous adjacents are called linear data structures. This type of structure involves a single level and therefore all elements can be traversed in a single run.
Examples of linear data structures include: array, stack, queue, linked list.
A structure where elements are not arranged sequentially are called non-linear data structures. This type of structure involves more than a single level and therefore all elements cannot be traversed in a single run.
Examples of non-linear data structures include: tree, graph, map.
An interface represents the set of operations that a data structure supports. An interface only provides the list of supported operations, type of parameters they can accept, and return type of these operations.
Implementation provides the internal representation of a data structure. Implementation also provides the definition of the algorithms used in the operations of the data structure.
A static array is a fixed length container of contiguous chunks of memory containing n elements indexable—each position can be referenced with a number—from range [0, n-1]. The only way to access elements in an array is by their index. Array indexing is zero-based, meaning the first element is found at position zero.
Static array | |
---|---|
Access | |
Search | |
Insertion | N/A |
Appending | N/A |
Deletion | N/A |
A dynamic array differs from a static array in that it does not have a fixed length. Rather, a dynamic array can grow and shrink in size as needed.
One way of implementing a dynamic array is to use a static array.
Dynamic array | |
---|---|
Access | |
Search | |
Insertion | |
Appending | |
Deletion |
C.f. Linked list
A stack is a one-ended linear data structure which models a real world stack by having two primary operations: push and pop. A stack is a last in first out (LIFO) data structure.
Stack | |
---|---|
Pushing | |
Popping | |
Peeking | |
Searching | |
Size |
One way of implementing a stack is by using a singly linked list:
A queue is a linear data structure which models real world queues by having two primary operations: enqueue and dequeue. A queue is a first in first out (FIFO) data structure.
There is no consistent terminology for inserting and removing elements from a queue. Enqueue is sometimes called adding or offering; dequeue is sometimes called removing or polling.
Queue | |
---|---|
Enqueue | |
Dequeue | |
Peeking | |
Contains | |
Removal | |
is Empty |
A priority queue is an abstract data type that operates similar to a normal queue except that each element has a certain priority. The priority of the elements determine the order in which elements are removed. Priority queues only support comparable data, meaning the data must be able to be ordered in some way from least to greatest or greatest to least so that it is possible to assign relative priorities to each element.
Priority queue | |
---|---|
Binary heap construction | |
Polling | |
Peeking | |
Adding | |
Naive removing | |
Removing (hash table) | |
Naive contains | |
Contains (hash table) |
Problem: Often the standard library of most programming languages only provide a min PQ which sorts by smallest elements first, but sometimes we need a max PQ. Since elements are comparable, they implement some sort of comparable interface which we can simply negate to achieve a max heap.
A tree represents data as parent nodes linked to child nodes by edges.
A binary tree is a tree structure that adheres to the following properties:
A graph represents data as nodes and edges.