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:

- linear data structures
- non-linear data structures

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.

- Storing and accessing sequential data
- Used by IO routines as buffers
- Lookup tables and inverse lookup tables
- Used to return multiple values from a function
- Used in dynamic programming to cache answers to sub-problems

Static array | |
---|---|

Access | $O(1)$ |

Search | $O(n)$ |

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.

- Create a static array with an initial capacity.
- Add elements to the underlying static array, keeping track of the number of elements.
- If adding another element will exceed the capacity, then create a new static array with twice the capacity and copy the original elements into it.

Dynamic array | |
---|---|

Access | $O(1)$ |

Search | $O(n)$ |

Insertion | $O(n)$ |

Appending | $O(1)$ |

Deletion | $O(n)$ |

A linked list is a dynamic data structure comprised of nodes pointing to other nodes.

- Used in many list, queue, and stack implementations
- Great for creating circular lists
- Can easily model real world objects such as trains
- Used in separate chaining
- Often used in the implementation of adjacency lists for graphs

- Head: the first node in a linked list
- Tail: the last node in a linked list
- Pointer: reference to another node
- Node: an object containing data and pointer(s)

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 | $O(n)$ | $O(n)$ |

Insert at head | $O(1)$ | $O(1)$ |

Insert at tail | $O(1)$ | $O(1)$ |

Remove at head | $O(1)$ | $O(1)$ |

Remove at tail | $O(n)$ | $O(1)$ |

Remove in middle | $O(n)$ | $O(n)$ |

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.

- Used by undo mechanisms in text editors.
- Used in compiler syntax checking for matching brackets and braces.
- Used behind the scenes to support recursion by keeping track of previous function calls.
- Can be used to do a Depth First Search on a graph.

Stack | |
---|---|

Pushing | $O(1)$ |

Popping | $O(1)$ |

Peeking | $O(1)$ |

Searching | $O(n)$ |

Size | $O(1)$ |

*One* way of implementing a stack is by using a singly linked list:

- To initialize, point the head to a null node.
- To push, insert a new node before the head and adjust the head pointer to the new node.
- To pop, move the head pointer to the next node and deallocate the last node.

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.

- Any waiting line models a queue.
- Used to keep track of the
*x*most recently added elements. - First come first serve web server request management.
- Breadth first search (BFS) graph traversal.

- Enqueue: add an element to the end of the queue
- Dequeue: remove an element from the front of the queue

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 | $O(1)$ |

Dequeue | $O(1)$ |

Peeking | $O(1)$ |

Contains | $O(n)$ |

Removal | $O(n)$ |

is Empty | $O(1)$ |

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:

- The value of the left sub-tree is less than the value of its parent node
- The value of the right sub-tree is greater than or equal to the value of its parent node

A graph represents data as nodes and edges.