리스트 - 이중 연결 리스트(Doubly Linked List)와 이중 연결 원형 리스트(Doubly Circular Linked List)

이중 연결 리스트

  - 리스트의 각 노드가 전위 방향과 후위 방향에 대한 2개의 링크 필드 llink와 rlink로 연결된 리스트

 

장점

1. 리스트 검색 시 매번 첫 번째 노드로부터 검색을 시작할 필요가 없다.

2. 삽입 및 삭제 연산이나 기타 연산 등에서 선행 노드에 대한 추가적인 파라미터 전달이 필요 없게 된다.

 

이중 연결 리스트를 구조체로 정의

typedef struct node_type *node_ptr; typedef struct node_type {     node_ptr llink;     int data;     node_ptr rlink; }; node_ptr list_ptr;

 

이중 연결 리스트의 첫 번째나 마지막 노드가 아닌 임의의 노드에 대해서 다음과 같은 관계가 성립.

ptr = ptr->llink->rlink = ptr->rlink->llink

이 관계가 이중 연결 원형 리스트에서는 모든 노드들에 대해서 성림함.

 

 

헤드 노드를 갖는 이중 연결 원형 리스트