문과생이 이해한 원형 연결리스트

출처 : <c언어로 쉽게 풀어쓴 자료구조> + 학교 수업

 

<전체코드>

#include<stdio.h>
#include<stdlib.h>

typedef struct {
	int data;
	struct node* link;
}node;

void print_node(node* head) {
	node* p;

	if (head == NULL) return;
	p = head->link;
	do {
		printf("%d -> ", p->data);
		p = p->link;
	} while (p != head);
	printf("%d->", p->data);
}

node* insert_first(node* head, int data) {
	node* p = (node*)malloc(sizeof(node));
	p->data = data;
	if (head == NULL) {
		head = p;
		p->link = head;
	}else {
		p->link = head->link;
		head->link = p;
	}
}

node* insert_last(node* head, int data) {
	node* p = (node*)malloc(sizeof(node));
	p->data = data;
	if (head == NULL) {
		head = p;
		p->link = p;
	}else {
		p->link = head->link;
		head->link = p;
		head = p;
	}
}

int main() {
	node* head = NULL;

	head=insert_last(head, 20);
	head=insert_last(head, 30);
	head=insert_last(head, 40);
	head=insert_first(head, 10);
	print_node(head);

	return 0;
}

 

1.  head==NULL일 때 삽입 연산

 

 

---

 

 

2. head!=NULL일 때 삽입 연산

 2-1) 

 

 2-2) 

 

---

 

 

3. insert_first(head,10)

 

 

<최종 형태>

 

 

 

---

 

 

 원형 리스트의 삽입 연산은 head의 앞에 넣을 건지, 뒤에 넣을 건지가 나눠져 있다. head의 뒤에 넣으면 그 노드로 head의 포인터도 변하고, head의 앞에 넣으면 head->link만 새 노드로 향하게 된다. 

 

 원형 리스트의 장점은 헤드 포인터가 마지막 노드를 가리키도록 구성한다면, 리스트의 처음과 끝 노드에 간편하게 값 삽입이 가능하다. 특히 단일 연결리스트에서서 리스트의 맨 끝에 노드를 삽입하려면 반복문을 통해서 첫번째 노드에서 끝까지 가야하지만, 원형 리스트에서는 그렇게 하지 않아도 된다. 

 

 

(+) 위와 같은 이유로 원형 연결리스트는 '상수 시간' 안에 처음과 끝에 노드를 삽입할 수 있다고 한다. 

ko.wikipedia.org/wiki/%EC%83%81%EC%88%98_%EC%8B%9C%EA%B0%84

상수 시간 - 위키백과, 우리 모두의 백과사전

 

 

---

  

 

 마지막으로 이것도 이중 포인터로 바꿔서 해봤는데 오류가 뜬다.