In a doubly linked list, How many pointers are affected on an insertion operation?

Question

I had an interview yesterday. As it started, the first thing that the interviewer asked was

" In a doubly linked list, How many pointers will be affected on an insertion operation ? "

---

Since, he didn't specifically asked where to insert I replied that it depends on how many nodes are there in DLL.

As total pointers that will be affected will depend on whether the list is empty or not and where insertion takes place.

But, he didn't say anything whether I had convinced him or not.

Was I correct or maybe I missed something ?

Answer 1

I think the answer depends on whether we are inserting the new node in the middle of the list (surrounded by two nodes), or at the head or tail of the list.

For insertions in the middle of the list, to splice in a new node as follows:

A --- B
   ^^ splice M in here

A.next = M
M.prev = A
B.prev = M
M.next = B

Hence four pointer assignments take place. However, if the insertion be at the head or tail, then only two pointer assignments would be needed:

TAIL (insert M afterward)

TAIL.next = M
M.prev = TAIL