이중 연결 리스트

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

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

그러면 이중 연결 리스트를 한 번 구현해보도록 하겠습니다.

노드 정의

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

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

노드 삽입

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

구조를 생각해보면 이중 연결 리스트지만 원형 리스트처럼 끝노드와 시작노드가 딱히 따로 정해져있지는 않습니다. 그래서 삽입 구현시 맨 앞, 맨 뒤에 넣는 연산 없이 그냥 삽입 연산 한가지만 구현하면 됩니다.이 상태에서 삽입을 하면삽입을 진행하면 위와 같은 형태로 이전 노드의 오른쪽 링크 필드는 삽입한 노드를, 다음 노드의 왼쪽 링크 필드는 삽입한 노드를 가리킵니다. 또한 삽입한 노드의 왼쪽 링크 필드는 이전 노드를, 오른쪽 링크 필드는 다음 노드를 가리키는 식으로 연결해주기만 하면 됩니다.

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문이 조금 난해할 수도 있는데요 바로 이 부분을 구현한 것 입니다.

노드 삭제

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

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;

else문 내부의 해당 코드는 다음과 같은 의미를 갖습니다.

---

전체 코드는 GitHub에서 확인하실 수 있습니다.