C로 만드는 자료구조-이중 연결 리스트

이중 연결 리스트(Doubly Linked List)란?

 이중 연결 리스트는 노드들이 양방향으로 연결되어 있는 연결 리스트를 말한다.

그림과 같이 이중 연결 리스트는 노드들을 양방향으로 연결하기 위해 링크를 2개씩 가지고 있다.
이때 왼쪽으로 가는 링크는 pLLink 오른쪼으로 가는 링크는 pRLink라고 할것이고 이중 연결 리스트에서는 다음과 같은 식이 성립한다.

pNode==pNode->pLLink->pRLink;

 

이중 리스트의 장점

 원형 리스트는 양방향으로 연결되어 있기 때문에 어떠한 노드에 접근할때 정해진 방향으로만 가야하는 단순 연결 리스트,원형 연결 리스트에 비해 용이하다. 예를 들어 위치 인데스 position에 존재하는 노드를 이용해 position 이전에 있는 노드에 접근하라고 한다면 단순/원형 연결 리스트는 처음부터 position-1 까지 순회해야 할것이다. 그러나 이중 연결 리스트에서는 간단하게 앞으로 가는 링크를 이용하면 된다. 

이중 연결 리스트 구현

 이중 연결 리스트의 기본구조 또한 단순 연결 리스트와 비슷하다. 기존에는 오른쪽으로 가는 링크만 신경 써주었다면 이제 왼쪽으로 가는 링크도 생각해주어야 한다.자세한 설명은 함수 구현 부분에서 하겠다.

소스 파일의 구성은 다음과 같다.

파일 이름	내용
Doublyinkedlist.h	구조체 및 함수 선언
Doublylinkedlist.cpp	함수 구현
DoublyLinkedListMain.cpp	main 함수 실행

1.Doublyinkedlist.h

#pragma once
#include<iostream>
using namespace std;

#define TRUE  1
#define FALSE 0

typedef struct DoublyListNode{
	int data;
	struct DoublyListNode* pLLink;
	struct DoublyListNode* pRLink;
};
typedef struct DoublyList {
	int currentElementCount;
	DoublyListNode headerNode;
};

DoublyList* createDoublyList();//연결 리스트 생성
void deleteDoublyList(DoublyList* pList);// 리스트 삭제
int addDLElement(DoublyList* pList, int position, DoublyListNode element);//리스트에 원하는 위치에 자료 추가
int removeDLElement(DoublyList* pList, int position);// 리스트에서 해당위치에 존재하는 자료 제거
void clearDoublyList(DoublyList* pList);//리스트 비우기
int getDLELength(DoublyList* pList);// 리스트 길이 반환
DoublyListNode* getDLElement(DoublyList* pList, int position);//리스트에서 해당위치에 존재하는 자료 반환
void displayDoublyList(DoublyList* pList);// 리스트에 저장되어 있는 원소 출력

- DoublyListNode는 DuoblyList에 저장될 노드를 의미하며 자료(data)와 왼쪽으로 가는 링크(pLLink), 오른쪽으로 가는 링크(pRLink)로 구성되어 있다.
- DoublyList는 실질적인 이중 연결 리스트를 의미하며 현재 저장 중인 원소의 개수(currentElementCount)와 리스트의 기능 구현을 쉽게 하기 위한 더미(Dummy) 노드인 헤더 노드(headerNode)로 구성되어 있다.
추가적으로 #define을 이용해 TURE은 1, FALSE는 0 값으로 정의해주었다.

2.DoublyList.cpp

- createCircularList()

DoublyList* createDoublyList() {
	DoublyList* pReturn = NULL;
	pReturn = new pReturn
	if (pReturn != NULL) {
		memset(pReturn, 0, sizeof(DoublyList));
		pReturn->headerNode.pLLink = &(pReturn->headerNode);
		pReturn->headerNode.pRLink = &(pReturn->headerNode);
	}
	else {
		cout << "메모리 할당 오류" << endl;
		return NULL;
	}
	return pReturn;
}

단순 연결 리스트와 똑같은 형식인데 일단 헤더 노드의 링크들을 자기 자신을 가리키게 해주었다.

- addCLElement()

단순 연결 리스트때와 마찬가지로 추가하려는 곳의 위치 인덱스(position) 이전에 위치한 노드(pPreNode)를 찾은 후 새로 추가한 노드(pNewNode)와 링크를 재설정 해주면 된다.

pNewNode->pLLink = pPreNode; // 1
pNewNode->pRLink = pPreNode->pRLink; // 2 
pPreNode->pRLink = pNewNode; // 3
pNewNode->pRLink->pLLink = pNewNode; // 4

