1.4.2 Data Structures Flashcards
1.4.2 A)
What is an array
And what are the different types of arrays
An ordered finite set of elements of a single data type.
A 1D array is an linear array always zero indexed
A 2D array can be like a table or spreadsheet you go up and down the toes then across the columns to find a given position
A 3D array can be a visualised as multiple 2D arrays example : print(array[x,y,z]) where x = the array number , y = row , z= column
1.4.2 A)
What is a record
A row in a file, made up of values from fields the variable must be declared
1.4.2 A)
What is a list
A data structure consisting of ordered items where items can occur more than once. They can contain multiple data types.
1.4.2 A)
How to access a list
Similar to 1D array in his they can be access, however values stored non contagiously meaning they don’t need to be next to eachother In memory
1.4.2 A)
Operations of a list
IsEmpty()
Append(value)
Remove(value)
Search(value)
Length()
Index(value)
Insert(pos,value)
Pop()
Pop(pos)
1.4.2 A)
What is a tuple?
An ordered set of values of any types. It’s immutable which means cannot be changed elements can’t be added or removed once it’s created.
Attempting to add or remove will cause an error
1.4.2 B)
What is a stack
What is a stack used for
Last in first out (LIFO) data structure.
Used as a undo / reverse action
1.4.2 B)
What are the two types of stacks
Static or dynamic
If max size required is known in advance use static as it’s easier to implement and make more efficient use of memory.
1.4.2 B)
How are stacks implemented
Using a pointer which check top of the stack where next piece of data will be inserted
1.4.2 B)
What are the operation of a stack
IsEmpty()
Push(value) - adds a new value to end of list need to check list is not full
Peek() - returns top value make sure stack isn’t empty
Pop() same as peek but removed value
Size()
IsFull()
1.4.2 B)
What is a queue
First in first out (FIFO) data structure
1.4.2 B)
What are queues used for
Printers linear queue consisting of an array
1.4.2 B)
How is data added / removed from a queue
Items added to the next available
Space starting from the front. Items are removed from the front. Used two pointers one at front and one at back.
1.4.2 B)
What makes linear queues ineffective
As items are removed address cannot be reused in efficient use of space
1.4.2 B)
How can queues become more efficient
Circular queues.
When the rear pointer = max size of the array it can be looped around to the front of the array uses space more efficiently but harder to implement
Only works if front of queue is empty