SLR 14 Data Structures

define array

define array

static data structure that allocates contiguous parts of memory to store data of only 1 data type

state a difference between lists and arrays

• lists don’t store data continuously, arrays do

• lists are dynamic, arrays are static

define record

collection of relation fields (variables) with different data types

define linked list

• dynamic data structure

• made of nodes and pointers

• each pointer gives the location of the next node

define tuple

static data structure that is immutable and stores multiple data types

describe how to add a node to a linked list

• check there is space to add a node

• create the node, if its first node then give it start pointer

• if not, check if it’s greater than first node, if so then set it

• if not then move to next node and repeat until no nodes left

• update free pointer to next available storage space

describe how to remove node from linked list

• check if list is empty, if so display error

• if item to delete is first node, set pointer to next node

• if not, start at first node and check if current node is item to delete

• if so, delete it, if not set previous pointer to next node, and follow pointer to check and repeat again

• update free pointer

define graph

dynamic data structure made up of nodes and edges

what are the 2 ways a graph can be implemented

adjacency list (dictionary) and adjacency matrix (array)

state 3 uses for graphs

• social networks, storing data in social media networks

• transport networks, mapping road networks for navigation systems

  • operating systems, resource allocation

explain a breadth-first search on a graph

• uses queue data structure

• set root node as current node and add to list of visited nodes

• add any connected nodes to the queue from left to right

• add to list of visited nodes and dequeue

• repeat until queue is empty

• output all visited nodes: dunkirk, bolton, moulton, hartlepool, frogmore, teesside, cardiff

• better for searching for nodes closer to source node

explain a depth-first search on a graph

• uses stack data structure

• set root node as current node and add to list of visited nodes

• pick a connected node and if it’s not already on list of visited nodes then push onto stack

• repeat for any nodes connected to current node

• output all visited nodes: dunkirk, bolton, frogmore, moulton, hartelpool, teesside, cardiff

• better for when decision is made and fully explored before moving on

define stack

static + LIFO data structure where last item pushed on is first to be popped off

explain how to push onto a stack using OOP

1. check if stack is full, if so display error message

2. if not, create new node and insert data

3. new node should point to previous node

4. stack pointer is set to point at new node

explain how to pop a stack in OOP

1. check if stack is empty, if so display error message

2. if not, output node pointed to by stack pointer

3. set stack pointer to previous node

define queue

FIFO data structure with pointers where first item to be queued is first to be dequeued

state and explain the 3 types of queues

1. linear queue

   • array where items are added to next available space and removed from front

2. circular queue

   • static array with fixed capacity

3. priority queue

explain how to enqueue in OOP

1. check if queue is full, if so output error message

2. create new node and enter data

3. back pointer is set to point to new node

4. if this node is also the first, front pointer should point to it too

explain how to dequeue in OOP

1. check if queue is empty, if so output error message

2. if not, output node pointer by front pointer

3. set front pointer to previous term

define tree

data structure with root, child and leaf nodes, sub trees and pointers

what are 3 uses of trees

1. managing folder structures

2. wireless networking and router tables

3. cryptography

state the difference between trees and binary trees

• in binary trees a node can have no more than 2 child nodes

explain how to add data to a binary tree

1. check if there is memory space for a new node, if not display error message

2. create new node and insert data

3. if binary tree is empty, new node = root node

4. if not, check if value of new node is greater than root node

5. if yes, go right, otherwise go left and repeat

explain how to remove data from a binary tree

1. search for node you want to remove

2. if node has no children, just remove from tree

3. if node has 1 child, replace node with child

4. if not has 2 children, replace with right child node

explain pre-order traversal on a binary tree

1. start at root node

2. output node

3. follow left pointer and output until none left

4. follow right pointer and output until none left

(full goes down 1 path before moving on)

jenny, alfie, aaron, paul, lauren, robert, sarah

explain in-order traversal on a binary tree

1. start at root node

2. follow left pointer until none left

3. output node

4. follow right pointer until none left

(outputs all left branches from the bottom first)

aaron, alfie, jenny, lauren, paul, robert, sarah

explain post-order traversal on a binary tree

1. start at root node

2. follow left pointer until none left

3. follow right pointer until none left

4. output node

(outputs left branches, then right, then root node)

aaron, alfie, lauren, paul, robert, sarah, jenny

define hash table

data structure where hashing algorithm is used to release a value that maps the key to an index in a table

state the 3 qualities of a good hash function

• quick calculations

• minimal collisions

• minimal use of memory

state and explain the 2 ways to solve collision

1. linear probing

   • data is placed in next free position in hash table with is found by probing sequentially or via interval (e.g. every 3rd slot)

2. chaining

   • use linked lists to store more than one item in the same memory space

explain how to add data to a hash table

1. hash function generates index of position in array

2. check if position is empty, if so insert item and stop

3. if not, check first position in overflow table, if its empty insert item and stop

4. if not, increment position and repeat until space is found

explain how to remove an item from a hash table

1. hash function generate index for position within array

2. if position has item, delete and stop

3. if not, check first position in overflow table, if this is it delete and stop

4. if not, increment position until item is found and delete

(exactly same as traversing)