1.4.2 Data Structures Flashcards
What is an arrary?
A data structure for storing a finite, ordered set of data of the same data type within a single indentifer
What are 3 features of arrays
- Static
- Ordered, made up of elements which each have an index (starting from zero)
- Stored contiguously in memory
How do you count the numbers of elements in an array?
length = len[array_name]
How do you define an array?
array_name = [“firstelement”,”secondelement”,”thirdelement”]
How do you update a value in an array?
array_name[2] = “2nditem”
How do you output a value from an arrary?
print(arrary_name[2])
What is a 2D array?
Can be visualised as a table or spreadsheet. Arrays inside of an array.
How do the indexes work in a 2D array?
array_name[row,column]
The row is called first then the column
What are 3D arrays?
A 3D array can be visualised like a pile of 2D arrays.
Think of a stack of spreadsheets.
How do the indexes work in 3D arrays?
array_name[row, column, depth]
What is a tuple?
A data structure for storing an immutable, ordered set of data, which can be different data types within a single identifier.
What does immutable mean?
Cannot be modified morethan once
What are 4 features of a tuple?
Mixed data types
Fixed size
Ordered
Immutable
What is a list?
A data structure that stores a sequence of data values, each with a unique index
What are 4 features of lists?
Ordered
No predefined scope - dynamic
Multiple data types
Stored non-contigously
Why are lists easy to initalise?
There is no need to define attributes in advance.
What is a record?
A data structure that stores data in elements called fields, organised based on attributes
What are 3 attributes of records?
Stores multiple values under one identifier
Can hold different data types
Unordered
Why are collections of records usually stored in an array?
So they can be accessed using an index
print(array_name[0].sort)
Which operation checks if a list is empty?
.isEmpty()
Which operation adds a new value to the end of a list?
.append(value)
Which operation removes the value the first time it appears in the list?
.remove(value)
Which operation searches for a value in the list?
.search(value)
Which operation returns the length of the list?
.length()
Which operation returns the position of the item in a list?
.index(value)
Which operation inserts a value at a given position in a list?
.insert(position,value)
Which operation returns and removes the last value in a list?
.pop()
Which operation returns and removes the value in the list at the given position?
.pop(position)
What is a stack?
Last in first out data structure (LIFO)
Uses one pointer to point to the top of the stack
Where are stacks used?
Web browser history
Undo buttons
How do you add a item to a stack?
Push
How do you remove the top item from a stack?
Pop
How do you return the value at the top of stack without removing it?
Peek
What are the 2 possible errors you could get when pushing/popping?
Popping an item from an empty stack will produce an underflow error
Pushing an item onto a full stack will produce an overflow error
What is a queue?
A first in first-out data structure (FIFO)
Uses two pointers, one to store the location of the front of the queue and one to store the location of the back of the queue.
Where are queues used?
Printer queues
Keyboard buffers
How can you add an item to the back of the queue?
Enqueue
How can you remove an item from the front of the queue?
Dequeue
How can you output the item from the front of the queue without removing it?
Peek
What are the 2 possible errors you can get when dequeuing/enqueuing?
Dequeuing an empty queue will produce an underflow error
Enqueuing a full queue will produce an overflow error
What is a circular queue?
Circular queues use arrays to make the front of the queue attached to the end of the queue