1.4.2 Data Structures

• Data Structures

  • Arrays
  • Records
  • Lists
  • Tuples
• Data Structures

  • Linked List
  • Graphs
  • Stack
  • Queue
  • Tree
  • Binary Search Tree
  • Hash Table
• Data Structures

  1. Traversing data structures

  2. Adding data and removing data from data structures
• Array

  An ordered, finite set of elements of a single type. Zero-indexed by default
• Array

  • oneDimensionalArray = [1, 23, 12, 14, 16, 29, 12]
  • twoDimensionalArray = [[123, 28, 90, 38, 88, 23, 47],[1, 23, 12, 14, 16, 29, 12]]
  • threeDimensionalArray = [[[12,8],[9,6,19]],[[241,89,4,1],[19,2]]]
• Record

  More commonly referred to as a row in a file, made up of fields
• Record


  • fighterDataType = record integer ID string FirstName string Surname end record
• Lists are data structures consisting of ordered items where items can occur more than once. They can contain elements of more than one data type
• List values are stored non-contiguously unlike arrays
• There are a range of operations that can be performed involving lists
• Characteristics of Lists

  • Do not have to be stored next to each other in memory
  • Can contain elements of more than one data type
• List Operations

  • isEmpty()
  • append(value)
  • remove(value)
  • search(value)
  • length()
  • index(value)
  • insert(position, value)
  • pop()
  • pop(position)
• A tuple is an ordered set of values of any type
• Tuple

  Immutable, cannot be changed once created
• Tuples are initialised using regular brackets instead of square brackets
• Elements in a tuple cannot be changed or removed
• Linked Lists are dynamic data structures used to hold an ordered sequence
• Linked List

  • Items do not have to be in contiguous data locations
  • Each item is called a node and contains a data field alongside a link or pointer field
• When traversing a linked list, the algorithm outputs the values at each node until it finds that the pointer field is empty or null
• Manipulating a linked list allows values to be easily added or removed by editing pointers
• Linked list update

  Update the ‘NextFree’ pointer
• Linked list update steps

  • Update the pointer field of 'Example' to point to 'OCR' at position 3
  • Update the pointer field of 'OCR' to point to 'Linked' at position 0
• Traversing the linked list

  • 'Example', 'OCR', 'Linked', 'List'
• Removing a node from a linked list

  Update the pointer field of 'Example' to point to 'List' at index 2
• Traversing the updated linked list

  • 'Example', 'List'
• Removing a node from a linked list only ignores it, which wastes memory
• Storing pointers in linked lists requires more memory compared to an array
• Items in linked lists are stored in a sequence and can only be traversed in order
• Graphs are a set of vertices/nodes connected by edges/arcs
• Categories of graphs

  • Directed Graph
  • Undirected Graph
  • Weighted Graph
• Computers process graphs using an adjacency matrix or an adjacency list
• Adjacency Matrix Advantages

  • Convenient to work with due to quicker access times
  • Easy to add nodes
• Adjacency List Advantages

  • More space efficient for large, sparse networks
• A stack is a last in first out (LIFO) data structure
• Stacks are used to reverse actions and are key data structures in computer science
• Stacks can be implemented as either static or dynamic structures
• Stacks are implemented using a pointer pointing to the top of the stack
• Manipulating a stack

  Performing operations on a stack using specific syntax
• Stack Operations


  • isEmpty()
  • push(value)
  • peek()
  • pop()
  • size()
• Stack

  First checks the stack is not empty by looking at value of top pointer