[C] 연결리스트 : 원형, 이중연결리스트

다양한 연결리스트

---

[원형연결리스트]

 

단순연결리스트에 한계가 있음을 깨달았다 ...

원형연결리스트를 이용해 삽입 삭제를 더 편리하게 해보자!

 

단순연결리스트에서는 마지막 노드가 NULL을 가리켰지만

원형연결리스트에서는 마지막 노드가 첫 번째 노드를 가리킨다.

 

원형연결리스트를 이용하면 맨 뒤에 노드를 삽입하는 것이 용이해진다!

헤드 포인터가 마지막 노드를 가키리도록 구성하자.

 

헤드 포인터를 첫 번째 노드를 가키리도록 하면

마지막 노드를 접근하기 위해 모든 노드들을 다 거쳐가야하고,

비효율적으로 동작하기 때문에 헤드 포인터가 마지막 노드를 가리켜야한다 ㅠ ㅠ

 

print_list(list)

insert_first(list, data)

insert_last(list, data)

를 이용해서 원형연결리스트를 구현해보자

 

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

typedef int element;
typedef struct ListNode {
	element data;
	struct ListNode* link;
}ListNode;

void print_list(ListNode* head) {
	ListNode* p = head->link;
	
	//비어있으면 print 안함
	if (head == NULL) return;

	//단순연결과 달리 null을 가리키는 포인트가 없으므로
	//p가 head 가 아닐 때 까지 print 해야 함
	//그러므로 while이 아니라 do while로!!
	do {
		printf("%d->", p->data);
		p = p->link;
	} while (p != head->link);
	printf("탐색 끝!\n\n");
}

ListNode* insert_first(ListNode* head, element data) {
	ListNode* node = (ListNode*)malloc(sizeof(ListNode));
	node->data = data;
	//연결리스트가 비어있으면 head는 새로 삽입한 node가 됨
	if (head == NULL) {
		head = node;
		//데이터가 하나일 경우, 원형연결이므로 link는 자기자신을 가리키게됨
		node->link = head;
	}
	else {
		//이미 데이터가 있으면, 새로운 노드의 링크는 원래 헤드의 링크를 가리킴
		// example) 1 2 3 1 2 3 .. 인 원형일 경우
		// 맨 앞에 0을 삽입하면 0 노드의 링크는 1을 가리킴
		node->link = head->link;
		// example) 현재 head는 3이므로, head의 링크는 0을 가리켜야함
		//-> 0 1 2 3 0 1 2...
		head->link = node;
	}
	return head;
}

ListNode* insert_last(ListNode* head, element data) {
	ListNode* node = (ListNode*)malloc(sizeof(ListNode));
	node->data = data;
	if (head == NULL) {
		head = node;
		node->link = head;
	}
	else {
		// example) 1 2 1 2.. 원형연결리스트의 경우
		// 1 2 3 1 2 3 ..으로 3을 삽입해보자
		//새로운 node 3 의 링크는 첫번째 노드를 가리켜야함
		//head가 마지막 노드이므로 첫번째 노드는 head->link
		node->link = head->link;
		//원래 마지막 노드였던 head의 링크는 새로운 마지막 노드인 node를 가리켜야함
		head->link = node;
		//head를 마지막 노드(=새로 삽입한 노드)로 변경
		head = node;
	}
	return head;
}

int main() {
	ListNode* head = NULL;
	element i;
	for (i = 20; i <= 40; i += 10) {
		head = insert_last(head, i);
		print_list(head);
	}
	head = insert_first(head, 10);
	print_list(head);
	//20
	//20 30
	//20 30 40
	//10 20 30 40 순으로 삽입
	
}

 

출력 결과

---

[이중연결리스트]

 

원형연결리스트에서는 선행 노드를 찾지 못한다.

10 20 30 의 경우에 20 뒤에 30이 있는 것은 아는데

20 전에 어떤 데이터가 있는지 찾지 못한다.

이 문제를 해결하기 위해 이중연결리스트가 만들어졌다고 한다.

 

이중연결리스트에는 다음 노드를 가리키는 link뿐만 아니라

