# Data Structures

# Introduction to Data Structures

- A
**data structure**refers to the way data is organised, stored, and retrieved in computing. - Data structures are key in ensuring that data is easily accessible within a program and that operations can be performed efficiently.
- Each type of data structure has strengths and weaknesses that determine in what exact cases it is best utilised.
- Understanding the complexity (measured in
**Big O notation**) of operations within data structures is crucial. - Data structures include but are not limited to: arrays, stacks, queues, linked lists, trees, graphs, hash tables.

# Arrays

- An
**array**is a fundamental data structure that stores elements of the same type in a continuous memory location. - Elements in an array can be accessed directly by their
**index**, starting at 0 for the first position. - Adding or removing elements from an array requires shifting elements and can consume considerable time.

# Linked Lists

- A
**linked list**is a dynamic data structure where each element (node) contains a reference to the next node in the sequence. - Different types of linked lists exist, including
**singly linked**,**doubly linked**, and**circular linked lists**. - Linked lists do not require preallocated space like arrays and elements can be added or removed in a constant amount of time.

# Stacks

- A
**stack**is a last in, first out (LIFO) structure, meaning that the last element added is the first to be removed. - Common operations include
**push**(to add an element) and**pop**(to remove an element). - Stacks can be used in various algorithms, such as to reverse a word or check balanced symbols.

# Queues

- A
**queue**operates in a first in, first out (FIFO) methodology; the first element added is the first to be removed. - Primary operations are
**enqueue**(add to end) and**dequeue**(remove from front). - Queues are effective in situations where tasks must be done in the order they arrive (such as a print queue).

# Trees

- A
**tree**is a non-linear hierarchical data structure with a root and nodes, where each node has at most a single parent but can have multiple children. - A binary tree is a type of tree where each node has at most two children, referred to as the left child and the right child.
- Tree traversal can be performed in a variety of ways including in-order, pre-order and post-order.

# Graphs

- A
**graph**is a non-linear data structure made up of nodes or vertices, connected by edges. - Graphs can be either
*directed*(edges with direction) or*undirected*. - Numerous algorithms exist for graphs, including searching and sorting algorithms.

# Hash Tables

- A
**hash table**uses a hash function to compute an index for an array from which the desired value can be found. - Favouring access over storage, it allows for efficient retrieval of items based on their values.
- Care must be taken with the hash function and table size to avoid collisions.