[자료구조/알고리즘]03. 이중 연결 리스트 Double Linked List

레거시/레거시-자료구조 2019. 1. 19. 00:38

CH 03 이중 연결 리스트(Double Linked List)

목표

연결 리스트의 응용 중 하나인 이중 연결 리스트에 대해 알아보고, C/C++ 프로그래밍 언어로 구현해봄으로써 연결 리스트의 이해의 깊이를 늘려보세요!

배열의 한계를 뛰어넘기 위해서, 연결 리스트란 자료 구조를 공부하였습니다. 그러나 연결 리스트에도 불편함이 있지요? 무슨 불편함이냐면, 분명히 꼬리 부분 tail 의 위치를 알고 있음에도, 꼬리 삭제 시에 꼬리 이전까지 반복문을 돌아야 했습니다. 이를 개선할 방법이 없을까요?

이중 연결 리스트에 대해서

위의 질문은 답은 여러가지가 존재하지만, 이중 연결 리스트가 그 중 하나입니다. 이중 연결 리스트는 단일 연결 리스트의 제한된 흐름 방향을 개선하고자 만든 자료구조입니다. 기존에는 다음 노드의 위치를 가리키는 next만을 지원했다면, 이중 연결 리스트는 이전 노드의 위치를 가리키는 prev를 지원합니다. 즉, 자기 참조 구조체는 아래 그림처럼 다음과 같이 변경됩니다.

이 그림을 다음의 코드로 변경할 수 있습니다.

typedef struct _node {
    T data;
    struct _node * prev;    /* 추가 이전 노드를 가리키는 포인터 */
    struct _node * next;
}Node;

이런 구조로 변경해서 얻는 효과는 대표적으로 꼬리 삭제 시에 일어납니다. 잠깐 연결 리스트의 꼬리 삭제하는 코드를 살펴봅시다.

T LPopBack(LinkedList * list) {
    /* 이전과 동일 */
    Node * temp = list->tail;
    T data = temp->data;
    /* 꼬리 노드 -> 꼬리 이전 노드로 변경 */
    list->tail = list->head;

    while (list->tail != temp && list->tail->next != temp) {
        list->tail = list->tail->next;
    }
    /* 이전과 동일 */
}

앞서 말했듯이 꼬리 노드의 위치를 알아도 그 이전 노드로 가기 위해서는 반복문을 돌아야 했습니다. 그러면, 잠시 이중 연결 리스트의 꼬리 삭제 코드를 살펴볼까요?

T LPopBack(DoubleLinkedList * list) {
    /* 삭제 코드 */
    Node * temp = list->tail;
    T data = temp->data;
    /* 꼬리 노드 -> 꼬리 이전 노드로 변경 */
    list->tail = list->tail->prev;
    /* 삭제 코드 */
}

코드로 보시다시피 반복분을 돌 필요 없이 prev로 접근해서 단 한번만에 자신의 이전 노드로 이동 시킬 수 있습니다. 이중 연결 리스트는 연산의 효율이 O(N)에서 O(1)로 올라간다는 엄청난 장점이 있지만, 추가/삭제 시 노드들의 포인터를 연결 리스트보다 훨씬~~~ 더 세심하게 다뤄주어야 합니다. 그만큼 난이도가 올라가지요. 코드에 대해서는 3절에서 보다 깊이 설명하도록 하겠습니다. 이제 ADT에 대해 알아보도록 하겠습니다.

2. 이중 연결 리스트 ADT

이중 연결 리스트의 ADT는 다음과 같습니다.

ADT DoubleLinkedList

characters
1. head: Node *
  - 리스트의 머리 노드를 가리킴
2. tail: Node *
  - 리스트의 꼬리 노드를 가리킴
3. size: int
  - 리스트의 크기(=원소들의 개수)
operations
1. LInit(list: DoubleLinkedList *)
  - 리스트를 생성한 후에, 초기화가 진행됩니다.
