자료구조) 이중 연결 리스트 (Double Linked List) - 1

이중 연결 리스트

기존의 방법(단일 연결 리스트)으로 리스트의 데이터를 찾으려면 링크를 타고, 타고, 타고 내려가서 맞는게 나올때까지 들어가야 했다.

이 방법을 어떻게 개선할 수는 없을까?

그림처럼 노드를 두 개로 만들면 된다. 이전 노드의 주소를 저장하는 노드(PrevNode)와 다음 노드의 주소를 저장하는 노드(NextNode).

이제 우리는 양방향으로 데이터를 찾을 수 있게 되었다.

이 방식의 장점은 단일 연결 리스트에 비해 접근이 빠르다는 점이다. 예를 들어 1000개의 데이터 중 900번째 데이터에 접근해야 한다면 단일 연결 리스트는 900번 이동해야 하지만, 이중 연결 리스트는 꼬리부터 100번 움직이면 접근할 수 있다.

 

이중 연결 리스트에 다른 노드를 연결은 어떻게 할 수 있을까?

 

맨 처음 상태이다. 여기에 25라는 노드를 20과 30 사이에 끼워넣는다고 가정하자.

 

먼저 25 노드에서 NextNode가 30노드를 가리키게 해야 한다.

 

 

그 다음 30->20을 가리키던 30의 PrevNode가 25를 가리키게 변경해준다.

 

 

그 다음은 25에서 PrevNode가 20을, 20->30을 가리키던 20의 NextNode가 25를 가리키도록 만들어주면 삽입이 끝이 난다.