Doubly Linked List

Doubly Linked List

Head : Linked List의 시작 노드를 가르키는 포인터
Node :
1. 데이터를 가르키는 포인터(Data)
2. 다음 노드를 가르키는 포인터(Right)
3. 이전 노드를 가르키는 포인터 (Left)
첫 노드의 Left = 마지막 Node의 Right = NULL

---

Search

node = *head;
while(!node) {
    if(node->data == want)
        return true;

    node=node->right;
}
return false;

---

Insertion

Case 1. Insertion at The Front

1. 새로운 Node 생성(New)
2. New->Right = Head
3. New->Left = NULL
4. Head->Left(A) = New
5. Head = New

Case 2. Insertion after The Node

Curr = The Node in The List

1. 새로운 Node 생성(New)
2. New->Left = Curr
3. New->Right = Curr->Right
4. Curr->Right->Left = New
5. Curr->Right = New;

Case 3. Insertion at The End

End = Last Node of The List

1. 새로운 Node 생성(New)
2. New->Left = End
3. New->Right = NULL
4. End->Right = New

---

Deletion

Case 1. Deletion at The Front

Front = First Node of The List / Node A

1. Head = Front->Next
2. Front->Right->Left = NULL
3. Free The Node

Case 2. Deletion after The Node

Curr = The Node to Delete / Node B

1. Curr->Left->Right = Curr->Right
2. Curr->Right->Left = Curr->Left
3. Free The Node

Case 3. Deletion at The End

Curr = The Node to Delete / Node C

1. Curr->Left->Right = NULL
2. Free The Node