1. 원형 연결 리스트(Circular linked list)
- 단순 연결 리스트에서 마지막 노드가 리스트의 첫 번째 노드를 가리키게 하여 리스트의 구조를 원형으로 만든 연결 리스트
- 단순 연결 리스트의 마지막 노드의 링크 필드에 첫 번째 노드의 주소를 저장하여 구성
- 링크를 따라 계속 순회하면서 이전 노드에 접근 가능
2. 원형 연결 리스트 구조
| head | Datd | Link | Datd | Link | Datd | Link |
| → | 10 | → | 20 | → | 30 | ↓ |
| curr | ↑ | ← | ||||
| node1 | node2 | node3 | ||||
원형 연결리스트 구조를 보게 되면 head와 curr은 첫 번째 노드를 가리킨다. 각 노드는 뒤에 있는 노드를 가리킨다.
단순 연결리스트에서 마지막 노드에는 NULL이 들어가지만, 원형 연결리스트에서 마지막 노드의 Link는 첫 번째 노드를 가리키게 된다.
3. 원형 연결 리스트 생성
1) C언어 실습
#include <stdio.h>
#include <stdlib.h>
typedef struct NODE{
int data;
struct NODE *link;
} NODE;
void main(){
NODE *head = NULL; // 머리 노드 생성
NODE *node1 = (NODE *)calloc(8, sizeof(NODE)); // 첫 번째 노드 생성
head = node1; // 머리 노드 다음은 첫 번째 노드
node1 -> data = 10; // 첫 번째 노드에 10 저장
NODE *node2 = (NODE *)calloc(8, sizeof(NODE)); // 두 번째 노드 생성
node1 -> link = node2; // 첫 번째 노드 다음은 두 번째 노드
node2 -> data = 20; // 두 번째 노드에 20 저장
NODE *node4 = (NODE *)calloc(8, sizeof(NODE)); // 네 번째 노드 생성
node2 -> link = node4; // 두 번째 노드 다음은 네 번째 노드
node4 -> data = 40; // 네 번째 노드에 40 저장
node4 -> link = node1; // 네 번째 노드 다음은 첫 번째 노드를 가리킴
puts(" - 출력 시작 -");
head = node1;
NODE *curr = node1; // 연결 리스트 순회용 포인터에 첫 번째 노드의 주소 저장
do{
printf(" %d\n", curr -> data); // 현재 노드의 데이터 출력
curr = curr -> link; // 포인터에 다음 노드의 주소 저장
} while(curr != head); // 포인터가 head가 아닐 때 계속 반복
free(node1); // 노드 메모리 해제
free(node2); // 노드 메모리 해제
free(node4); // 노드 메모리 해제
}
4. 원형 연결 리스트의 삽입
- 마지막 노드의 링크를 첫 번째 노드로 연결하는 부분만 제외하고는 단순 연결리스트에서 삽입 연산과 같은 연산
- 중간 노드로 삽입하기
- 원형 연결 리스트에 30 값을 갖는 노드 NEW를 포인터 pre가 가리키는 노드의 다음 노드로 삽입하는 알고리즘
1) 순서
- new.link <- pre.link;
- 노드 pre의 다음 노드로 new를 삽입하기 위해서 먼저 노드 pre의 다음 노드(pre.link)를 new의 다음 노드(new.link)로 연결
- pre.link <- new;
- 노드 new의 주소를 노드 pre의 링크에 저장하여 노드 pre가 노드 new를 가리키게 한다.
2) C언어 실습
위 생성된 원형 연결 리스트 코드에서 삽입 코드를 추가한다.
#include <stdio.h>
#include <stdlib.h>
typedef struct NODE{
int data;
struct NODE *link;
} NODE;
void main(){
NODE *head = NULL; // 머리 노드 생성
NODE *node1 = (NODE *)calloc(8, sizeof(NODE)); // 첫 번째 노드 생성
head = node1; // 머리 노드 다음은 첫 번째 노드
node1 -> data = 10; // 첫 번째 노드에 10 저장
NODE *node2 = (NODE *)calloc(8, sizeof(NODE)); // 두 번째 노드 생성
node1 -> link = node2; // 첫 번째 노드 다음은 두 번째 노드
node2 -> data = 20; // 두 번째 노드에 20 저장
NODE *node4 = (NODE *)calloc(8, sizeof(NODE)); // 네 번째 노드 생성
node2 -> link = node4; // 두 번째 노드 다음은 네 번째 노드
node4 -> data = 40; // 네 번째 노드에 40 저장
node4 -> link = node1; // 네 번째 노드 다음은 첫 번째 노드를 가리킴
puts(" - 삽입 전 -");
head = node1;
NODE *curr = node1; // 연결 리스트 순회용 포인터에 첫 번째 노드의 주소 저장
do{
printf(" %d\n", curr -> data); // 현재 노드의 데이터 출력
curr = curr -> link; // 포인터에 다음 노드의 주소 저장
} while(curr != head); // 포인터가 head가 아닐 때 계속 반복
puts(" - 삽입 후 -");
NODE *pre = node2;
NODE *NEW = (NODE *)calloc(8, sizeof(NODE)); // 새 노드 생성
NEW -> link = pre -> link; // 새 노드 링크를 pre의 링크로
NEW -> data = 30; // 새 노드에 30 저장
pre -> link = NEW;
curr = node1;
do{
printf(" %d\n", curr -> data); // 현재 노드의 데이터 출력
curr = curr -> link; // 포인터에 다음 노드의 주소 저장
} while(curr != head); // 포인터가 head가 아닐 때 계속 반복
free(node1); // 노드 메모리 해제
free(node2); // 노드 메모리 해제
free(node4); // 노드 메모리 해제
free(NEW); // 노드 메모리 해제
}
여기서 제일 중요한 코드는 puts(" - 삽입 후-"); 이후 코드다. 이후 코드를 글로써 설명한다.
원래는 node2가 node4를 가리킨다. 이때 포인터 변수를 하나(pre) 생성해서 node2를 저장한다. pre 변수는 node2가 되는 것이다. 이후 NEW 노드를 생성한다.
NEW 노드의 link를 pre의 link로 주었을 때 pre는 node2 이므로 node2의 link가 된다. 즉, NEW 노드의 link는 node4를 가리키게 되고 NEW data에 30을 저장한다. 다음 pre의 link를 NEW로 주게 되면 node2의 link가 NEW를 가리키게 되어 NEW 노드는 node3의 역할을 할 수 있게 된다.
삽입 전
| Data | Link | Data | Link | Data | Link |
| 10 | → | 20 | → | 40 | ↓ (첫 번째 노드) |
| ↑ | ← | ||||
| node1 | node2 | node4 | |||
삽입 후
| Data | Link | Data | Link |
| 20 | → | 40 | 첫 번째 노드 |
| pre = node2 | node4 | ||
| Data | Link |
| 30 | pre link |
| NEW | |
여기서 pre link가 가리키는 것은 node4다.
| Data | Link | Data | Link | Data | Link |
| 20 | NEW | 30 | pre link | 40 | 첫 번째 노드 |
| pre = node2 | NEW | node4 | |||
결국은 이렇게 마무리가 되는데 코드는 위에서부터 순서대로 진행하기 때문에 pre link는 위에서 가리켰던 node4가 된 후에 pre link가 NEW로 바뀌게 된다. 이렇게 되어서 20과 40 사이에 30이 삽입되는 것이다.
5. 원형 연결 리스트의 삭제
- 원형 연결 리스트에서 포인터 pre가 가리키는 노드의 다음 노드를 삭제하고 삭제한 노드는 자유공간 리스트에 반환하는 연산
- 포인터 old는 삭제할 노드 지시
1) 순서
- old <- pre.link;
- 노드 pre의 다음 노드를 삭제할 노드 old로 지정
- pre.link <- old.link;
- 노드 old의 이전 노드와 다음 노드를 서로 연결
2) C언어 실습
#include <stdio.h>
#include <stdlib.h>
typedef struct NODE {
int data;
struct NODE *link;
} NODE;
void main() {
NODE *head = NULL; // 머리 노드 생성
NODE *node1 = (NODE *)calloc(8, sizeof(NODE)); // 첫 번째 노드 생성
head = node1; // 머리 노드 다음은 첫 번째 노드
node1 -> data = 10; // 첫 번째 노드에 10 저장
NODE* node2 = (NODE *)calloc(8, sizeof(NODE)); // 두 번째 노드 생성
node1 -> link = node2; // 첫 번째 노드 다음은 두 번째 노드
node2 -> data = 20; // 두 번째 노드에 20 저장
NODE* node3 = (NODE *)calloc(8, sizeof(NODE)); // 세 번째 노드 생성
node2 -> link = node3; // 두 번째 노드 다음은 세 번째 노드
node3 -> data = 30; // 세 번째 노드에 40 저장
NODE* node4 = (NODE *)calloc(8, sizeof(NODE)); // 네 번째 노드 생성
node3 -> link = node4; // 두 번째 노드 다음은 네 번째 노드
node4 -> data = 40; // 네 번째 노드에 40 저장
node4 -> link = node1; // 네 번째 노드 다음은 첫 번째 노드를 가리킴
puts(" - 삭제 전 -");
head = node1;
NODE *curr = node1; // 연결 리스트 순회용 포인터에 첫 번째 노드의 주소 저장
do {
printf(" %d\n", curr -> data); // 현재 노드의 데이터 출력
curr = curr -> link; // 포인터에 다음 노드의 주소 저장
} while (curr != head); // 포인터가 head가 아닐 때 계속 반복
puts(" - 삭제 후 -");
NODE *pre, *old;
pre = node2;
old = node3;
pre -> link = old -> link;
curr = node1;
do {
printf(" %d\n", curr -> data); // 현재 노드의 데이터 출력
curr = curr -> link; // 포인터에 다음 노드의 주소 저장
} while (curr != head); // 포인터가 head가 아닐 때 계속 반복
free(node1); // 노드 메모리 해제
free(node2); // 노드 메모리 해제
free(node3); // 노드 메모리 해제
free(node4); // 노드 메모리 해제
}
위에서 설명했듯이 pre가 node2가 되고 old가 node3이 되어서 pre link를 old link로 저장하면 node3을 건너뛰고 node3이 가리키고 있던 node4가 출력되는 것이다.
'Language > C' 카테고리의 다른 글
| [자료구조] 스택(Stack) (0) | 2020.06.22 |
|---|---|
| [자료구조] 이중 연결 리스트(Doubly linked list) (0) | 2020.06.22 |
| [자료구조] 연결리스트 PART.2 (0) | 2020.06.21 |
| [자료구조] 연결리스트 PART.1 (0) | 2020.06.19 |
| [자료구조] 선형리스트 (0) | 2020.06.19 |
댓글