What is a Doubly Linked List?

이중 연결 리스트(doubly linked list)는 각 노드가 값과 두 개의 포인터(이전 노드를 가리키는 prev와 다음 노드를 가리키는 next)를 가지는 노드들의 시퀀스입니다. 리스트 자체는 양쪽 끝인 head(첫 번째 노드)와 tail(마지막 노드)을 모두 추적합니다.

노드당 두 개의 포인터와 추가적인 tail 참조는 많은 이점을 제공합니다. 이제 끝에 추가하는 작업은 O(1)이며(체인을 따라 걷는 대신 tail로 바로 이동), 마지막 노드를 제거하는 작업 또한 O(1)입니다(tail.prev를 통해 마지막에서 두 번째 노드에 도달할 수 있기 때문입니다). 트레이드오프는 노드당 더 많은 메모리가 사용된다는 점과, 삽입 및 삭제 시마다 동기화해야 할 포인터가 더 많아진다는 점입니다.

이중 연결 리스트의 다섯 가지 주요 연산은 다음과 같습니다:

1. AddFirst: 리스트의 맨 앞에 값을 추가합니다.
2. AddLast: 리스트의 맨 끝에 값을 추가합니다 (O(1)!).
3. Get: 주어진 인덱스의 값을 반환합니다.
4. RemoveLast: 마지막 노드를 삭제합니다 (O(1)!).
5. Size: 현재 저장된 노드의 개수를 반환합니다.

먼저 Node 클래스를 만들고, 그 위에 DoublyLinkedList를 구축해 봅시다!