2. LCount(list: DoubleLinkedList *): int
  - 리스트의 크기를 반환합니다.
3. LIsEmpty(list: DoubleLinkedList *): bool
  - 리스트가 비었는지 여부를 반환합니다.
  - 리스트가 비어있다는 것은 size가 0과 같다는 뜻입니다.
4. LPushFront(list: DoubleLinkedList *, data: T): void
  - 리스트의 첫 번째 부분에 데이터를 저장합니다.
5. LPushBack(list: DoubleLinkedList *, data: T): void
  - 리스트 마지막 부분에 데이터를 저장합니다.
6. LPushMiddle(list: DoubleLinkedList *, index: int, data: T): void
  - 리스트 index 위치에 데이터를 저장합니다.
  - 매개변수 index는 항상 이중 연결 리스트 크기보다 작거나 같아야 합니다.
7. LPopFront(list: DoubleLinkedList *): T
  - 리스트의 첫번째 데이터가 삭제됩니다.
  - 삭제된 데이터는 반환됩니다.
8. LPopBack(list: DoubleLinkedList *): T
  - 리스트의 마지막 데이터가 삭제됩니다.
  - 삭제된 데이터는 반환합니다.
9. LPopMiddle(list: DoubleLinkedList *): T
  - 리스트 index 위치의 데이터를 삭제합니다.
  - 매개 변수 index는 리스트의 크기보다 작아야 합니다.
  - 삭제된 데이터는 반환됩니다.
10. LGet(list: DoubleLinkedList *, index: int): T
  - 리스트의 index 번째 원소를 반환합니다.
11. LDestroy(list: DoubleLinkedList *): void
  - 리스트의 모든 리소스를 해제합니다.
  - 이후 리스트를 사용하려면 다시 초기화가 진행되어야 합니다.

이중 연결 리스트의 ADT는 연결 리스트와 거의 유사합니다. 여기서는 이중 연결 리스트의 삽입/삭제 시 더 자세한 동작을 알아보기 위해서 리스트 중간에서 삽입/삭제 연산을 추가하였습니다. 이들은 각각 6번 LPushMiddle, 9번 LPopMiddle 합수들입니다. 자 이제 구현하러 가볼까요?

3. C로 구현하기

자 이제 C로 구현해봅시다. 먼저, 이중 연결 리스트 또한 연결 리스트의 일종이기 때문에 코드 흐름이 비슷합니다. 심지어 LInit, LCount, LIsEmpty, LPopFront, LGet, LDestroy 함수들은 코드 내용이 매개 변수로 바뀐것 외에는 완전하게 똑같습니다. 삽입/삭제도 거의 다르지 않죠. 여기서는 2장 연결 리스트의 코드와 설명을 빌려 써오도록 하겠습니다. 먼저 DoubleLinkedList.h를 만들고 다음의 코드를 복사해주세요.

#pragma once

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

typedef int T;

typedef struct _node {
    T data;
    struct _node * prev;
    struct _node * next;
}Node;

typedef struct _double_linked_list {
    Node * head;
    Node * tail;
    int size;
}DoubleLinkedList;

void LInit(DoubleLinkedList * list);
void LPushFront(DoubleLinkedList * list, T data);
void LPushBack(DoubleLinkedList * list, T data);
T LPopFront(DoubleLinkedList * list);
T LPopBack(DoubleLinkedList * list);
T LGet(DoubleLinkedList * list, int index);
int LCount(DoubleLinkedList * list);
void LDestroy(DoubleLinkedList * list);
bool LIsEmpty(DoubleLinkedList * list);

void LPushMiddle(DoubleLinkedList * list, int index, T data);
T LPopMiddle(DoubleLinkedList * list, int index);

이전 코드와 다른 점은, 먼저 노드의 부분 앞서 언급했듯 prev가 추가되었습니다.

typedef struct _node {
    T data;
    struct _node * prev; /* 이전 노드를 가리킬 참조 포인터 (추가)*/
    struct _node * next;
}Node;

