더블 링크드 리스트

[Concept] 더블 링크드 리스트 (double linked list)

이번 글에서는 더블 링크드 리스트 (이중 연결 리스트) 에 대해 적어보겠습니다. 이전 글에서 적었던 일반 링크드 리스트는 데이터를 조회할 때 head, 즉 앞에서부터 찾아가는 방식이었습니다. But, 만약 데이터가 20000개가 있고, 맨 마지막 데이터를 조회하고자한다면, 20000번 조회를 해야하는거겠죠? 대신 뒤에서부터 조회한다면 어떨까요? 즉, 앞쪽의 데이터를 조회할 떄는 앞에서부터, 뒤쪽의 데이터를 조회할 때는 뒤에서부터 찾아나갈 수 있는 리스트가 더블 링크드 리스트 입니다. 이전 기본 연결 리스트의 노드에는 데이터와 next 주소만 있었다면, 더블 연결 리스트에는 prev 주소도 함께 저장됩니다. 이전 기본 연결 리스트에서는, self.head()만 지정했다면, 더블 연결 리스트에는 self.t..