[자료구조] 6. 리스트(List)3 - 원형 연결 리스트 / 이중 연결 리스트

원형 연결 리스트에서는 어떤 노드에서든 다른 모든 노드로의 접근이 가능하다. 따라서 삽입과 삭제 연산이 단순 연결 리스트에 비해 용이하며, 특히 헤드 포인터가 마지막 노드를 가리키도록 구성한다면 리스트의 마지막에 노드를 삽입하거나 삭제하기 위해 리스트의 맨 끝까지 가지 않아도 되기 때문에 리스트의 끝에 노드를 삽입/삭제하는 연산이 효율적이다. 즉, 헤드 포인터 head가 마지막 노드를 가리키고, 첫 번째 노드는 head->link가 가리키도록 원형 연결 리스트를 조금 변형하면 원형 연결 리스트를 더 효율적으로 사용할 수 있다.

2) 노드 정의

단순 연결 리스트에서의 노드 정의와 동일하다.

// 노드 정의
typedef int element;   //노드에 저장할 요소의 자료형

typedef struct ListNode {      // 노드 정의
	element data;   
	struct ListNode* link;    
}ListNode

3) 원형 연결 리스트 연산 구현

[원형 리스트의 처음에 삽입]

새롭게 삽입할 노드의 링크인 node->link가 기존의 첫 번째 노드를 가리키게 하고, 마지막 노드의 링크는 삽입한 노드를 가리키도록 한다.

//원형 리스트 처음에 삽입
ListNode* insertFirst(ListNode* head, element data) {
	ListNode* node = (ListNode*)malloc(sizeof(ListNode));  //삽입할 노드 생성
	node->data = data;

	if (head = NULL) {    //리스트가 공백 상태인 경우
		head = node;
		node->link = head;
	}
	else {               //리스트가 공백 상태가 아닌 경우
		node->link = head->link;   //삽입할 노드의 링크가 첫 번째 노드를 가리킴
		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 {
		node->link = head->link;
		head->link = node;
		head = node;   //head의 위치를 삽입한 노드로 바꾸어줌
	}

	return head;
}

[항목 출력 연산]

원형 연결 리스트는 마지막 노드의 링크가 NULL이 아니기 때문에 리스트의 끝에 도달했는지를 검사하기 위해서는 헤드 포인터와 비교해야 한다. 방문하려는 항목이 head가 가리키는 노드이면 반복문을 탈출한다.

//원형 리스트의 항목 출력 연산
void print_list(ListNode* head) {
	ListNode* p;

	if (head == NULL) return;   //원형 리스트가 공백 상태인 경우
	
	p = head->link;     //첫 번째 노드

	do {
		printf("%d->", p->data);
		p = p->link;
	} while (p != head);
	printf("%d->", p->data);   //마지막 노드 출력
}

4) 원형 연결 리스트 정의/생성

단순 연결 리스트와 마찬가지로 원형 연결 리스트도 헤드 포인터만 있으면 된다.

ListNode *head;

6.2 이중 연결 리스트

1) 이중 연결 리스트란?

이중 연결 리스트 : 하나의 노드가 선행 노드와 후속 노드에 대한 두 개의 링크를 가지는 리스트.

단순 연결 리스트에서 후속 노드를 찾는 것은 쉽지만 선행 노드를 찾으려면 구조상 매우 어렵다. 이러한 문제점을 해결하는 자료구조가 이중 연결 리스트이다. 이중 연결 리스트는 링크가 양방향으로 구성되어 양방향으로 검색이 가능하므로 특정 노드에서 양방향으로 자유롭게 움질일 필요가 있다면 이중 연결 리스트를 사용해야 한다.

이중 연결 리스트는 실제 응용에서 이중 연결 리스트와 원형 연결 리스트를 혼합한 형태로 많이 사용되고,헤드 포인터 대신 헤드 노드를 별도로 추가하는 경우가 많다.

헤드 노드(head node)란 데이터를 가지고 있지 않는 특별한 노드이며 삽입/삭제 연산을 간편하게 하기 위해 존재한다.

* 헤드 포인터는 리스트의 첫 번째 노드를 가리키는 포인터이고, 헤드 노드는 구조체 변수이다.

2) 노드 정의

이중 연결 리스트에서의 노드는 3개의 왼쪽 링크 필드, 데이터 필드, 오른쪽 링크 필드로 이루어진다.

하나의 노드에서 다른 노드를 향해 앞뒤로 똑같이 이동할 수 있으므로 특정 노드를 가리키는 포인터를 p라고 할 때 다음의 관계가 성립한다. 헤드 노드를 사용할 경우 이러한 관계는 공백 리스트에서도 성립한다.

p = p->llink->rlink = p->rlink->llink

구조체를 이용한 노드의 정의는 다음과 같다.

// 노드 정의
typedef int element;   //노드에 저장할 요소의 자료형

typedef struct DListNode {      
	element data;
	struct DListNode* llink;   //왼쪽 링크 필드, 선행 노드를 가리키는 포인터
	struct DListNode* rlink;   //오른쪽 링크 필드, 후속 노드를 가리키는 포인터
}DListNode;

3) 이중 연결 리스트 연산 구현

[이중 연결 리스트 초기화]

이중 연결 리스트는 사용하기 전에 반드시 헤더 노드의 링크 필드들이 자기 자신을 가리키도록 초기화를 해야 한다.

//이중 연결 리스트 초기화
void init(DListNode* head) {
	head->llink = head;
	head->rlink = head;
}

[삽입 연산]

삽일합 새로 만들어진 노드의 링크는 아무런 정보도 가지고 있지 않아 변경하여도 안전하기 때문에 새로 만들어진 노드의 링크를 먼저 바꾸어 준 후, 기존의 노드 링크들을 바꾼다.

//삽입 연산
void dinsert(DListNode* before, element data) {    //새로운 데이터 노드를 선행 노드의 오른쪽에 삽입
	DListNode* newnode = (DListNode*)malloc(sizeof(DListNode));   //삽입할 노드 생성
	
	newnode->data = data;
	
	newnode->llink = before;           //새로운 노드를 선행 노드에 연결
	newnode->rlink = before->rlink;    //새로운 노드를 후속 노드에 연결

	before->rlink->llink = newnode;    //후속 노드를 새로운 노드에 연결
	before->rlink = newnode;           //선행 노드를 새로운 노드에 연결
}

[삭제 연산]

//삭제 연산
void ddelete(DListNode* head, DListNode* removed) {
	if (removed == head) return;   //리스트가 공백 상태인 경우

	removed->llink->rlink = removed->rlink;    //삭제할 노드의 선행 노드를 후행 노드에 연결
	removed->rlink->llink = removed->llink;    //삭제할 노드의 후행 노드를 선행 노드에 연결
	free(removed);     //메모리 반납
}

[항목 출력 연산]

//항목 출력 연산
void print_dlist(DListNode* head) {
	DListNode* p;
	for (p = head->rlink; p != head; p = p->rlink) {   //첫 번재 노드로 다시 돌아오면 리스트 순회 종료
		printf("<- |%d| -> ", p->data);
	}
	printf("\n");
}

4) 이중 연결 리스트 정의 /생성

DlistNode *head = (DListNode *)malloc(sizeof(DlistNode));    //헤드 노드 생성
init(head);     //초기화