그리고 연결 리스트를 나타내는 구조체 LinkedList가 DoubleLinkedList로 변경되었습니다. 매개 변수 역시 변경되었지요. ADT가 변경됐듯 우리가 구현할 함수도 다음과 같이 2개가 추가 되었습니다.

/* 이전 연산에 해당하는 함수들은 동일 */
void LPushMiddle(DoubleLinkedList * list, int index, T data);
T LPopMiddle(DoubleLinkedList * list, int index);

이제 구현부를 구현해볼까요? DoubleLinkedList.c를 만들고 다음을 코드를 복사합니다. 앞서 말했듯이 LInit, LCount, LIsEmpty, LPopFront, LGet, LDestroy 함수들은 내용이 완전하게 동일합니다. 따라서 위 함수들의 설명은 건너뛰겠습니다.

#include "DoubleLinkedList.h"

void LInit(DoubleLinkedList * list) {
    list->head = NULL;
    list->tail = NULL;
    list->size = 0;
}

T LPopFront(DoubleLinkedList * list) {
    assert(LIsEmpty(list) == false);

    Node * temp = list->head;
    T data = temp->data;

    list->head = list->head->next;
    free(temp);
    list->size -= 1;

    if (LIsEmpty(list) == true) {
        list->head = NULL;
        list->tail = NULL;
    }

    return data;
}

T LGet(DoubleLinkedList * list, int index) {
    assert(LCount(list) > index);
    Node * curr = list->head;

    for (int i = 0; i < index; i++) {
       curr = curr->next;
    }

    return curr->data;
}

int LCount(DoubleLinkedList * list) {
    return list->size;
}

void LDestroy(DoubleLinkedList * list) {
    if (list != NULL) {
        int size = list->size;

       for (int i = 0; i < size; i++) {
           LPopFront(list);
       }

       list = NULL;
    }
}

bool LIsEmpty(DoubleLinkedList * list) {
    return (list->size == 0);
}

T LPopBack(DoubleLinkedList * list) {
    /* 변경 사항 존재 */
}

void LPushFront(DoubleLinkedList * list, T data) {
    /* 변경 사항 존재 */
}

void LPushBack(DoubleLinkedList * list, T data) {
    /* 변경 사항 존재 */
}
//리스트 데이터 삽입(중간)
void LPushMiddle(DoubleLinkedList * list, int index, T data) {
    /* 구현 해야 함 */
}

//리스트 데이터 삭제(중간)
T LPopMiddle(DoubleLinkedList * list, int index) {
    /* 구현 해야 함 */
}

먼저 살펴볼 것은 LPopBack 함수입니다. LPopBack 함수 흐름은 연결 리스트와 동일합니다. 다만, 아까 이중 연결 리스트로 변경했을 때의 장점을 설명할 때, 반복문을 제거할 수 있다고 하였습니다. 반복하는 코드를 tail = tail->prev; 로 바꿔주면 됩니다. 따라서 LPopBack 함수는 다음과 같이 작성할 수 있습니다.

T LPopBack(DoubleLinkedList * list) {
    assert(LIsEmpty(list) == false);

    Node * temp = list->tail;
    T data = temp->data;
    list->tail = list->tail->prev; /* 변경 사항, 반복문 제거 */
    free(temp);
    list->size -= 1;

    if (LIsEmpty(list) == true) {
       list->head = NULL;
       list->tail = NULL;
    }

    return data;
}

사실, LPushFront, LPushBack도 비슷합니다. 2장 연결 리스트와 코드를 비교해보면 각 노드의 prev에 해당하는 코드들이 추가될 뿐입니다. 2장 연결 리스트의 코드와 함께 보시면, 어떤 것이 변했는지 눈에 확 알 수 있을 겁니다. 각각의 함수 코드는 다음과 같습니다.

