GATE CS 1997 Q1.4 — Linked Lists

To concatenate two lists $L_1$ and $L_2$ in $O(1)$ time, we must be able to access the head and tail of both lists in $O(1)$ time and update their connections.

In a Circular Doubly Linked List (CDLL), we only need a single pointer to the head of each list (say, head1 and head2):

• The tail of $L_1$ is directly accessible in $O(1)$ time as head1->prev.
• The tail of $L_2$ is directly accessible in $O(1)$ time as head2->prev.

We can concatenate the two lists by updating a constant number of pointers:

1. Identify the tails:
   tail1 = head1->prev
tail2 = head2->prev
2. Link the tail of the first list to the head of the second list:
   tail1->next = head2
head2->prev = tail1
3. Link the tail of the second list back to the head of the first list to maintain circularity:
   tail2->next = head1
head1->prev = tail2

All these pointer manipulations take $\mathcal{O}(1)$ time.

Why other options are incorrect:

• Singly linked list / Doubly linked list: Without an explicit tail pointer, finding the tail node requires traversing the entire list, which takes $\mathcal{O}(N)$ time.
• Array implementation: Concatenating two arrays requires shifting elements or allocating a new larger array and copying elements, which takes $\mathcal{O}(N)$ time.