DSA interview question

Introduction to Doubly Linked Lists

Easy · Data structures · Topics: linkedlist, doubly linkedlist

The problem

A web browser's history needs to go both backward and forward from the current page, and a cache needs to remove any entry in O(1) once it has a pointer to it. A singly linked list can do neither well: it can't step backwards, and removing a node requires finding its predecessor. A doubly linked list gives every node a prev pointer as well as next. Your first task: convert an array into a doubly linked list, and traverse it forwards from the head and backwards from the tail, confirming the prev links are right.

Example: [1, 2, 3] → forwards 1 <-> 2 <-> 3, backwards 3 <-> 2 <-> 1.

Function signature

struct DNode { int data; DNode* prev; DNode* next; };
DNode* arrayToDLL(const vector<int>& a);   // returns the head
vector<int> forward(DNode* head);          // head to tail via next
vector<int> backward(DNode* head);         // tail to head via prev

Test cases

Input `a`	Forward	Backward	Explanation
`[1, 2, 3]`	`1 <-> 2 <-> 3`	`3 <-> 2 <-> 1`	prev links mirror next links
`[7]`	`7`	`7`	Head and tail are the same node
`[]`	`(empty)`	`(empty)`	head is nullptr
`[4, 4, 9]`	`4 <-> 4 <-> 9`	`9 <-> 4 <-> 4`

(Confirm: head->prev and tail->next are nullptr; backward traversal must be the exact reverse of forward traversal.)

How interviewers phrase it

"Implement a doubly linked list" or "Convert an array to a doubly linked list."
Theory: "Singly vs doubly linked list? Where are doubly linked lists used?"
It's the core structure behind an LRU cache (LeetCode 146), a classic design question.

Clarifying questions to ask

Should I keep a tail pointer?
Circular or linear?
Who frees the memory?

Follow-ups to expect

"What do you gain over a singly linked list?"
"What does it cost?"
"Where is it used?"
"How do you delete a node in O(1)?"
"Complexity?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview