이중 연결된 목록에서 삽입 작업의 영향을받는 포인터는 몇 개입니까?

Question

나는 어제 인터뷰를 가졌습니다. 이되면서, 면접관이 물었다 제일 먼저,

"이중 연결리스트에서이, 얼마나 많은 포인터가 삽입 작업에 영향을받을 것인가?"이후

---

이었다 그는 특별히 요구하지 않았다 삽입 할 위치는 DLL에 얼마나 많은 노드가 있는지에 따라 다릅니다.

영향을받을 총 포인터는 목록이 비어 있는지 여부와 삽입이 이루어지는 위치에 따라 다릅니다.

그러나 그는 내가 확신했는지 여부를 말하지 않았습니다.

내가 맞았거나 뭔가를 놓쳤을까요?

Answer 1

나는 (두 노드로 둘러싸인) 목록 중간에 새 노드를 삽입 할 것인지 아니면 목록의 머리 또는 꼬리에 삽입 할 것인지에 따라 응답이 달라집니다. 다음과 같이

목록의 중간에 삽입 들어

는 새로운 노드에 잇기 :

A --- B 
    ^^ splice M in here 

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

따라서 네 개의 포인터 할당이 이루어집니다. 그러나 삽입이 머리 또는 꼬리에 있다면 두 포인터 지정 만 필요합니다.

TAIL (insert M afterward) 

TAIL.next = M 
M.prev = TAIL