void LPushFront(DoubleLinkedList * list, T data) {
    Node * newNode = (Node *) malloc(sizeof(Node));
    newNode->data = data;
    newNode->prev = NULL; /* 노드 초기화 시 prev 역시 NULL */
    newNode->next = NULL;

    if (LIsEmpty(list)) {
        list->tail = newNode;
    } else {
       newNode->next = list->head;
       list->head->prev = newNode; /* 머리 이전 노드가 새로운 노드를 가리키게 해야 한다. */
    }

    list->head = newNode;
    list->size += 1;
}

void LPushBack(DoubleLinkedList * list, T data) {
    Node * newNode = (Node *)malloc(sizeof(Node));
    newNode->data = data;
    newNode->prev = NULL; /* 노드 초기화 시 prev 역시 NULL */
    newNode->next = NULL;

    if (LIsEmpty(list)) {
       list->head = newNode;
    } else {
       list->tail->next = newNode;
       newNode->prev = list->tail; /* 새로운 노드의 prev는 꼬리를 가리켜야 한다. */
    }

    list->tail = newNode;
    list->size += 1;
}

이제 중간에서 삽입/삭제를 할 때를 살펴봅시다. 먼저 중간 삽입입니다.

중간 삽입 LPushMiddle

LPushMiddle 함수는 매개 변수로 이중 연결 리스트의 포인터, 삽입될 위치 index, 삽입될 data를 매개변수로 받습니다. 중간 삽입의 흐름은 다음과 같습니다.

1. index == 0 이라면, LPushFront를 호출합니다.
2. index == LCount(list)라면, LPushBack을 호출합니다.
3. LCount(list) > index 가 아니라면, 프로그램을 멈춥니다.
4. 새로운 노드를 만들고 data를 초기화합니다.
5. 리스트 머리부터 index까지 curr의 위치를 이동시킵니다.
6. 새로운 노드의 prev를 curr의 prev로, 새로운 노드의 next를 curr로 초기화합니다.
7. curr의 이전 노드의 next를 newNode로 curr의 prev를 새로운 노드로 가리키게 합니다.
8. 리스트의 크기를 1 늘립니다.

4~7을 그림으로 나타내면 다음과 같습니다.

이를 코드로 나타내면 다음과 같습니다.

void LPushMiddle(DoubleLinkedList * list, int index, T data) {
    //1. index == 0 이라면, LPushFront를 호출합니다.
    if (index == 0) {
        LPushFront(list, data);
        return;
    }
    //2. index == LCount(list)라면, LPushBack을 호출합니다.
    else if (index == LCount(list)) {
        LPushBack(list, data);
        return;
    }
    //3. LCount(list) > index 가 아니라면, 프로그램을 멈춥니다.
    assert(LCount(list) > index);
    //4. 새로운 노드를 만들고 data를 초기화합니다.
    Node * newNode = (Node *)malloc(sizeof(Node));
    newNode->data = data;
    newNode->prev = NULL;
    newNode->next = NULL;
    //5. 리스트 머리부터 index까지 curr의 위치를 이동시킵니다.
    Node * curr = list->head;

    for (int i = 0; i < index; i++) {
       curr = curr->next;
    }
    //6. 새로운 노드의 prev를 curr의 prev로, 새로운 노드의 next를 curr로 초기화합니다.
    newNode->prev = curr->prev;
    newNode->next = curr;
    //7. curr의 이전 노드의 next를 newNode로 curr의 prev를 새로운 노드로 가리키게 합니다.
    curr->prev->next = newNode;
    curr->prev = newNode;
    //8. 리스트의 크기를 1 늘립니다.
    list->size += 1;
}

중간 삭제 LPopMiddle

LPopMiddle은 매개변수로 이중 연결 리스트의 포인터와 삭제될 위치 index를 받습니다. 또한 삭제된 원소를 반환합니다. 이를 코드 흐름으로 살펴보면 다음과 같습니다.

