Linked Lists Revision Questions Flashcards
What determines the linear order of an array? And what determines the linear order of a linked list?
The linear order of an array is determined by the array indices, and the order in a linked list is determined by a pointer in each object.
What do the three key attributes of an object (key, next, prev) in a doubly linked list stand for?
key = data
next = link to next node
previous = link to previous node (address)
What does head stand for?
the first element in the list
What does NIL mean?
No element
Under what condition is a linked list empty?
If L: head = NIL , the list is empty.
What is the difference between a singly linked list and doubly linked list?
Singly linked list only go one way, so there is no ‘prev’ pointer.
Doubly linked lists can go in both directions.
What is a circular list?
A circular list only goes one way, but its tail links back to its head, so it goes in a circle.
What does LIST-SEARCH(L, k) algorithm do and how does it work? Why does it takes Θ(n) in the worst case? What is the best case?
LIST-SEARCH searches a list for a specific element. It uses a simple linear search.
The worst case is Theta(n), since it may have to search the entire list.
What does LIST-INSERT(L, x) algorithm do, and how does it work? Why does it take O(1)?
The LIST-INSERT procedure splices an element onto the front of the list.
What does LIST-DELETE(L, x) algorithm do, and how does it work? Why does it take O(1)? What is the time complexity measure if we delete an element with a given key?
The LIST-DELETE removes an element x from a linked list L . It must be given a pointer to x , and it then “splices” x out of the list by updating pointers.
If we wish to delete an element with a given key, we must first call LIST -SEARCH to retrieve a pointer to the element.
this would add worst-case runtime Theta(n)
What is a sentinel L.nil?
What is the benefit of having a circular doubly linked list with a sentinel? And what is the side effect?
A sentinel is a dummy object that allows us to simplify boundary conditions.
The gain from using sentinels within loops is usually a matter of clarity of code rather than speed;
We should use sentinels judiciously. When there are many small lists, the extra storage used by their sentinels can represent significant wasted memory.
