[자료구조] 연결 리스트의 응용

연결 리스트의 변형

자료구조 강의 속 이미지

단순 연결 리스트

단순 연결 리스트의 문제점

• 하나의 링크 만 있고, 각각의 노드의 링크는 후행 노드만을 가리키는 구조.

→ 특정 노드의 후행 노드는 쉽게 접근 가능 하지만 , 선행 노드를 찾으려면 헤드 노드 부터 다시 검색 해야 함. (비 효율적)

이중 연결 리스트

• 선행과 후행을 가리키는 두개의 링크를 가진다.

→ 특정 노드에서 선행 노드와 후행 노드에 직접적으로(간단한 코드를 통해) 접근이 가능

원형 연결 리스트

• 연결 리스트를 살펴보면, 가장 마지막 노드의 링크 필드는 언제나 NULL

→ 리스트의 마지막 원소 뒤에는 아무 원소도 없기 때문에 연결 리스트의 마지막 노드의 링크 필드는 언제나 null

→ 마지막 노드의 필드를 활용하면서도 프로그램 성능에 도움이 되도록 하기 위해 원형 연결 리스트가 제안 됨.

원형 연결 리스트의 생성

• 정의 및 생성

typedef struct ListNode { // 원형 연결 리스트의 노드 구조 정의
				int data;
				struct ListNode * link;
} listNode;

typedef struct { // 원형 연결 리스트의 헤드 노드 구조 정의
		listNode * head;
} linkedList_h;

linkedList_h* createLinkedList_h(void) { // 원형 연결 리스트의 헤드 노드 생성
	linkedList_h* H;
	H = (linkedList_h*)malloc(sizeof(linkedList_h));
	H -> head = NULL;
	return H;
}

• 원형 연결 리스트의 노드 삽입

void addFirstNode(linkedList_h* H, int x){
// 원형 리스트 첫 번째 노드 삽입 연산, x 값은 100이라고 가정함

	listNode* tempNode;
	listNode* NewNode;
	NewNode = (listNode*)malloc(sizeof(listNode));
	NewNode = data = x;
	NewNode = link = NULL;
}

if(H -> head == NULL) { // 현재 원형 연결 리스트가 공백인 경우
	H -> head = NewNode;
	NewNode -> link = NewNode;
	return ;
}
else { // 현재 원형 연결 리스트가 공백이 아닌 경우
	tempNode = H -> head;
	while(tempNode -> link != H -> head)
					tempNode = tempNode -> link;
	NewNode -> link = tempNode -> link;
	tempNode -> link = NewNode;
	H -> head = NewNode;
	}
}

원형 연결 리스트가 공백일 경우

• 헤드 노드가 NewNode 를 가리키고, NewNode 가 NewNode의 값을 link 로 가리키는 모습

원형 연결 리스트의 노드가 존재 할 경우 (맨뒤)

• tempNode 의 값이 NewNode 를 가리키고, NewNode의 값이 tempNode 를 가리키는 모습

특정 노드 뒤에 삽입 할 경우

• 원형 연결 리스트 중간 위치 (prevNode 뒤에 삽입)에 삽입

NewNode -> link = prevNode -> link;
prevNode -> link = NewNode;
return;

원형 연결 리스트의 노드 삭제를 위한 탐색

• 원형 연결 리스트의 삭제 노드 탐색

void finddelCircularNode(linkList_h* H , itdata) {
// 원형 연결 리스트에서 삭제하려는 노드를 탐색하는 연산,
// itdata 값은 90이라고 가정함
	listNode* tempNode;
	listNode* prevNode;
	prevNode = H;
if(H -> head == NULL) { // 공백인 경우
	printf("Circular Linked List is EMPTY");
return;
}
 else{
	tempNode = H -> head ; // 첫번쨰 노드부터 검색하기 위함
		do{
			if(tempNode -> data == itdata) { // 찾는 노드값 검색
					return deleteCircularNode(H, prevNode);
			}
			// 찾았다면 삭제 함수 호출하며 검색 함수 는 끝
			else {
				prevNode = tempNode;
				tempNode = tempNode -> link;
			}
		} while(tempNode != H -> head);
	}
}

• 원형 연결 리스트의 삭제 노드 탐색 방법

→ tempNode 를 head 부터 → 하나씩 값을 이동 (prevNode도 동일) 값이 없으면 printf 호출 있으면 해당 위치 삭제.

이중 연결 리스트

이중 연결 리스트의 노드 구조

• 양쪽 방향으로 순회 할 수 있도록 링크 필드가 두개 필요함

→ 시작점(head) 도 두개의 링크 (Lhead, Fhead) 가 필요

• 이중 연결 리스트의 노드 구조 → 두개의 링크 필드 와 한개의 데이터 필드

이중 연결 리스트의 정의 및 생성

• 초기화

typedef struct ListNode {

// 이중 연결 리스트의 노드 구조 정의
		struct ListNode * Llink;
		int data;
		struct ListNode* Rlink;
}listNode;

typedef struct { // 이중 연결 리스트의 헤드 노드 구조 정의
	listNode* Lhead;
	listNode* Fhead;
} linkedList_h;

linkedList_h* createLinkedList_h(void) {
// 원형 연결 리스트의 헤드 노드 생성
		linkedList_h* H;
		H = (linkedList_h*)malloc(sizeof(linkedList_h));
		H -> Lhead = NULL;
		H -> Rhead = NULL;
		return H;
}

• 삽입 연산

void addDNode(linkedList_h* H, listNode* prevNode, int x){
// 이중 연결 리스트 노드 삽입 연산, x 값은 200 이라고 가정함
	listNode* NewNode;
	NewNode = (listNode*)malloc(sizeof(listNode));
	NewNode -> Llink = NULL;
	NewNode -> data = x;
	NewNode -> Rlink = NULL;

	NewNode -> Rlink = prevNode -> Rlink;
	prevNode -> Rlink = NewNode;
	NewNode -> Llink = prevNode;
	NewNode -> Rlink -> Llink = NewNode;

}

• 이중 연결 리스트의 특정 노드 삭제

void deleteDNode(linkedList_h* H , listNode* delNode){
// 이중 연결 리스트에서 데이터의 값이 300인 노드 (delNode) 를 삭제하는 연산

	delNode -> Llink -> Rlink = delNode -> Rlink;
	delNode -> Rlink -> Llink = delnode -> Llink;
	free(delNode);
}

정리하기

단순 연결 리스트

링크 부분이 하나만 있고 각각의 노드는 후행 노드만을 가리키는 구조

이중 연결 리스트

특정 노드에서는 선행 노드와 후행 노드에 대해 간단한 프로그램 코드를 통해 접근 할 수 있는 구조

원형 연결 리스트

NULL 값을 갖는 마지막 노드의 링크 부분을 활용하면서도 프로그램 성능에 도움을 주기 위해 제안, 한 방향으로 모든 노드가 원형으로 계속 연결 되어 있기 때문에 한 노드로부터 다른 어떤 노드로도 접근이 가능한 구조