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.

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.

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.

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).

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.

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.

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.