AI InterviewSearch…Search problems, topics, or pages…Ctrl KGet started
Easylinked listcomplexity

~60s

Constant-time list operation

A singly linked list is kept with only a head pointer. Which operation runs in O(1) time?

Show the answer and the worked solution

Correct answer: B.

Inserting a node at the front

Worked solution

  1. The head pointer reaches the first node immediately and nothing else.
  2. Inserting a node at the front means pointing the new node at the old head and moving the head — two assignments, whatever the length.
  3. Reaching the last node, its predecessor, or a searched value all require walking the list, which is O(n).

Answer: Inserting a node at the front.

The idea

Cost in a linked structure is the number of links you must follow. Keeping a tail pointer as well would make end insertion constant too, but end deletion would still need the predecessor.

Shortcut. With only a head pointer, anything that needs the last node or a search walks n links; only the front needs no traversal.

Common trap. "Inserting a node at the end" is O(1) only when a tail pointer is kept, and this list has just the head.

Data Structures & Algorithms

8 of 40

Level

Easy

Target time

~60s

PreviousNext
AI InterviewGet started

Constant-time list operation — Aptitude Question

Constant-time list operation: A singly linked list is kept with only a head pointer. Which operation runs in O(1)… Answer and worked solution on CodeKairo.

Question

A singly linked list is kept with only a head pointer. Which operation runs in O(1) time?

Options

  1. Deleting the last node
  2. Inserting a node at the front
  3. Inserting a node at the end
  4. Searching for a given value
Show the answer and the worked solution

Correct answer: B. Inserting a node at the front

Worked solution

  1. The head pointer reaches the first node immediately and nothing else.
  2. Inserting a node at the front means pointing the new node at the old head and moving the head — two assignments, whatever the length.
  3. Reaching the last node, its predecessor, or a searched value all require walking the list, which is O(n).

Answer: Inserting a node at the front.

The idea

Cost in a linked structure is the number of links you must follow. Keeping a tail pointer as well would make end insertion constant too, but end deletion would still need the predecessor.

Shortcut. With only a head pointer, anything that needs the last node or a search walks n links; only the front needs no traversal.

Common trap. "Inserting a node at the end" is O(1) only when a tail pointer is kept, and this list has just the head.

All Data Structures & Algorithms questions · placement mock tests