Data Structures (4.2 - Part 1) Flashcards
Arrays
Data structures of fixed size that contain data of same type stored in contiguous block of memory
How are items in 3d array referred to?
First by 2d array no., then by row no. and then by column no.
Which 2 data structures can be implemented using linked lists?
Stacks and queues
What do nodes contain?
- Data item
- Pointer to next node in sequence
Null pointer
Pointer used to identify last item of data
What does use of pointers mean for linked lists?
Data doesn’t have to be stored contiguously in memory
2 benefits of linked lists
- Size can be dynamically changed easily
- Easy to use
Disadvantage of linked lists
Slower to access across specific elements than arrays
Queue
Data structure where items are always added to end and removed from front
What type of data structure is queue?
FIFO
Static queue
Queue that is fixed in size
Dynamic queue
Queue that is able to grow in size when necessary
enQueue ()
Adds item to rear of queue
deQueue ()
Removes and displays item at front of queue
isEmpty ()
Checks to see if queue is empty
2 uses of queues
- CPU scheduling
- Breadth-first traversal of graph
Linear queue
Type of queue where when item of data is removed from front, all other items move up one place
Circular queue
Type of queue where when item of data is removed from front, the pointers identifying front and rear of queue are updated
Graphs
Data structures used to represent data items that have connections between them
2 methods of traversing a graph
- Depth first
- Breadth first
Depth-first traversal
Involves travelling down one route as far as possible, before reversing and travelling as far down next route as possible
Breadth-first traversal
Involves visiting all adjoining nodes for each node in turn
