Circular queue & Singly and doubly linked list

Objectives
    • Create a doubly linked list containing a dummy node.
    • Modify the implementation of a linked list to add methods.
    • Resolve problems that require knowledge of interfaces.
Circular queue Singly and doubly linked list
Circular queues are a type of queues that implements the principle of First In First Out (FIFO). In these queues, the last element is linked back to the first in order to create a loop. These queues use one instance variable for the head of the queue and one for the tail of the queue.
When we add an element using enqueue(), we add the element at the position of the tail and increment the pointer tail. When we remove an element using dequeue(), we remove and return the element at the position of the head pointer and increase that pointer.
Here is a visual representation of a circular queue and its use. We can represent it via an array where the last element links to the first, or like a circular array.


Figure 1 : Visual representation of a circular queue.
Singly and doubly linked list
Reminder: we have seen in class that there are several implementations for a list using linked elements. We have discussed singly- and doubly-linked list. These implementations, however similar they might be, have some important differences.
Singly-linked lists link each elements to the next one in the list, up to the last element, whose next is null.
Doubly-linked lists allow faster implementation of some methods thanks to the link between each element and the previous one. The next of the last element will be null just like the prev of the first element will be null.
It is also possible to implement a (doubly- or singly-)linked list using a dummy node. A dummy node has a null value and is placed at the beginning of the list. This allows for a simpler implementation of the methods by reducing the number of special cases and allows the list to be circular since the first element is linked to the last one via the dummy node.
Test your knowledge of the different implementations.
Question 1.0 :
Describe the following image. Particularly, is this a singly or doubly linked list? What is this technique called ( a … node)?
See image
Answer
Question 1.1 :
True or false? It is possible go through a singly linked list in both directions efficiently.
Answer
Question 1.2 :
What can we do to make it easier to add an element at the end of a list? (without needing to traverse the entire list first)
Answer
Question 1.3 :
True or false? A circular list using a dummy node will have many special cases.
Answer
Question 1.4 :
In what cases is the use of a list implemented using an array more efficient than with a list using singly-linked elements? (name 2 methods).
Answer
Question 1.5 :
Do we need to have a pointer tail in a circular doubly-linked list?
Answer
Question 1.6 :
True or false? To implement a linked list, we can simply use a dynamic array
Answer
Question 1.7 :
Here is the constructor of the nested class node for a list. Is the list singly or doubly linked?
//constructor
private Node(T value, Node next) {
        this.value = value;
        this.next = next;
}
Answer
Question 1.8 :
What does the following code do in a circular doubly-linked list? Consider that the variable current was previously declared.
current = head.prev;
while (current != head) {
        current = current.prev;
}
Answer