unit 7 Flashcards
what is an array?
an array is an ordered static set of elements that can only store data type
what is a 2D array?
what is a record?
a row in a file made up of fields
what is a list?
a dynamic data structure that consists of a number of items where the items can occur more than once
they can contain elements of different data types
what are the operations in a list?
isEmpty()
append(value)
remove(value)
length()
index(value)
insert(p,v)
pop()
what is a tuple?
a tuple is an ordered set of values of any type
immutable = cannot be changed, after creation
what is a linked list?
a dynamic data structure that is used to hold an ordered sequence
items do not have to be in contiguous data locations
each item is a node which contains a data field alongside another address is called a pointer
how does a linked list work?
data field contains the value of the actual data
pointer field contains the address of the next item in the list
linked lists also store the index of the first item as a pointer
also store a pointer identifying the index of the next available space
what are the steps to traverse a linked list?
check if list is empty
start at the node the pointer is pointing to
output the item at the current node
follow the pointer to the next node repeating through each node
when the pointer field is empty it means the end of the linked list has been reached
how do you add a node in a linked list?
check if there is space to insert data
add the new value to the end of the linked list and update the next pointer
how do you remove a node in a linked list?
update the pointer field of the item pointing to the node you want to delete
it should point to the node after the deleted node
the node pointing from the deleted node to the next node is then ignored (this wastes memory)
what is a stack?
LIFO data structure
items only added or removed from the top of the stack
static ds
what are the operations in a stack?
isEmpty()
push(value)
peek()
pop()
size()
isFull()
how does a stack use pointers?
uses a pointer to point to the top of the stack where the next piece of data will be added or current is removed
pointer then + 1
what is stack overflow?
attempt to push an item onto a full stack
what is stack underflow?
attempt to remove an item from an empty stack
pointer then - 1
what is a queue?
a FIFO data structure
items are added to the end and removed from the front
how does a queue work?
has a front and rear pointer
track the position of the front and back of the queue
what are the 3 types of queue?
linear
circular
priority
what are the operations in a queue?
enQueue(value)
deQueue()
peek()
isEmpty()
isFull()
what are linear queues?
a data structure that consists of an array
items added to the next available space in the queue starting from the front
what are circular queues?
a static array that has a fixed capacity
space is freed up at the start of the array
reuses empty slots at the front as the rear pointer wraps round to point to the start
what is a graph?
a set of nodes that are connected by edges
what are the different types of graphs?
directed
undirected
weighted
