자료구조 - Chapter 05

원형 연결 리스트(Circular Linked List)

원형 연결 리스트

연결 리스트의 마지막 노드가 NULL을 지칭 했다면 원형 연결 리스트는 마지막 노드가 다시

첫 번째 노드를 지칭하게 한다. 따라서 순환 모형이 만들어 진다.

 

원형 연결 리스트에서는 머리와 꼬리 노드 구분이 없다. 유일한 차이점은 포인터 변수 head가

무엇을 지칭하는가 이다.

 

따라서 노드 추가 작업이 발생할 경우 끝을 찾아가는 일이 발생하기 때문에 보통 head 포인터 대신

tail 포인터를 설정하여 꼬리를 표기한다.

 

예제 : 원형 연결 리스트

 

원형 연결 리스트

CLinkedList.c

0.00MB

CLinkedList.h

0.00MB

ex5-1 circleLinkedList.C

0.00MB

typedef struct _CLL{

    Node * tail;

    Node * cur;

    Node * before;

    int numOfData;

} CList;

#기존 코드와 다르게 head포인터가 사라지고 tail 포인터만으로 구성되어 있으며

현재 위치 포인터와 전 값을 가지고 있는 before포인터를 내포하고 있다.

 

원형 연결 리스트 노드 삭제 상황

• 예외 상황1 : 삭제할 노드가 tail을 가리키는 경우
• 예외 상황2 : 삭제할 노드가 리스트에 홀로 남는 경우

if ( plist->tail == plist ->tail->next) 마지막 노드를 체크하는 경우를 추가한다.

 

예제 : 원형 연결 리스트 활용(당직 구하기)

당직 근무표를 토대로 기준에서 몇일 뒤 당직 당번을 예측한다.

 

원형 연결리스트 예제

양방향 연결 리스트(Double Linked List)

양방향 연결 리스트

이중 연결 리스트라고도 한다. 노드가 양쪽 방향으로 연결된 리스트

 

양방향 연결 리스트는 양방향으로 조회가 가능해서 before 포인터 변수가 필요 없다.

 

예제 : 이중 연결 리스트 구현

 

이중 연결 리스트

DBLinkedList.c

0.00MB

DBLinkedList.h

0.00MB

ex5-3 simpleDoubleLinkedlist.c

0.00MB

typedef struct _node{

    Data data;

    struct _node * next;

    struct _node * prev;

} Node;

#좌우에 관련된 오른쪽 왼쪽 방향 포인터가 필요하다.

 

양방향 연결리스트 삭제

• 첫 번쨰 노드를 삭제하는 경우
• 마지막 노드를 삭제하는 경우
• 그 외의 노드를 삭제하는 경우

예제 : 더미 노드를 추가한 삭제 및 이중 연결리스트 구현

 

이중 연결리스트

DBDLinkedList.c

0.00MB

DBDLinkedList.h

0.00MB

ex5-4 DummyDBLinkedList.c

0.00MB