코드 구현은 다음과 같다.

int addDLElement(DoublyList* pList, int position, DoublyListNode element) {
	int ret = 0;
	DoublyListNode *pPreNode = NULL, *pNewNode = NULL, *pTempNode = NULL;
	if (pList != NULL) {
		if (position >= 0 && position <= pList->currentElementCount) {
			pNewNode = (DoublyListNode*)malloc(sizeof(DoublyListNode));
			if (pNewNode == NULL) {
				cout << "메모리할당오류 pNewNode" << endl;
				return ret;
			}
			*pNewNode = element;
			pNewNode->pLLink = NULL;
			pNewNode->pRLink = NULL;

			pPreNode = &(pList->headerNode);
			for (int i = 0; i < position; i++) {
				pPreNode = pPreNode->pRLink;
			}
			pNewNode->pLLink = pPreNode;
			pNewNode->pRLink = pPreNode->pRLink;
			pPreNode->pRLink = pNewNode;
			pNewNode->pRLink->pLLink = pNewNode;

			pList->currentElementCount++;
			ret = TRUE;
		}
		else {
			cout << "위치 인덱스 오류" << endl;
		}
	}
	return ret;
}

- removeCLElement()

 마찬가지로 제거하려는 노드(pDelNode)와 제거하려는 노드 이전에 위치한 노드(pPreNode)를 찾아내어 링크를 재설정 해주면 된다.

pPreNode->pRLink = pDelNode->pRLink; // 1
pDelNode->pRink->pLLink = pPreNode;  //2
delete pDelNode;

코드 구현은 다음과 같다.

int removeDLElement(DoublyList* pList, int position) {
	int ret = FALSE;
	DoublyListNode *pPreNode = NULL, *pDelNode = NULL, *pTempNode = NULL;

	if (pList != NULL) {
		if (position >= 0 && position < pList->currentElementCount) {
			pPreNode = &(pList->headerNode);
			for (int i = 0; i < position; i++) {
				pPreNode = pPreNode->pRLink;
			}
			pDelNode = pPreNode->pRLink;

			pPreNode->pRLink = pDelNode->pRLink;
			pDelNode->pRLink->pLLink = pPreNode;
			delete pDelNode;

			pList->currentElementCount--;
			ret = TRUE;
		}
	}
	else {
		cout << "위치 인덱스 오류" << endl;
	}
	return 0;
}

 

나머지 함수 구현 코드는 다음과 같다.

DoublyListNode* getDLElement(DoublyList* pList, int position) {
	DoublyListNode* pNode = NULL;
	if (pList != NULL) {
		if (position >= 0 && position < pList->currentElementCount) {
			pNode = pList->headerNode.pRLink;
			for (int i = 0; i < position; i++) {
				pNode = pNode->pRLink;
			}
		}
	}
	return pNode;
}//리스트에서 해당위치에 존재하는 자료 반환

void clearDoublyList(DoublyList* pList) {
	if (pList != NULL) {
		while (pList->currentElementCount > 0) {
			removeDLElement(pList, 0);
		}
	}
}//리스트 비우기
int getDLELength(DoublyList* pList) {
	int ret = 0;
	if (pList != NULL) {
		ret = pList->currentElementCount;
	}
	return ret;
}// 리스트 길이 반환
void deleteDoublyList(DoublyList* pList) {
	if (pList != NULL) {
		clearDoublyList(pList);
		delete pList;
	}
}// 리스트 삭제
void displayDoublyList(DoublyList* pList) {
	if (pList != NULL) {
		cout << "현재 원소의 개수: " << pList->currentElementCount << endl;
		for (int i = 0; i < pList->currentElementCount; i++) {
			cout << getDLElement(pList, i)->data << '\t';
		}
	}
	else {
		cout << "원소가 존재하지 않습니다." << endl;
	}
	cout << endl;

}

3.DoublyLinkedListMain.cpp

메인 함수 실행 코드는 다음과 같다.

#include "stdafx.h"
#include"doublylist.h"

int main()
{
	DoublyList *pList = NULL;
	DoublyListNode* pNode = NULL;
	DoublyListNode node;

	pList = createDoublyList();

	if (pList != NULL) {
		node.data = 1;
		addDLElement(pList, 0, node);
		

		node.data = 3;
		addDLElement(pList, 1, node);
		
		node.data = 5;
		addDLElement(pList, 0, node);
		displayDoublyList(pList);

		removeDLElement(pList, 1);
		displayDoublyList(pList);

		deleteDoublyList(pList);
	}


	return 0;
}

실행결과는 다음과 같다.