Question

In C++

Question 1) Theoretical Questions

1.1) Why is it better to store the tail pointer rather than the head pointer in a circular singular linked list?

1.2) What are the main advantages of a doubly linked list compared to a singularly linked list?

Question 2) Practical Questions

Suppose a doubly-linked list makes use of a class called DLNode, defined as follows:

template<class T>

struct DLNode

{

T data;

DLNode<T> * next;

DLNode<T> * prev;

};

Further suppose the linked list class maintains a pointer to the first node in the list as a member variable called DLNode<T> *head.

2.1) Suppose left and right are variables of type DLNode<int>* pointing to two nodes that are adjacent in a doubly-linked list, i.e left->next points to right. Both nodes have predecessors and successors in the list. Write the code taht will swap the nodes in the list by adjusting pointers. Do not change the value of the data field of either nodes.

2.2) Given a circular doubly-linked list of 5 integers (1,2,3,4,5), write a function printAll() to output the list in the following order: (1,5,2,4,3). The function should work on any odd number of nodes.

Answer 1

1.1

My understanding...

Advantages:

• Inserting at the end is O(1) instead of O(N).
• If the list is a Doubly Linked List, then removing from the end is also O(1) instead of O(N).

Disadvantage:

• Takes up a trivial amount of extra memory: 4-8 bytes.
• The implementer has to keep track of the tail.

Looking at these advantages and disadvantages, I can't see why a Linked List would ever avoid using a tail pointer.

1.2

Following are advantages/disadvantages of doubly linked list over singly linked list.

Advantages over singly linked list
1) A DLL can be traversed in both forward and backward direction.
2) The delete operation in DLL is more efficient if pointer to the node to be deleted is given.
3) We can quickly insert a new node before a given node.
In singly linked list, to delete a node, pointer to the previous node is needed. To get this previous node, sometimes the list is traversed. In DLL, we can get the previous node using previous pointer.

Disadvantages over singly linked list
1) Every node of DLL Require extra space for an previous pointer. It is possible to implement DLL with single pointer though (See this and this).
2) All operations require an extra pointer previous to be maintained. For example, in insertion, we need to modify previous pointers together with next pointers. For example in following functions for insertions at different positions, we need 1 or 2 extra steps to set previous pointer.