index == 0이라면, LPopFront 함수를 호출합니다.
index == LCount(list) - 1 이라면, LPopBack 함수를 호출합니다.
LCount(list) > index가 아니라면, 프로그램을 멈춥니다.
현재 위치 curr을 index만큼 이동합니다.
현재 위치의 data를 저장합니다.
curr의 이전 노드의 next를 curr의 다음 노드로 변경합니다.
curr의 다음 노드의 prev를 curr의 이전 노드로 변경합니다.
노드를 삭제합니다.(이때, curr->prev, curr->next는 NULL)
데이터를 반환합니다.

이를 그림으로 나타내면 다음과 같습니다.

이를 코드로 나타내면 다음과 같습니다.

T LPopMiddle(DoubleLinkedList * list, int index) {
    //1. index == 0이라면, LPopFront 함수를 호출합니다.
    if (index == 0)
       return  LPopFront(list);
    //2. index == LCount(list) - 1 이라면, LPopBack 함수를 호출합니다.
    else if (index == LCount(list)-1)
       return LPopBack(list);
    //3. LCount(list) > index가 아니라면, 프로그램을 멈춥니다.
    assert(LCount(list) > index);
    //4. 현재 위치 curr을 index만큼 이동합니다.
    Node * curr = list->head;

    for (int i = 0; i < index; i++) {
       curr = curr->next;
    }
    //5. 현재 위치의 data를 저장합니다.
    T data = curr->data;
    //6. curr의 이전 노드의 next를 curr의 다음 노드로 변경합니다.
    curr->prev->next = curr->next;
    //7. curr의 다음 노드의 prev를 curr의 이전 노드로 변경합니다.
    curr->next->prev = curr->prev;
    //8. 노드를 삭제합니다.(이때, curr->prev, curr->next는 NULL)
    free(curr);
    list->size -= 1;

    return data;
}

이제 C로 모두 구현해 보았으니 C++로 한 번 바꿔보도록 하겠습니다.

4. C++로 바꿔보기

C++로 바꾸는 요령은 똑같습니다. 따라서 코드만 기술합니다. DoubleLinkedList.hpp 는 다음과 같습니다.

#pragma once

#include <cassert>

template<class T> class DoubleLinkedList {
private:
	struct Node
	{
		T data;
		Node * prev;
		Node * next;
	};
	Node * head;
	Node * tail;
	int size;
public:
	DoubleLinkedList() : head(nullptr), tail(nullptr), size(0) {}
	
	~DoubleLinkedList() {
		int size = this->size;
		for (int i = 0; i < size; i++) {
			this->popBack();
		}
	}
	
	bool isEmpty() {
		return (this->size == 0);
	}

	int getSize() {
		return this->size;
	}

	void pushFront(T data) {
		Node * newNode = new Node{ data, nullptr, nullptr };

		if (this->isEmpty()) {
			this->tail = newNode;
		}
		else {
			newNode->next = this->head;
			this->head->prev = newNode;
		}

		this->head = newNode;
		this->size += 1;
	}

	void pushBack(T data) {
		Node * newNode = new Node{ data, nullptr, nullptr };

		if (this->isEmpty()) {
			this->head = newNode;
		}
		else {
			this->tail->next = newNode;
			newNode->prev = this->tail;
		}

		this->tail = newNode;
		this->size += 1;
	}

	void pushMiddle(int index, T data) {
		if (index == 0) {
			this->pushFront(data);
			return;
		}
		else if (index == this->getSize()) {
			this->pushBack(data);
			return;
		}
		assert(this->getSize() > index);

		Node * newNode = new Node{ data, nullptr, nullptr };
		Node * curr = this->head;

		for (int i = 0; i < index; i++) {
			curr = curr->next;
		}

		newNode->next = curr;
		newNode->prev = curr->prev;
		curr->prev->next = newNode;
		curr->prev = newNode;

		this->size += 1;
	}

	T popFront() {
		assert(this->isEmpty() == false);

		Node * temp = this->head;
		T data = temp->data;

		this->head = this->head->next;
		delete temp;
		this->size -= 1;

		if (this->isEmpty() == true) {
			this->head = nullptr;
			this->tail = nullptr;
		}

		return data;
	}

	T popBack() {
		assert(this->isEmpty() == false);	
		
		Node * temp = this->tail;
		T data = temp->data;
		this->tail = this->tail->prev;
		
		delete temp;
		this->size -= 1;
		
		if (this->isEmpty() == true) {
			this->head = nullptr;
			this->tail = nullptr;
		}

		return data;
	}

	T popMiddle(int index) {

		if (index == 0) {
			return this->popFront();
		}
		else if (index == this->size-1) {
			return this->popBack();
		}

		assert(this->size > index);
	
		Node * curr = this->head;
		
		for (int i = 0; i < index; i++) {
			curr = curr->next;
		}

		curr->prev->next = curr->next;
		curr->next->prev = curr->prev;

		T data = curr->data;
		this->size -= 1;
		delete curr;

		return data;
	}

	T get(int index) {
		assert(this->getSize() > index);	
		Node * curr = this->head;

		for (int i = 0; i < index; i++) {
			curr = curr->next;
		}

		return curr->data;
	}
};

