Abstract Data Structures

• Abstract data types


  Allow us deal with the operations and behaviours of a data type and not to be concerned with their operation which is abstracted away
• Static data structure


  • Fixed block of memory that is reserved at the start of the program
  • Contiguous space on disk
  • Next memory location is the next address and its position can be implied, so there is no need to explicitly point to it
• Removing an element from a static data structure


  Not easy because we must move all the succeeding elements up one place
• Dynamic data structure


  • Memory is allocated and deallocated during the running of the program
  • Memory is allocated on the heap
  • Allows random allocation and access of memory
  • Uses linked lists where each element points to the address of the succeeding element
• Removing an element from a dynamic data structure


  Just requires pointing to a different address
• Adding an element to a dynamic data structure


  Just requires pointing to that address
• Advantages of static data structures


  • Memory locations are fixed and can be accessed easily and quickly and are in a contiguous position in memory
• Disadvantages of static data structures


  • Memory is allocated even when it is not being used
• Advantages of dynamic data structures


  • More flexible and more efficient than static data structures because we only use memory that is needed
  • Uses linked lists and makes it much easier to remove and add element
• Disadvantages of dynamic data structures

  • Data structure may be fragmented so can be slow to access
• Stacks


  Last in first out file system just like a stack of plates
• Stack operations


  • push – add element to the stack
  • pop – remove element from the stack
  • peek / top – view the top element on a stack without removing
  • isEmpty – test to see if stack is empty
  • isFull – test to see if stack is Full

  
• Uses of stacks


  • Can reverse a sequence of numbers by popping a value from one stack and pushing to another
  • Used in Reverse Polish Notation
  • Stack frames used in subroutine calls

  
• Queues


  First in first out data structure
• Queue operations


  • Add – add element to the end of a queues
  • remove – remove element from front of queue
  • isEmpty – test to see if queue is empty
  • isFull – test to see if queue is Full
• Linear queue


  • As an item is removed from the queue all the other items move up one space. For a long queue this can take a lot of processing
• Linear queue using pointers


  • As an item is removed from the queue the pointer representing the start of the queue also moves up one
  • We need to know the length of the queue and how many elements have been removed
  • The problem is that we end up with a lot of empty cells in memory that are now unused at the front of the list
• Circular queue


  • Gets around the problem of unused memory locations at the front of the queue by "recycling" these memory locations
• Priority queue


  • Each element is assigned a priority
  • Highest priority items are removed first
  • If elements have the same priority then the item nearest the front of the queue is removed first
• Alternative priority queue


  • Stores items in priority order and the item removed from the front of the queue as with a linear queue
• Graphs


  • A way of representing the relation between data
  • Made up of vertices/nodes that are connected by edges or arcs

  
• Graphs do not need to be connected
• Weighted graph


  Adds a value to an arc, representing the distance between places or the time taken between train stations
• Adjacency matrix with no weighting


  • Graphs with no weights are given a value of 1 for connected nodes
• Adjacency matrix with weighting


  • Contains the weights between connected nodes
• Adjacency list with no weighting


  • Represents the connections between nodes
• Adjacency list with weighting


  • Represents the connections between nodes and the weights
• Directed graphs


  Connections only apply in one direction, represented with edges with arrow heads on one end
• Advantages of adjacency matrices vs adjacency lists


  • For sparse graphs, adjacency matrices have a lot of empty cells taking up more unused computer memory
  • Adjacency lists take longer to process so are slower
  • For sparse graphs where memory is a limiting factor, adjacency lists are preferable
  • For graphs with lots of edges, adjacency matrices are preferable
• Trees


  • Connected, undirected graphs with no cycles
  • Rooted trees have a root node with no parent and all other nodes descended from the root
  • Leaf nodes have no children
• Binary trees


  • Nodes can have a maximum of two child nodes
  • Can be used for sorting a sequence of numbers
• Tree data structure


  • Represented with three lists/arrays: one for node values, one pointing to left child, one pointing to right child
• The use of edge adjacency matrix is preferable
• Trees


  • Connected - Every node is connected either indirectly to directly to every other node
  • No Cycles – There is only one path between nodes
  • Undirected - can traverse in both directions along the edge
• Rooted tree


  Has a root node that has no parent and all other nodes are descended from the root. All other nodes can be a parent and/or a child node.
• Leaf node


  Has no children
• Binary Tree


  • A node can only have a maximum of two child nodes
  • Can be used for sorting a sequence of numbers
  • The first number is the root node
  • If the number is smaller than the node then we branch left if it is bigger we branch right
• Tree data structure


  • Represented with three lists/arrays: an array contains the values at the nodes, an array that points to the location of left child, an array that points to the location of right child
  • If a node does not have child node then this is indicated with a -1 or null
• Hashing


  Allows stored data to be accessed very quickly without the need to search through every record. This is achieved by relating the data itself to its index position using a key.
• Collisions


  Occur when a bin is already occupied. In such a situation the data are placed in the next available bin.