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.


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


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

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.