5. 결론

이중 연결 리스트 정리

이렇게 해서 연결 리스트보다 더 우수한 리스트, 이중 연결 리스트의 개념, 구현에 대해서 알아보았습니다. 연결 리스트와 다른 점을 꼽자면, 자기 참조 구조체의 형태, prev가 추가된 것이지요. 구초체가 변형됨으로써 얻은 효과는 불필요하게, 반복문을 돌던 꼬리 삭제를 선형 시간으로 연산 효율을 올릴 수 있었다는 것입니다. 그리고 중간 삽입/삭제에 대해 동작을 정의하고 구현해봄으로써 이중 연결 리스트에서 포인터를 어떻게 다루는지도 알 수 있었습니다. 이중 연결리스트에 대해서 감이 좀 잡히시나요? ㅎㅎ 자료구조/알고리즘 파트는 꾸준히, 공부하고 써서 자신의 몸에 체득시키는 일종의 기술이라고 생각하시면 좋습니다. 생각날 때 한 번씩 반복해서 공부하는 것이지요. 이쯤에서 이중 연결 리스트에 대한 설명을 마치도록 하겠습니다.

다음 장에서는 이 중에서 선형 자료 구조의 하나인 스택에 대해 알아보도록 하겠습니다.

저작자표시

'레거시 > 레거시-자료구조' 카테고리의 다른 글

목차 (0)	2019.08.30
[자료구조/알고리즘]05. 큐 (0)	2019.02.02
[자료구조/알고리즘]04. 스택 Stack (0)	2019.01.29
[자료구조/알고리즘] 02. 연결 리스트 Linked List (0)	2019.01.19
[자료구조/알고리즘] 01. 추상 데이터 타입 ADT (0)	2019.01.19

ABOUT ME

구르미의 개발 이야기 구르미의 개발 이야기

CH 03 이중 연결 리스트(Double Linked List)

목표

목차

1. 이중 연결 리스트란 무엇인가?

연결 리스트의 한계

이중 연결 리스트에 대해서

2. 이중 연결 리스트 ADT

3. C로 구현하기

4. C++로 바꿔보기

5. 결론

이중 연결 리스트 정리

'레거시 > 레거시-자료구조' 카테고리의 다른 글

티스토리툴바

ABOUT ME

CH 03 이중 연결 리스트(Double Linked List)

목표

목차

1. 이중 연결 리스트란 무엇인가?

연결 리스트의 한계

이중 연결 리스트에 대해서

2. 이중 연결 리스트 ADT

3. C로 구현하기

4. C++로 바꿔보기

5. 결론

이중 연결 리스트 정리

'레거시 > 레거시-자료구조' 카테고리의 다른 글

관련글 관련글 더보기

티스토리툴바