Data Structures and Data Manipulation Flashcards
Data Structure
Is a group of related data items.
Static Data Structure
Are those where the size is fixed when the structure is created (the size cannot change during processing).
Dynamic Data Structure
Are those where the size of the data structure changes as data is added and removed.
Static vs Dynamic
Static - amount of storage required known so easier to program. Dynamic - amount of storage not known more complex code.
Stack
LIFO. A stack is a list in which insertion and deletion take place at the same end (TOP). One pointer – top.
Stack - uses
Storing return addresses (during subroutine calls), Passing parameters, Storing contents of registers while processing interrupt
Reversing the order of a set of data.
Stack overflow/underflow
Overflow error when try to push an item onto a full stack and Underflow when try to pop item off empty stack.
Stack – insert algorithm
Push item onto stack
If Stack is full Then Error and stop Else Increment StackPointer. Add data item at position StackPointer End if.
Stack – retrieve/delete alg
Pop item off stack
If Stack is empty Then Error and stop Else Return the data item at position StackPointer. Decrement StackPointer End if.
Queue
FIFO. A queue is a list. Insertion is done at one end, while deletion is performed at the other end. Front and back pointers.
Q overflow/underflow
Overflow error when try to enqueue an item onto a full queue and Underflow when try to dequeue item off empty queue.
Queue - uses
Jobs waiting for a printer in a spool queue, Job queue batch processing system, Keyboard buffer.
Shuffle queue
Front index always fixed (items shuffle up to front when an item is dequeued.
Circular queue
When enqueuing next index moves forward. When dequeuing the front index moves forward. Circular as next pointer wraps to beginning once last index is reached.
Queue – insert algorithm / add item to circular queue
(Enqueue). If Queue is full Then Error and stop Else Add data item at position NextPointer. Increment NextPointer. If NextPointer > MaxIndex Then Assign the value of 1 to NextPointer End if.
Queue – retrieve/delete
from circular queue
(Dequeue). If Queue is empty Then Error and stop Else Return the data item at position FrontPointer. Increment FrontPointer. If FrontPointer > MaxIndex Then Assign the value of 1 to FrontPointer End If End If.
Tree
Tree is represents the relationship between data items. (Stack and queue don’t imply relationship between data items).
Tree - uses
Binary search tree - storing data in such a way that it makes it easy and fast to search. Representing sorted lists of data.
Most databases use this tree concept as the basis of storing, searching and sorting it’s records.
Tree – insert algorithm
add item to a tree
Start at root. REPEAT IF new data
Tree – retrieve algorithm
Start at root. WHILE pointer is not Null DO IF current data = required data THEN RETURN current data ELSE IF required data
Tree – delete algorithm
Deletion is more tricky as simply deleting a node could detach child nodes from the tree. Deletion could be done in the following ways: Mark the node deleted but leave in tree to maintain structure. OR Re-attach any child nodes to the tree
Binary Search
The binary search is more efficient than the linear search, but requires the data to be in order.
Binary Search Alg
1) Look at the item at the midpoint of the list (the current item). 2) If the current item is the item sought, then it has been found. 3) If the current item is not the item sought, discard the half of the list that can’t contain the item sought and repeat the same method with the other half of the list. 4) Keep repeating these steps until the item is found or the list contains no items.
Binary Search Adv
Usually faster because half of the data is discarded at each step and fewer items checked. This is more efficient for large files.
