1.4.2 Data Structures

• Array

  • Static Data Structure
  • Stores ordered set of data
  • Of the same data type
  • Under a single identifier (variable)
• Graph

  • Data structure consisting of a set of vertices/nodes connected by edges/arcs
• Hash Table

  • Hashing algorithm calcs a value to determine where a data value is to be stored
  • Directly accessed
  • the role of the hash function is to map the key to an index in the hash table
  • collision - where two inputs result in the hashed table
  • a good hashing algorithm should have a low probability of collisions
  • collision resolution - item placed in the next available location when there is a collision
  • normally used for indexing - provides fast access to data due to keys having a unique one-to-one relationship with the address they are stored at
• Linked Lists

  • Dynamic Data Structure
  • Ordered sequence of data
  • Each data stored with pointer which points to next item in list
  • Not stored contiguously in memory
  • values can be easily added or removed by editing pointers
• Lists

  • data structure
  • stores sequences of data values each with unique index
• Queues

  • FIFO data structure
  • First item to be pushed is first item to be popped
  • 2 pointers: one pointing to the front and one pointing to the back, where the next item can be added
• Records

  • Stores data in fields
  • Organised based on attributes
• Stacks

  • LIFO structure
  • Last item pushed is first to be popped
  • uses 1 pointer which points to the top of the stack, where the next piece of data will be inserted
• Trees

  • each node is child node of parent node
  • hierarchical structure
• Tuples

  • storing immutable data (can't be modified)
  • of different data types
  • under single identifier
• Arrays vs Lists

  1. Lists are stored non-contiguously which means they don't have to be stored next to each other in memory like data in arrays do
  2. Lists contain elements of more than one data type, unlike arrays
• Example of a Linked List:

  
• Circular Queues

  • also a FIFO structure similar to linear queues
  • once the queue's rear pointer is equal to the maximum size of the queue, it can loop back to the front of the array and store values here provided that it is empty
  • circular queues can use space in an array more effectively although they are harder to implement
• Trees

  
• Key Terms in Trees

  
• Uses of Hash Tables::

  • securely stores data such as pins or passwords