Help
Options
Didn't know it?
click below
click below
Knew it?
click below
click below
Don't Know
Remaining cards (0)
Know
retry
shuffle
restart
0:00
Embed Code - If you would like this activity on your web page, copy the script below and paste it into your web page.
Normal Size Small Size show me how
Normal Size Small Size show me how
1.4.2 (b pt 1)
1.4.2
| Question | Answer |
|---|---|
| Removing values from data structures | for all data structures, the value is never removed; the space is marked as free and there are no pointers to it |
| Linked list | A list of data together with a set of links to sort the data on various factors Foundation for other data structures Stores data in inputed order and pointers link nodes in desired order |
| Linked list diagram | - Start pointer identifies first node - Each node contains data and pointer to next node |
| Linked list types | - Doubly linked lists - Circular linked list - Doubly circular list |
| Doubly linked lists | can point to previous nodes as well |
| Circular linked list | last node points to first |
| Doubly circular linked list | Doubly and circular linked lists merged |
| Static arrays: Implement linked lists | nodes stored adjacent in memory: Start = 1 nextFree = 4 |
| Object-oriented: Implement linked lists | Nodes stored anywhere in memory, dynamic structure: Class Node Element = “” Pointer = Node End class |
| Applications (linked lists) | Music playlist Web browsers (to go back a page) |
| Operations (linked lists) | - Add node - Delete node (delete) - Move to next node (next) - Move back a node (previous) - Linear search (traverse) |
| Array: add node (linked lists) | second linked list holds list of free spaces |
| Object-oriented: add node (linked lists) | (no need for second linked list) same as array but Step 2 becomes: create new node and insert value |
| Array: delete node (linked lists) | second linked list holds list of free spaces |
| Array: linear search (traverse) (linked list) | second linked list with free spaces Go through a linked list, outputting the contents as you go 1. Check if empty 2. Start at node start pointer is showing 3. Output item 4. Follow pointer to next node 5. Repeat from step 3 until end is reached |
| Graphs | (really similar to trees) A collection of data nodes/vertices with connections (edges/arcs/pointers) between: Each vertex can connect to any other vertex Edges may be assigned weightings (values applied to edges in a graph, e.g. distances) |
| Graph types | Directed Unidirected Binary tree |
| Directed (graphs) | data connection may flow in one or both directions, as specified by arrows |
| Unidirected (graphs) | all edges are bidirectional, with no arrows on any edges |
| Binary tree (graphs) | a special type of graph |
| Object-oriented: Implement graphs | (Adjacency list) |
| Array: Implement graphs | |
| Graph diagram | |
| Graph applications | Navigation systems Social network data |
| Operations | Adjacent Neighbours Add Remove Add edge Remove edge Get vertex value Set vertex value Get edge value Set edge value Depth and breath first searches Pre-order, in-order, post-order traversal (types of breadth-first search) |
| Adding/removing from graphs | no single set of algorithms to add/remove items, each graph is different. You must traverse the graph to find the node first, and then do stuff with it |
| Adjacent graphs | returns if there is an edge |
| Neighbours graphs | returns all vertices between two vertices |
| Depth-first search | starts at root vertex, then visits each vertex and goes down each branch as far as possible before backtracking |
| Depth-first search graphs | uses LIFO and stacks |
| Breadth first search | starts at root node and visits each neighbouring node then moves to vertices of next depth |
| Breath first search graphs | uses FIFO and queues |
| Stack | LIFO A pointer points to the item currently at the top of the stack |
| LIFO | (last in, first out): (imagine a stack of coins) - Data added to the top of the structure - Data removed from the top of the structure |
| Stack operations | Push: adds top value Pop: removes the top value Peek: returns value at top of stack without deleting it Traverse |
| Array: push (stack) | 1. Check for stack overflow. Output error is stack is full 2. Increment the stack pointer 3. Insert new data item at location pointer to by the stack pointer If stack pointer is pointing at next available space, switch 2 and 3 around |
| Object-oriented: push (stack) | 1. Check for overflow. Output error if pointer points to last node 2. Create a new node and insert data into it 3. The new node points to the previous node 4. The stack pointer points to new/next space |
| Object-oriented: pop (stack) | 1. Check for underflow. Output error is pointer points to no node 2. Output node pointed to by pointer 3. Set stack pointer to previous item |
| Array: pop (stack) | 1. Check for underflow. Output an error if the stack is empty 2. Copy/output data item pointed to by pointer 3. Decrement the pointer |
| Traverse stack | No algorithm, either: Peek at top item Repeatedly pop items and output them |
| Stack overflow | If the stack is full, data cannot be pushed onto it and a stack overflow occurs |
| Stack underflow | If the stack is empty, data cannot be popped, causing a stack underflow |
| Array: Implement stack | (in tables) Top = 4 |
| Object-oriented: Implement stack diagram | (linked list) |
| Object-oriented: Implement stack pseudo code | Front/head pointer Back//tail pointer |
| Stack applications | When a program jumps to a subroutine, to hold a return line Undo operations on documents |
| Queues | (linear) FIFO pointers |
| FIFO | first in, first out): (like a shop queue) Data added to the end of the structure Data removed from the start of the structure |
| priority queue (FIFO) | when new items can join at the front, or jump the queue |
| Front/head pointer (queue) | points at the front of the queue |
| Back//tail pointer (queue) | points at the end of the queue |
| queue operations | Enqueue: adding to queue Dequeue: removing from queue Peek: returns value at top of the queue without deleting it Traverse |
| Array: enqueue (queue) | 1. Check for overflow. Output error if queue is full 2. Increment the back/tail pointer 3. Insert new data item at location pointed to by back/tail pointer |
| Object-oriented: enqueue (queue) | 1. Check for overflow 2. Create a new node and insert data into it 3. The back pointer is set to point to new node 4. If this is the first node, front pointer is set to point to new node |
| Object-oriented: dequeue (queue) | 1. Check for underflow 2. Output node pointed to by front pointer 3. Set front pointer to previous item |
| Array: dequeue (queue) | 1. Check for underflow. Output error if queue is empty 2. Copy/output data item pointed to by front/head pointer 3. Increment front/head pointer |
| Traverse queue | No algorithm, either: Peek at top item Repeatedly dequeue items and output them |
| queue overflow | If the queue is full, data cannot be enqueued onto it and a queue overflow occurs |
| queue underflow | If the queue is empty, data cannot be dequeued from it, causing a queue underflow |
| Array: Implement queue | in a table, has to be a circular queue that cycles the back pointer to the front of the array when it reaches the end so that it doesn't run out of space Front = 0 Back = 4 |
| Array: Implement circular queue | |
| Object-oriented: Implement queue | |
| queue applications | printer queue |
Created by:
FlashCardFun!