이전 노드를 가리키는 노드까지 link가 2개 존재한다.

그래서 공간을 많이 차지하고 코드가 복잡해진다.

하지만 여러 장점이 많아서 널리 쓰인다고 한다.

 

이중연결리스트에는 3개의 필드가 존재한다.

왼쪽 링크, 오른쪽 링크, 데이터 필드.

 

p의 왼쪽 링크의 오른쪽 링크는 자기자신인 p이며

p의 오른쪽 링크의 왼쪽 링크도 자기자신인 p이다.

 

10 20 30 의 경우,20의 왼쪽 링크는 10, 오른쪽 링크는 30을 가리키고

30의 왼쪽 링크는 20, 오른쪽 링크는 10을 가리킨다.

(원형 느낌~)

 

여기서 head는 구조체 변수이다

(head 포인터가 아님!)
head 포인터는 첫 번째 노드를 가리키는 포인터이고
head 노드는 데이터를 가지고 있지 않는 특별한 노드이다

 

단순, 원형 연결 리스트에서는 head가 포인터였지만

이중 연결 리스트에서는 head가 노드로 쓰이는 점 유의하자!

 

#include<stdio.h>
#include<stdlib.h> // 동적할당시 이용

typedef int element;

typedef struct DListNode {
	struct DListNode* llink; //이전 노드 가리키는 링크
	element data;
	struct DListNode* rlink; //다음 노드 가리키는 링크
}DListNode;

//이중연결리스트 초기화
//노드 하나의 경우 왼쪽 링크도 자기자신을,
//오른쪽 링크도 자기자신을 가리킨다.
//공백 리스트에서도 마찬가지
void init(DListNode* phead) {
	phead->llink = phead;
	phead->rlink = phead;
}

void dinsert(DListNode* before, element data) {
	//before의 오른쪽에 삽입, before가 이전 노드가 됨
	DListNode* newnode = (DListNode*)malloc(sizeof(DListNode));
	newnode->data = data;

	//before, newnode, next 노드가 있다고 하면
	//새 노드의 왼쪽 링크를 before로
	newnode->llink = before;

	//새 노드의 오른쪽 링크를, next 노드로
	newnode->rlink = before->rlink;

	//next노드의 왼쪽 링크를 newnode로 하고자 함
	before->rlink->llink = newnode;

	//before노드의 오른쪽 링크를 newnode로
	before->rlink = newnode;
}

void ddelete(DListNode*head, DListNode*removed) {
	if (removed == head) return;

	// 10 20 30 의 경우, 20을 지우고자 하면
	// 20의 이전인, 10 노드의 오른쪽 링크(removed->llink->rlink)를
	// 20의 오른쪽 링크(removed->rlink) = 즉 30을 가리키게한다
	//그러면 10 다음에 30이 온다. 20은 사라지고
	removed->llink->rlink = removed->rlink;

	//10 20 30 에서 20을 지우고자 할 때,
	// 30의 왼쪽 링크를 10을 가리키게 해야함!
	removed->rlink->llink = removed->llink;
	free(removed);
}

void print_dlist(DListNode* phead) {
	DListNode* p;
	for (p = phead->rlink; p != phead; p = p->rlink)
		printf(" <- [%d] -> ", p->data);
	printf("\n");
}

int main() {
	DListNode* head = (DListNode*)malloc(sizeof(DListNode));
	init(head);

	int i;
	for (i = 40; i >= 10; i -= 10) {
		dinsert(head, i);
		print_dlist(head);
	}

	//여기서 head는 구조체 변수이다 (head포인터가 아님!)
	//head포인터는 첫 번째 노드를 가리키는 포인터이고
	//head노드는 데이터를 가지고 있지 않는 특별한 노드이다
	
	//head의 llink를 삭제하면 40인 마지막 노드 삭제
	//head의 rlink를 삭제하면 10인 첫번째 노드 삭제

	ddelete(head, head->llink);
	print_dlist(head);
	free(head);
}

출력 결과

 

 

 

[참고자료] C언어로 쉽게 풀어 쓴 자료구조, 생능출판, 천인국 공용해 하상호 지음