1.4.2 - data structures Flashcards
7
one dimensional array
A finite, ordered set of elements of the same type stored in contiguous memory.
Does row or column come first in 2D array?
row
tuple
An immutable, ordered set of values of any data type.
immutable
Its elements cannot be changed and you cannot dynamically add or delete elements from a tuple.
record
Contains a number of fields, each holding one item of data.
list
A contiguously stored data structure consisting of a number of ordered items where the items can occur more than once.
list.isEmpty()
Test for an empty list.
list.append(item)
Adds item to the end of a list.
remove(item)
Removes the first occurrence of an item from a list.
search(item)
Return whether an item exits in a list or not.
list.length()
Returns number of items in a list.
list.index(item)
Returns the position of item.
list.insert(position, item)
Insert a new item at position.
list.pop()
Remove and return the last item in the list.
list.pop(position)
Remove and return the item at position.
linked list
A dynamic data structure used to hold an ordered sequence not necessarily in contiguous data locations.
What is each item in a linked list called?
a node
2 parts of a node and their explanation
- data field: actual item
- pointer field: contains address of next item in sequence.
null pointer in a linked list
Used to identify the last item of data.
List 4 operations that can be carried out on queues.
1- enQueue()
2- deQueue()
3- isEmpty()
4- isFull()
3 uses of queues
- storing print jobs until the printer is ready to print
- CPU scheduling
- breadth first traversal of a graph
linear queues
When an item of data is removed from the front, all the other items move up one place. This is only suitable in a small queue, otherwise data processing time can be excessive.
circular queues
When an item of data is removed from the front, the two pointers have to be updated to identify the new front and rear of the queue.
2 uses of graphs
- locations on a map
- products on an e-commerce website
