이중 연결 리스트 (p75 ~ p76)

이중 연결 리스트(doublely linked list)는 두 개의 포인터를 사용하여 선행 노드와

후속 노드에 모두 연결되는 양방향 구조를 가진다.

 

 

자료 삽입

이중 연결 리스트에서 자료를 삽입하는 과정음 다음과 같다.

먼저 새로운 노드를 생성하여 노드의 데이터 영역에 자료(B)를 저장한다.

 

 

새로운 노드(B)의 오른쪽 포인터 영역이 다음 노드(C)를 가리키게 하고,

새로운 노드(B)의 왼쪽 영역이 이전 노드(A)를 가리키게 한다.

 

 

후속 노드(C)의 왼쪽 포인터 영역이 새로운 노드(B)를 가리키게 하고,

선행 노드(A)의 오른쪽 포인터 영역이 새로운 노드(B)를 가리키게 한다.

 

 

자료 삽입이 완료된 상태는 다음과 같다.

 

 

자료 삭제

자료가 저장된 리스트에서 가운데 위치한 노드(B)를 삭제하는 과정은 다음과 같다.

 

 

먼저 삭제하고자 하는 노드(B)의 이전 노드(A)의 오른쪽 포인터 영역이

다음 노드(C)를 가리키게 한다.

 

이어서 삭제하고자 하는 노드(B)의 다음 노드(C)의 왼쪽 포인터 영역이

이전 노드(A)를 가리키게 한다.

 

 

삭제가 완료된 상태는 다음과 같다.