SLR14 - Data Structures

Static/Dynamic

• Refers to size

• Static - Can’t change size once set up

• Dynamic - Can change size once set up

Mutable/Immutabe

• Refers to data contained

• Mutable - Can change once created

• Immutable - Can’t change once created

One dimensional arrays

• Eg: countries = [“Angola”, “Austria”, “Belgium”]

• Sets up one dimensional array called countries

• Index starts 0

• Static structure

• Mutable

Two dimensional array

• Can visualise as table with two sets of index

• Eg: Countries[0][0] is an item location

Record data structure

• Can store multiple values under one identifier

• The data can be of different data types

• Field - variable, each field in record can have different data type

steps to use record data structure

1. Define record structure - what field will be in record

2. Declare variable or array to use within record structure

3. Assign & retrieve data from variable record

Lists

• Mutable

• Can store more than one data type

• []

Array

• Mutable

• Item can be changed or replaced

• Store only one data type

• Allocate contiguous(stored together, simultaneously) parts of memory

• []

Tuple

• Immutable - item cannot be changed or replaced

• Can store more than one data type

• ()

Stacks

• Data structure where items pushed on top of stack when added to it and popped off top when deleted

• Last in first out - LIFO

Stack pointer

Points to top item

How are stacks implimented

Often using an array but can also be created using object orientated techniques

What are applications of stacks

• Used by processor to track flow of program

• When sub-routine called

• Used for:

  • Keep track of user inputs for undo operations

  • Backtracking algorithms

Operations that can be performed on a stack

• Push: add item to top

• Pop: Remove item from top

• Peek: Returning value from the top of stack without remove it

Queues

• Linear data structure

• Items are enqueued at back of queue & dequeued from front

• First in first out -FIFO

• Dynamic

How queues implemented

Queues can be implemented using array or object oriented technique

Circular queue

• Implemented when using queues with arrays to prevent running out of space

• Cycles back to pointer to front of array when reached end

Applications of queue

• process scheduling

• Transferring data between processors & printer spooling

• Performing breath-first searches on graph of data structure

Operations that can be performed on queue

• Enqueue: adding item to back of queue

• Dequeue: removing item from front of queue

• Peek: returning value from front of queue without removing it

Linked list

• Start pointer identifies first node

• Each node contains data & pointer to next node

• By manipulating links can grow, shrink, re-arrange data - dynamic

Implementing linked list using array

• Arrays are static data structures

• Stored contiguously in memory

• Need an index register to determine where a specific index is in relation to a base address

Implementing linked list using objects

• Any available memory address can be used - doesn’t need to be adjacent

• Dynamic

Linked list applications

• Image viewer to switch between previous & next image

• Music player to store music in playlist

• Web browser navigate forwards & backwards

• Hash table collision resolution as overflow

Linked list operations

• Add

• Delete

• Next

• Previous

• Traverse - linear search through linked list

Graph

• Data structure consisting of nodes/vertices and edges where each node can have more than two edges and can point to any vertex

• Edges can point in one direction or not specify a direction

Graph implementation

• Can store as objects or using dictionary, known as adjacency lists

• Can also store using array, known as adjacency matrix, with rows & columns representing vertices & edges

Graph applications

• Mapping road networks for navigation system

• Storing social network data

• resource allocation in OS

• Representing molecular structures & geometry

Graph operations

• Adjacent - returns whether there is an edge between two vertices

• Neighbours - returns all vertices between two vertices

• Add ( vertex)

• Remove (vertex)

• Add edge

• Remove edge

• Get vertex value

• Set vertex value

• Get edge value

• Set edge value

Search operations

• Depth-first-search

• Bread-first-search

Traversal operations

• Pre-order traversal

• In-order traversal

• Post-order traversal

Tree

• Consists of nodes where each node contains data and number of pointers

• Organised in root & leaf structure

• Root node at top, has zero or more leaf nodes coming off it

Tree applications

• Folder structure

• Implementation of A* pathfinder program

• storing & manipulating any form of hierarchal data that requires parent node to have zero or more child nodes eg. family tree

Binary tree

• Similar to standard tree however, each node can only have up to 2 pointers to another node

Binary tree implementation

• Essentially a graph

• can be represented in memory with dictionaries

• Or can be stored as array

• Commonly represented as objects - nodes with left & right pointers

Binary tree applicaiton

• Database applications where efficient searching & storing is required without moving items

• Wireless networking & router table

• Operating system scheduling processes

Binary tree operations

• Add

• Delete

• Binary search - returns data stored in node

• Pre-order traversal

• In-order traversal

• Post-order traversal (types of depth-first search)

Hash table

Hash function applied to item to determine a hash value - its position in the hash table

Hash table usually larger that needed to minimise chance of algorithm returning same value for more than one item - collision

Properties of a good hashing function

• Calculates quickly

• Results in as few collisions as possible

• Uses as little memory as possible

Resolving collsions

• Open addressing

• Two dimensional hash table

• Overflow table

Open addressing

• An approach to resolve hashing

• Repeatedly check next available space in hashing table until empty position

• To find later, hashing function returns tarting position, from here linear search until item found - linear probing

• Disadvantage - prevents other items from being stored in correct location

Hash table applications

Used in situations where items in large data set need to be found quickly:

• File system linking file name to path of file

• Identifying keywords in programming language during compilation

Hash table operations

• Add

• Delete

• Retrieve

Adding item to linked list

1. Check if free memory for new node - error if not

2. Create new node & inset data / insert data into node indicated by free storage pointer

3. If linked list is empty:

   • New node becomes first item & create start pointer to it

4. If new node should be placed before first node:

   • New node becomes first node

   • New node point to second node

