[Unit 1.4.2] Data Structures Flashcards
data structures
define “data structure”
collection of data organised for efficient processing
define “primitive data types”
single values (integers/floats)
define “compound data types”
combine primitive data types (records/dates)
what is a linear data structure
ordering data in a sequential order. each element is connected to the one before and after.
what is a non linear data structure
data organised with a hierarchy like a family tree
what are the two types of linear data structures
static:
fixed size, change content. memory allocated at compiler time
Dynamic:
change size, change content. memory allocated during run time as needed.
what are records
data structures consists of fixed number of attributes (fields/columns)
three similarities between records and OOP
-bundle related properties together
-define attributes (to manipulate data)
-can have multiple instances
four differences between records and OOP
-record is data structure. class is template for data structure
-classes have methods
-classes can change visibility of properties
-classes have inheritance
what are the features of an array
same data type
static
stored contiguously
mutable
what are the features of a list
different data types
dynamic
stored contiguously
mutable
what are the features of a tuple
different data types
static
immutable
what are the features of a linked list
dynamic
data does not have to be stored contiguously
each item is called a node
what two features is a node comprised of
data and pointer
what is the pointer in a node
contains the address of the next node
what does it mean if a pointer is null
end of linked list
node not linked to another (if one has been deleted)
what is the head pointer (linked lists)
points to location of first node
what is the free space pointer and what does it mean if it is null (linked lists)
indicates next free element (if null then list is full)
what is the tail pointer (linked lists)
indicates location of last node
what are the three types of linked lists
single linked
doubly linked
circular linked
what is a single linked list
navigation is forwards only
what is a doubly linked list
navigation can be forwards or backwards
(must have two pointers (previous&next))
what is a circular linked list
last node links to first node.
can be single linked or doubly linked.
differences between array and linked list (4)
accessing data faster in array
uses less memory per item in array
array is static data structure
slow to add/remove data in array
how do you add a node to a linked list
-check free storage pointer is not NULL
-traverse list to free node and add data
-update pointer of previous node to new item
-update pointer of new item to same as previous node used to point to
-if list was empty update head pointer
-update free storage pointer to next free location
how do you delete a node from a linked list
-check if list is empty (output error if yes)
-traverse to node of item to delete
-update pointer of deleted node to NULL
-update previous node pointer to same as deleted item was
-if deleted node was the first. update head pointer
-update free storage pointer if required
how do you traverse a linked list
-check if list is empty (error if yes)
-begin at node of head pointer
-print
-follow pointer to next node
-repeat until pointer is NULL (end of list)
what is a queue
linear data structure that stores elements sequentially.
what does FIFO stand for?
first in first out
what are the two main operations performed on queues
enqueue (add to end)
dequeue (remove from start)
what are the two types of pointers in a queue
front/head
back/rear/tail
what happens if you enqueue a full queue
queue overflow error
what happens if you dequeue an empty queue
queue underflow error
what are some real life uses of queues
print queue
CPU scheduling
modelling situations like traffic jams
why are linear queues inefficient
they run out of space quickly. you could shuffle up each item after dequeue but this is inefficient and takes time on longer queues
what is a circular queue
front and rear end are connected
requires less memory
more efficient
what is a priority queue
each element has a priority
how does a priority queue work
when you add element. it is inserted ahead of lower priorities, but behind equal or higher priorities.
how do you enqueue an item
check if queue is full
-print error message if it is
increment rear pointer by 1
add element to location of rear pointer
how do you dequeue an item
check if queue is empty
-print error message if it is
take item at location of front pointer
increment front pointer by 1
how do you enqueue an item in a circular queue
check if queue is full
-print error message
change rear pointer to (rear +1) MOD maxsize of queue
add element to location of rear pointer
how do you dequeue an item in a circular queue
check if queue is empty
-print error message
take item at location of front pointer
change front pointer to (front + 1) MOD maxsize of queue
what is a stack
linear data structure, stores elements sequentially
a stack is a LIFO. what does LIFO mean
Last in first out
is a stack: static or dynamic?
it can be static or dynamic
what does push() do
add item to top of stack
what does pop() do
remove item from top of stack
define “stack overflow”
when you try to push() a full stack
define “stack underflow”
when you try to pop() an empty stack
what are stacks used for
reversing order of set of data items
used for calculations
used for handling interrupts.
how do you push a stack
check if stack is full
-print error message
increment top pointer by 1
add element to location of top pointer
how do you pop a stack
check if stack is empty
-print error message
take element from location of top pointer
decrease top pointer by 1
what are the features of a tree data structure
non linear
data represented hierarchically
nodes connected by edges
each tree has a root node
define “node”
fundamental element of tree. contains data. may link to another node
define “root” in terms of a tree data structure
top most node in tree.
no parent
define “parent” in terms of a tree data structure
node has one or more child nodes
define “child” in terms of a tree data structure
node that descends from another node
define “leaf” in terms of a tree data structure
node with no children
define “edge” in terms of a tree data structure
connection between two nodes.
may also be called a pointer
define “subtree” in terms of a tree data structure
tree formed by a node and its descendants
define “binary tree”
special rooted tree where every node has, at most, two child nodes
define “Binary search tree” (BST)
binary tree where nodes are ordered allowing for efficient searching
what are the properties of a binary search tree
- nodes of left subtree are less than root node
- nodes of right subtree are more than root node
- each subtree is also a BST, has the same properties
what are the 3 things in every binary tree
data
left pointer
right pointer
what are the two types of tree traversal
depth first
breadth first
what are the three types of depth first tree traversal
pre-order
post-order
in-order
how does pre order tree traversal work
visit root node
traverse left subtree recursively in pre-order
traverse right subtree recursively in pre-order
how does post order tree traversal work
traverse left subtree recursively in post-order
traverse right subtree recursively in post-order
visit root node
how does in-order tree traversal work
traverse left subtree recursively in in-order
visit root node
traverse right subtree recursively in in-order
define backtracking
undoing a step, returning to previous node after exploring all possible paths from the current node
how does breadth first tree traversal work
visit each node level by level
typically left to right
how do you insert an item into a binary search tree
- check if full, output error if so
- create new node with required data
- if binary tree is empty the new node becomes first item. create start pointer
- if it isn’t empty:
- start at root
- if new node is less follow left pointer
- if new node is more follow right pointer
- repeat until pointer is null
- if it is less set left pointer to new node
- if it is more set right pointer to new node
how do you delete a leaf node in a binary search tree
- check if node to be removed is less or more than parent
- if less change left pointer of parent to null
- if more change right pointer of parent to null
- add deleted node to free storage list
how do you delete a node with one child in a binary search tree
- check if node to be removed is less or more than parent
- if less, update parent left pointer to point to only child
- if more update parent right pointer to point to only child
- add deleted node to free storage list
how do you delete a node with two children in a binary search tree
- find smallest value in right subtree and swap with deleted node
- if there are no left nodes in right subtree, upshift subtree by one
- delete leaf node (the new one that was swapped)
- add deleted node to free storage list
