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

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