5. if new node is to be place inside linked list:

   • Start on first node

   • If data in current node is less than value of new node:

     • Follow pointer to next node

     • Repeat from step 5b until correct poison found or end reached

   • New node is set to point where previous node pointed

   • Previous node set to point to new node

6. Update free pointer to next available storage space

Deleting item to linked list

1. Check if linked list is empty - error if is

2. if first item is item to delete, set start pointer to next node

3. If item to delete is inside:

   • Start first node

   • If current node item to delete:

     • Previous node’s pointer is set to point to next node

   • Follow pointer to next node

   • Repeat from step 3b until item found / end reached

4. Update free pointer

Traversing linked list

1. Check linked list is empty

2. Start at node the start is pointing to

3. Output item

4. Follow pointer & next node

5. Repeat from step 3 until end of linked list reached

Adding & removing item to graph

Need to use graph traversal algorithm to find a specific node where the connections is being added

Breadth-first search

• Makes use of queue

1. Set root node as current node

2. Add current node to list of visited nodes if not already in list

3. For every edge connected to the node:

   • If linked node is not in visited list:

     • Enqueue the linked node

     • Add linked node to visited list

4. Dequeue & set node removed as the current node

5. Repeat from step 2 until queue empty

6. Output all visited nodes

Depth-first search

• Makes use of stack

1. Set root node as current node

2. Add current node to visited nodes

3. For every edge connected to node:

   • If connected node is not in visited, push connected node onto stack

4. Pop stack & set removed item as current node

5. Repeat form step 2 until no nodes left to visit

6. Output all visited nodes

Adding item to stack - push

Array

1. Check for stack overflow - output error if stack full

2. Increment stack pointer

3. Insert new data item at location pointed to by stack pointer

Object

• Stack is dynamic with enough memory with this approach

1. Check for stack overflow - output error if no free memory

2. Create new node & insert data into it

3. New node point to previous node

4. Stack pointer is set to point to new node

Adding item to queue - enqueue

Array

1. Check for queue overflow - output error if queue full

2. Increment tail pointer

3. Insert new data item at location pointed to by tail pointer

Object

1. Check for queue overflow - output error if no free memory

2. Create new node & insert data into it

3. Back pointer is set to the new node

4. If this is the first in the list, the front pointer is set to point to the new node

Removing item form stack - pop

Array

1. Check for stack underflow - error if stack is empty

2. Copy/output data item pointed to by pointer

3. Decrement the pointer

Object

1. Check for stack underflow - ouput error is stack pointer doesn’t point to node

2. Output node pointed to by stack pointer

3. Set stack pointer to previous item

Removing item form queue - dequeue

Array

1. Check for queue underflow - error if queue empty

2. Copy/output data item pointed to by head pointer

3. increment head pointer

Object

1. Check for queue underflow - error in front pointer doesn’t point to node

2. Output node pointed to by front pointer

3. Set front pointer to previous item

Adding item to binary tree

1. Check there is free memory for new node - output error if not

2. Create new node & insert data into it

3. If tree empty:

   • New node become first item - create start pointer to it

4. if not empty:

   • Start at root node

   • If new node should place before current node, follow left pointer

   • If new node should be placed after current node, follow right pointer

   • Repeat form step 4b until leaf node reached

   • If new node should be place before current node, set left pointer to be new node

   • If new node should be placed after current node, set right pointer to new node

Removing item from binary tree

1. Start at the root node & set it as current node

2. While current node exits and it is not the one being selected:

   • Set previous node variable to be same as current node

   • If item to be deleted is less than current node, follow left pointer and set discovered node as current node

   • If item to be deleted is greater than the current node, follow the right pointer and set discovered node as current node

Deleting node that has no children

1. If previous node is greater than current node, previous node’s left pointer set to null

2. If previous node is less than current node, the previous node’s right pointer set to null

Deleting node that has one child

1. If current node is less than previous node:

   • Set previous node’s left pointer to current node’s left child

2. If current node is greater than previous

   • Set previous node’s right pointer to current node’s right child

Deleting node that has two children

1. If right node exists and has left sub-tree, fins the smallest leaf node in the right sub tree:

   • Change current node to the smallest leaf node

   • Remove the smallest leaf node

2. If right node exists and has left sub-tree:

   • Set current node to be the current node’s right pointer

   • Set current node’s right pointer to null

Pre-order traversal

1. Start at root node

2. Output node

3. Follow left pointer and repeat from step 2 recursively until no pointer to follow

4. Follow right pointer and repeat from step 2 recursively until no pointer to follow

In-order traversal

1. Start at root node

2. Follow left pointer and repeat from step 2 recursively until there is no pointer to follow

3. output

4. Follow right pointer and repeat from step 2 recursively until there is no pointer to follow

Post-order traversal

1. Start at root node

2. Follow left pointer and repeat from step 2 recursively until no pointer to follow

3. Follow right pointer and repeat from step 2 recursively until no pointer to follow

4. Output node

Adding item to hash table

1. Calc position of item in hash table using hash function

2. If position empty, insert item and stop

3. If position not empty, check first position in overflow table

   • If empty, insert and stop

   • Increment position to check in overflow table

   • Repeat from step 3a until item inserted of overflow table full

Removing item to hash table

1. Calc position of item in hash table using hash function

2. if calculated position contains item to be deleted, delete it and stop

3. If not, check first position in overflow table

   • If contains item to be deleted, delete it and stop

   • Increment position to check in overflow table

   • Repeat from step 3a until item to delete discovered or end of overflow table reached

Traversing hash table

1. Calc position of item in hash table using hash function

2. Check if item in that position is item to be found

3. If calculated position doesn’t contain item to be found, move to first position if in overflow table

   • Check if item in that position is item to be found

   • If it is not, increment to next position in overflow table

   • Repeat from step 3a until item found or end of overflow table reached

4. If item found, output item data, if not output “not found”