Flashcards in Data Structures Deck (72)
An array allows you to store multiple items of the same data type under a shared common name.
Arrays can store data of the same data type contiguously in memory. This means...
... random access to all element is available via its direct index.
Limitations of arrays:
- They can only store one data type
- They’re a static data structure (their scope is pre-determined)
an un-ordered data structure which is accessed through an attribute. It can store many different data types.
What are pythons versions of arrays?
Lists and tuples
Tuples are lists that cannot be edited and is said to be immutable.
structure and data cannot be changed at run time.
structure and data can be changed at run time.
Static data structure
size of the structure cannot change at run time
Dynamic data structure
size of the structure can change at run time.
Stack data structure
A stack is known as a LIFO, a single pointer is used to point to the top item of the stack, when a new item is pushed onto the stack the pointer is incremented. When an item is popped off the stack the pointer decrements to point to the new top of the stack.
last in first out - the last item you push to the top of the list is the first item you pop off the stack.
Queue data structure
A queue is known as a FIFO structure. A pair of pointers is used to point to the front and back of the queue. If an item is popped from the queue the front pointer points to the item being popped. If an item is pushed onto a queue the tail pointer increments by one and points to the new end of queue.
first in first out - because the new items get pushed to the back of the queue and new items get popped from the front of the queue.
Algorithm for insertion into a stack:
1. Check to see if the stack is full
2. If the stack is full report error and stop
3. Increment the stack pointer
4. Insert new data item into location pointed to by the stack pointer and stop
Algorithm for deletion/fetching from a stack:
1. Check to see if the stack is empty
2. If the stack is empty report an error and stop
3. Copy the data item in location pointed to by the stack pointer/ delete the data item
4. Decrement the stack pointer
Algorithm for insertion into a queue:
1. Check to see is the queue is full
2. If the queue is full report an error ad stop
3. Insert new data item into location pointed to by the head pointer
4. Increment the head pointer and stop
Algorithm for deletion/fetching from a queue:
1. Check to see if the queue is empty
2. If the queue is empty report an error and stop
3. Copy data item in location pointed to by the tail pointer/ delete the data item
4. Increment tail pointer and stop
A list of data together with a set of links to sort the data. Data is stored in the order its input and pointers are used to link the data into the desired order.
uses of linked lists
1. Implementing undo functionality
2. Dealing with browser cache
3. Helping with operating system job queues
Adding data from linked lists:
1. Store the data at the location indicated by the free storage pointer
2. Alter the free storage pointer to the next free storage space
3. Set the pointer for the item that will precede it to the new data item
5. Update the pointer for the new data item to that previously stored in the item the preceded it (i.e. the next data item)
Removing data from linked lists:
1. If the item to remove is in the first position
a. Then update starting pointer value of item you want to delete and update all the pointers
2. Else if the item is in any other position
a. Update the pointer value in the preceding node from the one you want to delete to the value of the pointer in the item to be removed and all the succeeding data items pointers
3. Update the free storage
Traversing data from linked lists:
1. Set the pointer to the start value
a. Go to the node
b. Output the data at the node
c. Set the pointer to the value of the next item pointer at the pointer
d. until pointer = 0/null
Searching for an item in a linked list:
1. Set the pointer to the start value
a. Go to node (pointer value)
b. If the data at the node is the search item
i. Then Output the data and stop
i. Set the pointer to the value of the next item pointer at the node
d. Until pointer = 0
3. Output data not found
Benefits of Hash tables
Speed of lookup, deletion and insertion of items is fast
an array which is coupled together with a hash function. The value from the hash function (hash value) maps the initial key to a fixed index in the hash table.
the same hash value is given by two different keys.
- Storing the key in the next available space
- adding a linked list to the location where the hash value is repeated
when there is a collision and the key is stored in the next available space increasing the likelihood of collisions.