JArchive 프로그래밍 일기

더블 링크드 리스트란

링크드 리스트의 탐색 기능을 개선한 자료구조입니다.

자신의 앞에 있는 노드를 가리키는 포인터도 있어서, 앞으로도 뒤로도 이동할 수 있습니다. 

다음은 더블 링크드 리스트를 표현한 구조체입니다. 

typedef struct Node {
	struct Node* prevNode;
	int Data;
	struct Node* nextNode;
}Node;

특별한건 없고 '앞 노드'를 처리하기 위한 포인터만 추가됩니다. 

노드 생성

다음은 노드를 생성하는 CreateNode() 함수 입니다. 

'앞 노드'를 가리키는 prevNode 포인터를 NULL로 초기화 하는것 말고는 싱글 링크드 리스트와 똑같습니다. 

Node* CreateNode(int data) {

	Node* newNode = (Node*)malloc(sizeof(Node));
    
	newNode->data = data;
	newNode->prevNode = NULL;
	newNode->nextNode = NULL;

	return newNode;
}

노드 추가

테일을 찾아서 새 노드를 추가합니다. 

새 노드의 prevNode 포인터가 tail 노드를 가리키도록 합니다. 

void AppendNode(Node** head, Node* newNode) {
	
	if (NULL == (*head)) { //헤드 노드가 없다면, 새 노드가 헤드 노드
		(*head) = newNode;
	}
	else {  // 테일 노드를 찾아서, 테일 뒤에 새 노드를 덧붙인다 
		Node* tail = (*head);

		while (NULL != tail->nextNode) {
			tail = tail->nextNode;
		}

		newNode->prevNode = tail;
		tail->nextNode = newNode;

	}
}

헤드 노드가 없으면, 새 노드가 헤드 노드가 됩니다. 

그렇지 않으면, 현재 노드가 테일 노드가 될 때까지 이동하고,

테일을 찾아내면,새 노드의 이전이 테일이고, 테일의 다음 노드가 새 노드가 되도록 포인터 변수값을 넣습니다.

노드 삭제

조금 어려운 부분입니다.

변경 해야 할 노드의 포인터가 4개이기 때문입니다.

앞 노드, 삭제할 노드, 뒷 노드  순으로 존재한다고 가정할 때, 

삭제할 노드의 '앞 노드'와 삭제할 노드의 '뒷 노드'의 포인터를 포함하여 총 4개입니다. 

void RemoveNode(Node** head, Node* target) {

	printf("[RemoveNode] %2d를 삭제합니다.\n", target->data);

	if ((*head) == target) { // 헤드를 삭제하는 경우, 
		// 헤드를 변경 
		(*head) = target->nextNode;

		if (NULL != (*head)) {
			(*head)->prevNode = NULL;
		}
		// 타겟을 제거 
		target->nextNode = NULL;
		target->prevNode = NULL;
		free(target);
	}
	else { 
		// temp = 타겟
		Node* temp = target;

		// temp의 앞과 temp의 뒤를 이어준다 (타겟의 앞과 뒤를 이어준다)
		temp->prevNode->nextNode = temp->nextNode;

		if (NULL != temp->nextNode) {
			temp->nextNode->prevNode = temp->prevNode;
		}

		target->nextNode = NULL;
		target->prevNode = NULL;
		free(target);
	}
}

삭제할 노드의 '앞 노드'가 삭제할 노드의 '뒷 노드'를 가리키도록 변경합니다. 

'뒷 노드'의 prevNode* 가 '앞 노드'의 nextNode*를 가리키도록 변경합니다. 

삭제할 노드의 앞뒤 포인터 두 개를 전부 NULL을 가리키도록 변경합니다. 

중복을 제거한 다음 코드도 정상 동작합니다. 

void RemoveNode(Node** head, Node* target) {

	printf("[RemoveNode] %2d를 삭제합니다.\n", target->data);

	if ((*head) == target) { // 헤드를 삭제하는 경우, 
		// 헤드를 변경 
		(*head) = target->nextNode;

		if (NULL != (*head)) {
			(*head)->prevNode = NULL;
		}
	}
	else { 
		// temp = 타겟
		Node* temp = target;

		// temp의 앞과 temp의 뒤를 이어준다 (타겟의 앞과 뒤를 이어준다)
		temp->prevNode->nextNode = temp->nextNode;

		if (NULL != temp->nextNode) {
			temp->nextNode->prevNode = temp->prevNode;
		}
	}

	target->nextNode = NULL;
	target->prevNode = NULL;
	free(target);

}

노드 삽입 

