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. One node is selected, visited and marked then adjacent nodes are visited & stored in a queue.
Depth-first search - uses stacks (LIFO) structure. Visited nodes are pushed onto the stack.
- When there are no nodes left to visit, the nodes are popped off the stack