이중 연결 리스트 Doubly Linked List

이번에 소개할 자료구조는 이중 연결 리스트 입니다.

---

1. 이중 연결 리스트

이중 연결 리스트 혹은 양방향 연결 리스트라고 불리우는 이 자료도 연결 리스트의 일종입니다. 지난번 원형 연결 리스트와 마찬가지로 한 가지 개념만 추가하면 되는데요. 바로 링크필드가 양옆에 있다는 점입니다.

지난번 까지 알아본 리스트의 노드들은 다음과 같이 구성되어있었습니다.

하지만 양방향 링크 필드의 노드는 다음과 같이 구성됩니다.

편의상 앞의 링크 필드는 '왼쪽 링크 필드', 뒤의 링크 필드는 '오른쪽 링크 필드'라고 명명하고 넘어가겠습니다. 왼쪽 링크 필드는 현재 노드의 이전 노드를 가리키고, 오른쪽 링크 필드는 현재 노드의 다음 노드를 가리킵니다. 이렇게 한 노드에서 양방향의 링크를 가리킨다 해서 양방향, 선모양으로 펼쳐놓으면 마치 두개의 리스트가 있는 것 같아서 이중 연결 리스트라고 불리우게 됩니다.

 

 

2. 이중 연결 리스트 구현

2-1. 노드 구현

typedef struct ListNode {
	struct ListNode* leftNode;	//왼쪽 링크 필드
	char* data[10];	//데이터 필드
	struct ListNode* rightNode;	//오른쪽 링크 필드
}listNode;

위의 그림대로 정의한 노드 구조체입니다. 순서대로 선언했는데 구조가 감이 잡히시나요?

 

 

2-2. 노드 삽입 하기

이번에는 노드를 삽입하는 것을 구현할 것인데 지금까지 본 삽입과는 접근 방식이 조금 다릅니다. 물론 구현은 비슷합니다.

구조를 생각해보면 이중 연결 리스트지만 원형 리스트처럼 끝노드와 시작노드가 딱히 따로 정해져있지는 않습니다. 그래서 삽입 구현시 맨앞, 맨뒤에 넣는 연산 없이 그냥 삽입 연산 한가지만 구현하면 됩니다. 

삽입 전

삽입을 진행하면 위와 같은 형태로 이전 노드의 오른쪽 링크 필드는 삽입한 노드를, 다음 노드의 왼쪽 링크 필드는 삽입한 노드를 가리켜야 합니다. 또한 삽입한 노드의 왼쪽 링크 필드는 이전 노드를, 오른쪽 링크 필드는 다음 노드를 가리키는 식으로 연결해주기만 하면 됩니다.

void insertNode(linkedList_h* DL, listNode* pre, char* x) {
	listNode* newNode;

	newNode = (listNode*)malloc(sizeof(listNode));
	strcpy(newNode->data, x);

	//리스트가 비어있는 경우
	if (DL->head == NULL) {
		newNode->rightNode = NULL;
		newNode->leftNode = NULL;
		DL->head = newNode;
	}
	else {
		newNode->rightNode = pre->rightNode;  //삽입 노드의 오른쪽 링크 필드를 이전 노드의 오른쪽 링크 필드가 가리키는 노드로 설정
		pre->rightNode = newNode;  //이전 노드의 오른쪽 링크 필드가 새 노드를 가리키게 설정
		newNode->leftNode = pre;  //새 노드의 왼쪽 링크 필드가 이전 노드를 가리키게 설정

		if (newNode->rightNode != NULL) {
        	//만약 삽입한 노드가 마지막 노드가 아니라면 실행
        	//새노드의 오른쪽 링크 필드가 가리키는
        	//즉, 다음 노드의 왼쪽 필드가 새 노드를 가리키게 설정
			newNode->rightNode->leftNode = newNode;
		}
	}
}

 

마지막 if문이 조금 난해할 수도 있는데요 바로 이 부분을 구현한 것 입니다.

 

 

2-3. 노드 삭제 하기

삭제 연산은 역시 삽입 연산의 반대로의 경우를 생각하면 되기 때문에 어렵지 않습니다. 삭제하고 노드끼리 서로를 가리키게 하면 됩니다.

void deleteNode(linkedList_h* DL, listNode* oldNode) {
	if (DL->head == NULL) {
		return;
	}
	else if (oldNode == NULL) {
		return;
	}
	else {
    	//삭제 노드의 왼쪽 필드가 가리키는 노드의 오른쪽 필드를
        //삭제 노드의 오른쪽 필드가 가리키게 설정
		oldNode->leftNode->rightNode = oldNode->rightNode;
        
        //그 반대로 오른쪽 필드의 설정 과정
		oldNode->rightNode->leftNode = oldNode->leftNode;

		free(oldNode);
	}
}

else문이 본격적으로 이중 연결 리스트의 삭제 연산입니다.

 

oldNode->leftNode->rightNode = oldNode->rightNode;

이 명령이 다음과 같은 의미를 가집니다. 반대의 경우도 마찬가지겠죠.

---

 

이렇게 해서 자료구조의 첫 관문 리스트 부분을 마쳤습니다. 다음 포스트로는 스택과 큐를 준비해오겠습니다.