Computer Science
What does a linked list consist of & what type of data structure is it?
- Nodes & a pointer
- Dynamic data structure
What does each node contain
Data and a pointer to the next node
What is a doubly linked list?
Where an extra pointer is added so that node can point ot the previous and next item
What is a circular linked list?
Where the last node points to the first. To circle through the list.
What is a doubly circular linked list?
Where an extra pointer is added to the previous item
Give examples of where linked lists can be used
- ISR routines
- Playlists (music players)
- Image viewers to switch between previous and next image
- Hash table collisions resolution as an overflow
What can you do with linked lists?
- Linear search through them
- Move to the previous item (doubly linked list)
- Delete nodes
- Add nodes
What is a graph and how does it differ from linked lists & binary trees
- A data structure consisting of nodes/vertices & pointers/edges.
- Each vertex can have more than 2 edges
Whats the difference between a directed graph and an undirected graph
Directed - Points in one direction
Undirected - Doesn't have a specified direction
What is meant by a 'Weighted' Graph
Where each edge is given a value showin the relationship between vertices
What are graphs normally stored as
Objects or Dictionaries known as adjacent lists
Give the advantages & disadvantages of using adjaceny matrixes
- Convenient to work with
- Adding edges are very simple
Disadvantages:
- Graphs with many nodes and few edges leaveempty cells
- Larger graphs waste more memory
- Using static structures e.g. arrays makes it harder to add/delete nodes
Give uses of graphs
Mapping road networks for navigation systems
Storing social network data
resource allocation
What are the 2 types of traversing graphs
Breadth-first search - uses queues (FIFO) structure. Start with the root node, dequeue the root node and explore its adjacent nodes. Repeat when going to next node (any order)
Depth-first search - uses stacks (LIFO) structure. Visited nodes are pushed onto the stack.
- When there are no nodes left to visit, the last node is popped off the stack
Give the 3 ways of traversing binary trees
- Pre-Order traversal
- In-Order traversal
- Post-Order traversal
Explain how you would add to a linked list
- Check if there's free memory for a new node, output error if not
- Create new node & insert data
- if the list is empty, new node becomes first node (put a satrt pointer on it)
- If the new node should be placed before the 1st node, put a start pointer on the new node and point it to that node
- If the new node is greater than the current node check the next node until you find the correct position
- update the free pointer so it points to the next available storage space
Explain how you would delete a node from a linked list
- Check if list is empty, if empty output error
- If first item to be deleted, set start pointer to next node & delete
- Start at node 1 & traverse if current node is to be deleted, set pointer from previous to next node
- update free pointer
Explain how you would traverse through a linked list
- Check if empty
- Start at node with starter pointer
- output item
- Go to next node
- repeat last 2 steps until item found
What is a linked list
A data sturcture used to hold an ordered sequence (Can be both static or dynamic)