이중 연결 리스트(Doubly Linked List)의 특징과 단일 연결 리스트와의 차이점은?

이중 연결 리스트는 각 노드가 데이터와 다음 노드를 가리키는 'next' 포인터뿐만 아니라 이전 노드를 가리키는 'prev' 포인터를 가지고 있다는 점이 특징입니다.

단일 연결 리스트는 'next' 포인터만 있어서 한 방향으로만 탐색이 가능한 반면, 이중 연결 리스트는 'prev' 포인터 덕분에 양방향으로 자유롭게 탐색할 수 있습니다.

단일 연결 리스트에서는 특정 노드를 삭제하려면 삭제할 노드의 이전 노드를 찾아야 하는 번거로움이 있지만, 이중 연결 리스트는 'prev' 포인터를 통해 이전 노드에 바로 접근할 수 있어 삭제 연산이 더 효율적입니다.

다만, 'prev' 포인터를 위한 추가적인 메모리 공간이 필요하다는 메모리 오버헤드가 발생한다는 단점도 있습니다.