AI InterviewSearch…Search problems, topics, or pages…Ctrl KGet started
Mediumlinked listcircular

~75s

Circular list with a tail pointer

A circular singly linked list is kept with a single pointer to its last node. Which insertions are possible in O(1) time?

Show the answer and the worked solution

Correct answer: C.

Both at the front and at the end

Worked solution

  1. In a circular list the last node's next field already points at the first node, so the head is one hop from the tail pointer.
  2. Inserting at the front splices the new node between the last node and the current first node — a constant number of assignments.
  3. Inserting at the end is the same splice, plus moving the tail pointer to the new node — again constant.
  4. So Both at the front and at the end are O(1).

Answer: Both at the front and at the end.

The idea

Keeping the tail rather than the head of a circular list buys both ends for the price of one pointer. It is why circular lists are the usual implementation of a round-robin ready queue.

Shortcut. tail.next is the head, so a tail pointer reaches both ends in one hop; front and end insertion are the same splice, differing only in whether tail moves.

Common trap. "At the end only" reasons as for a plain tail pointer and forgets that circularity hands over the head for free.

Data Structures & Algorithms

10 of 40

Level

Medium

Target time

~75s

PreviousNext
AI InterviewGet started

Circular list with a tail pointer — Aptitude Question

Circular list with a tail pointer: A circular singly linked list is kept with a single pointer to its last node. Answer and worked solution on CodeKairo.

Question

A circular singly linked list is kept with a single pointer to its last node. Which insertions are possible in O(1) time?

Options

  1. At the front only
  2. At the end only
  3. Both at the front and at the end
  4. Neither, since both need a traversal
Show the answer and the worked solution

Correct answer: C. Both at the front and at the end

Worked solution

  1. In a circular list the last node's next field already points at the first node, so the head is one hop from the tail pointer.
  2. Inserting at the front splices the new node between the last node and the current first node — a constant number of assignments.
  3. Inserting at the end is the same splice, plus moving the tail pointer to the new node — again constant.
  4. So Both at the front and at the end are O(1).

Answer: Both at the front and at the end.

The idea

Keeping the tail rather than the head of a circular list buys both ends for the price of one pointer. It is why circular lists are the usual implementation of a round-robin ready queue.

Shortcut. tail.next is the head, so a tail pointer reaches both ends in one hop; front and end insertion are the same splice, differing only in whether tail moves.

Common trap. "At the end only" reasons as for a plain tail pointer and forgets that circularity hands over the head for free.

All Data Structures & Algorithms questions · placement mock tests