Arrays, Lists, Queues etc Flashcards
Describe the properties of arrays
Contiguous: The elements are stored in consecutive memory locations
Homogeneous: All elements have the same type
Arrays have a fixed size which is defined when they are created
Describe the structure of a linked list
Made up of nodes, which store a piece of data and a pointer to the next node
The first node is called the head
The last node is called the tail and points to null
The nodes can be scattered across memory
Describe how a list would be implemented
L.head = pointer to head
L.tail = pointer to tail
L.size = length of list
N.data = data stored in node
N.next = pointer to the next node (or NULL)
What are the advantages/disadvantages of arrays/lists?
Arrays: Fast data access, slow data modification
Lists: Slow data access, fast data modification
What is a doubly-linked list?
A list where each node has a next and a prev pointer
Sentinel nodes at the start/end of the list
The size counter does not count sentinels
What is a circularly-linked list?
Like a singly-linked list but the last node points back to the first
The first node accessed when traversing the list is called the cursor
What is a stack?
Collection of objects that are inserted and removed according to the last-in-first-out (LIFO) principle
Which methods does a stack support?
push(e) inserts element e at the top of the stack
pop removes and returns the top element
size returns the number of elements
isEmpty returns 1 if the stack is empty
top returns the top element without removing it
How are stacks implemented using arrays?
They are stored as an N-element array S with an integer variable which stores the position of the top element (-1 when empty)
Advantages/disadvantages of representing stacks with arrays?
Time efficient, time taken does not depend on the size of the stack
Fixed capacity can cause errors
What is a queue?
Collection of objects that are inserted and removed according to the first-in-first-out (FIFO) principle
Element access and deletion are restricted to the first element in the sequence, which is called the front of the queue.Element insertion is restricted to the end of the sequence, which is called the rear of the queue.
What methods does a queue support?
enqueue(e) inserts element e at the back of the queue
dequeue removes and returns the element at the front of the queue
size returns the number of elements
front returns the element at the front without modifying it
How can a queue be represented by an array?
An array and two integers, f and r
f is the index of the cell storing the front of the queue
r is an index to the next available cell (the one after the rear)
Enqueue => increment r
Dequeue => increment f
r > f
How do we avoid errors when representing queues?
Let f and r wrap around using modulo N arithmetic, where N is the queue capacity
Limit the size of the queue to N-1 as a queue with N items would trigger isEmpty, as f = r
Queue size method
return (r - f) mod N