기준 노드(current) 뒤에 새 노드(newNode)를 삽입하는 것이므로 새 노드의 포인터만 주의하면 됩니다.

새 노드의 뒤 노드는 기준노드의 다음 노드를 가리킵니다.

새 노드의 앞 노드는 기준노드를 가리킵니다.

기준노드의 다음노드의 앞 포인터(current->nextNode->prevNode)와 기준노드의 뒷 포인터(current->nextNode)를 수정합니다. 

void InsertAfter(Node* current, Node* newNode) {

	newNode->prevNode = current;
	newNode->nextNode = current->nextNode;

	if (NULL != current->nextNode) {
		current->nextNode->prevNode = newNode;
	}

	current->nextNode = newNode;
}

전체 코드 입니다. 

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


// 더블 링크드 리스트 

/* 노드 선언 */
typedef struct Node {
	struct Node* prevNode;
	struct Node* nextNode;
	int data;
};


/* 노드 생성 */
Node* CreateNode(int data) {
	
	Node* newNode = (Node*)malloc(sizeof(Node));
	newNode->data = data;
	newNode->prevNode = NULL;
	newNode->nextNode = NULL;

	return newNode;
}

/* [공통] 노드 탐색 */
Node* GetLocation(Node* head, int location) {
	printf("[GetLocation]%d번째 노드를 찾아보자. \n", location);

	Node* current = head;

	while ((NULL != current) && (--location) >= 0) {
		printf("location : %d 번째 탐색 \n", location);
		current = current->nextNode;

	}

	return current;
}


/* [공통] 리스트 출력 */
void PrintList(Node* head) {
	printf("[PrintList] 리스트 전체를 출력합니다. \n");

	Node* tempNode = head;
	int count = 0;

	while (NULL != tempNode) {
		printf("%5d", tempNode->data);
		tempNode = tempNode->nextNode;
		count++;
	}
	printf("\n");
	printf("%5d개의 노드가 있습니다.\n", count);
}

/* 노드 추가. 테일 뒤에 새 노드를 덧붙인다 */
void AppendNode(Node** head, Node* newNode) {

	printf("[AppendNode] 데이터 %2d 추가합니다. \n", newNode->data);

	if (NULL == (*head)) { //헤드 노드가 없다면, 새 노드가 헤드 노드
		(*head) = newNode;
	}
	else {  // 테일 노드를 찾아서, 테일 뒤에 새 노드를 덧붙인다 
		Node* tail = (*head);

		while (NULL != tail->nextNode) {
			tail = tail->nextNode;
		}

		newNode->prevNode = tail;
		tail->nextNode = newNode;
	}
}

/* 노드 삭제 */
void RemoveNode(Node** head, Node* target) {

	printf("[RemoveNode] %2d를 삭제합니다.\n", target->data);

	if ((*head) == target) { // 헤드를 삭제하는 경우, 
		// 헤드를 변경 
		(*head) = target->nextNode;

		if (NULL != (*head)) {
			(*head)->prevNode = NULL;
		}

	}
	else { 
		// temp = 타겟
		Node* temp = target;

		// temp의 앞과 temp의 뒤를 이어준다 (타겟의 앞과 뒤를 이어준다)
		temp->prevNode->nextNode = temp->nextNode;

		if (NULL != temp->nextNode) {
			temp->nextNode->prevNode = temp->prevNode;
		}
	}

	target->nextNode = NULL;
	target->prevNode = NULL;
	free(target);

}

/* 노드 삽입. 특정 노드 뒤에 새 노드를 삽입한다. */
void InsertAfter(Node* current, Node* newNode) {

	printf("[InsertAfter] %2d를 %d 뒤에 삽입합니다.\n", newNode->data, current->data);

	newNode->prevNode = current;
	newNode->nextNode = current->nextNode;

	if (NULL != current->nextNode) {
		current->nextNode->prevNode = newNode;
	}

	current->nextNode = newNode;
}

int main() {

	Node* list = NULL;

	AppendNode(&list, CreateNode(10));
	AppendNode(&list, CreateNode(20));
	AppendNode(&list, CreateNode(30));

	PrintList(list);

	// 2번째 노드 위치 탐색(인덱스 1)
	// 2번째 노드 삭제 
	RemoveNode(&list, GetLocation(list, 1));

	PrintList(list);

	// 헤드 뒤에 삽입
	InsertAfter(list, CreateNode(40));
	PrintList(list);

	// 3번째 노드(인덱스 2) 뒤에 삽입 
	InsertAfter(GetLocation(list, 2), CreateNode(50));
	PrintList(list);

	return 0;
}

콘솔 화면 입니다.

다음 포스팅은 '환형 링크드 리스트' 입니다.