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.
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.
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 |
A linked list is a dynamic data structure comprised of nodes pointing to other nodes.
Singly linked lists only hold a reference to the next node. Doubly linked lists hold a reference to the next and previous nodes.
Pros | Cons | |
---|---|---|
Singly linked | Uses less memory, simpler implementation | Cannot easily access previous elements |
Doubly linked | Can be traversed backwards | Takes 2x memory |
Singly linked | Doubly Linked | |
---|---|---|
Search | ||
Insert at head | ||
Insert at tail | ||
Remove at head | ||
Remove at tail | ||
Remove in middle |
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 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.