Double Linked List

단일연결리스트는 tail포인터가 있더라도 removeLast를 하기위한 시간 복잡도가 $O(n)$입니다.
무조건 첫 요소부터 시작해서 마지막에서 두번째 요소까지와야 마지막요소를 제거할 수 있기 때문입니다.
그리고 마지막 노드를 기억하기위해 임시 포인터를 사용해야합니다.

이를 빠르게 해결하기 위한것이 이중 연결 리스트(Double Linked List)입니다.

이중 연결 리스트

단일 연결 리스트(LinkedList)와 유사하지만, 이중 연결 리스트에는 모든 노드에 next, previous, data가 있습니다.

각 노드에서 next는 다음 노드를 가리키고 있고 previous는 그 전 노드를 가리키고 있습니다.
tail 포인터는 상수 시간 안에 추가와 제거를 하기 위해 필요합니다.

이중 연결 리스트에서는 뒤에서 두번째 노드를 tail.previous로 바로 접근 할 수 있기때문에 임시 포인터를 만들 필요없이 tail.previous.next를 null로 가리키게 하면 됩니다.
그리고 tail은 tail.previous로 설정하면 마지막 노드가 사라지고 마지막에서 두번째 노드가 tail이 됩니다.

그러나 addFirst를 하는 경우엔 단점이 존재합니다.
previous 포인터가 추가되기 때문에 노드를 추가하는 과정이 더 복잡해지고 더 많은 메모리 공간이 필요하기 때문입니다.