연결 자료구조 - 이중 연결 리스트(DoublyLinkedList)

  이중 연결 리스트 

이중 연결 리스트는 이전 노드의 주소와 다음 노드의 주소를 모두 관리한다.

 

- 삽입(Insert) 연산

기존 노드의 다음을 삽입 노드가 가리키고 기존 노드의 다음은 삽입 노드를 가리키도록 하고 다음 노드의 이전을 삽입 노드가 가리키고 다음 노드의 이전은 삽입 노드를 가리키도록 한다.

 

* 원본 데이터

 

리스트 끝에 노드를 삽입하는 경우 리스트의 마지막 노드의 다음이 삽입 노드를 가리키고 삽입 노드의 이전이 마지막 노드를 가리키도록 만들어준다.

※ 리스트 앞에 노드를 삽입하는 경우 삽입 노드의 다음이 처음 노드를 가리키고 처음 노드의 이전이 삽입 노드를 가리키도록 만들어주면 된다.

 

리스트 중간에 노드를 삽입하는 경우 리스트 앞에 노드를 삽입할 때의 작업과 리스트 뒤에 노드를 삽입할 때의 작업을 모두 진행해야 한다.

 

- 삭제(Delete) 연산

삭제할 노드의 이전을 다음 노드의 이전이 가리키도록 하고 삭제할 노드의 다음을 이전 노드의 다음이 가리키도록 한다.

 

리스트 끝에서 노드를 삭제하는 경우 마지막 노드가 아무것도 가리키지 않도록 만들고 이전 노드의 다음이 아무것도 가리키지 않도록 만들어준다.

※ 리스트 앞에서 노드를 삭제하는 경우 처음 노드가 아무것도 가리키지 않도록 만들고 다음 노드의 이전이 아무것도 가리키지 않도록 만들어주면 된다.

 

리스트 중간에서 노드를 삭제하는 경우 리스트 앞에서 노드를 삭제할 때의 작업과 리스트 뒤에서 노드를 삭제할 때의 작업을 모두 진행해야 한다.

 

  이중 연결 리스트 구현 

단일 연결 리스트의 이해를 기반으로 C#의 LinkedList<T>를 간략화하여 int만 저장할 수 있는 DoublyLinkedList를 만든다.

 

구현이 필요한 메서드 및 속성은 다음과 같다.

 

• 생성자
  • DoublyLinkedList() 비어있는 인스턴스 생성
  • DoublyLinkedList(DoublyLinkedList&) 다른 DoublyLinkedList 데이터로 인스턴스 생성
• 속성 
  
  • Count 사용되고 있는 노드의 수
  • First 리스트의 처음 노드
  • Last 리스트의 마지막 노드
• 메서드 
  • AddFirst(data) 시작 위치에 데이터를 포함한 노드 생성 후 삽입
  • AddFirst(node) 지정된 노드 삽입
  • AddLast(data) 시작 위치에 데이터를 포함한 노드 생성 후 삽입
  • AddLast(node) 지정된 노드 삽입
  • Insert(int, data) 지정된 위치에 데이터를 포함한 노드 생성 후 삽입
  • Insert(int, node) 지정된 위치에 지정된 노드 삽입
  • RemoveFirst(data) 가장 처음 일치한 데이터를 포함한 노드 삭제
  • RemoveLast(data) 가장 마지막 일치한 데이터를 포함한 노드 삭제
  • Remove(node) 지정된 노드와 동일한 노드 삭제
  • Clear() 모든 노드 삭제
  • Contains(data) 데이터를 포함한 노드의 존재 여부 확인
  • Contains(node) 지정된 노드의 존재 여부 확인
  • Find(data) 가장 처음 일치한 데이터를 포함하는 노드 반환
  • FindLast(data) 가장 마지막 일치한 데이터를 포함하는 노드 반환

 

DoublyLinkedList.h

#pragma once
#include <xutility>
#include <iostream>

struct DoublyLinkedListNode
{
	DoublyLinkedListNode() {}
	DoublyLinkedListNode(int value) { m_data = value; }

	int m_data{ 0 };
	DoublyLinkedListNode* m_prev{ nullptr };
	DoublyLinkedListNode* m_next{ nullptr };
};

class DoublyLinkedList
{
public:
#pragma region 생성자
	DoublyLinkedList();
	DoublyLinkedList(const DoublyLinkedList& other);
	~DoublyLinkedList();
#pragma endregion

#pragma region 속성
	const int Count() { return m_count; }
	DoublyLinkedListNode& First() { return *m_head; }
	DoublyLinkedListNode& Last() { return *m_tail; }
#pragma endregion

#pragma region 메서드
	void AddFirst(int value);
	void AddFirst(DoublyLinkedListNode* node);
	void AddLast(int value);
	void AddLast(DoublyLinkedListNode* node);
	void Insert(int index, int value);
	void Insert(int index, DoublyLinkedListNode* node);

	bool RemoveFirst(int value);
	bool RemoveLast(int value);
	void Remove(const DoublyLinkedListNode* node);
	void Clear();

	bool Contains(int value);
	bool Contains(const DoublyLinkedListNode* node);
	DoublyLinkedListNode* Find(int value);
	DoublyLinkedListNode* FindLast(int value);
#pragma endregion

private:
#pragma region Class Util
	DoublyLinkedListNode* PopNode(int value);
	void PushNode(DoublyLinkedListNode* node);
#pragma endregion
	
private:
#pragma region 변수
	size_t m_count;
	DoublyLinkedListNode* m_head;
	DoublyLinkedListNode* m_tail;
	DoublyLinkedListNode* m_free;
#pragma endregion
};

 

생성자/소멸자 구현

기본 생성자와 DoublyLinkedList를 인자로 받는 복사 생성자를 구현한다.

 

DoublyLinkedList.cpp

/// <summary>
/// 비어있는 DoublyLinkedList를 생성한다.
/// </summary>
DoublyLinkedList::DoublyLinkedList()
	: m_count(0), m_head(nullptr), m_tail(nullptr), m_free(nullptr)
{
}

/// <summary>
/// 다른 SinglyLinkedList가 가지고 있는 노드를 복사해 SinglyLinkedList를 생성한다.
/// </summary>
/// <param name="other">기준이 될 DoublyLinkedList</param>
DoublyLinkedList::DoublyLinkedList(const DoublyLinkedList& other)
	: m_count(other.m_count), m_free(nullptr)
{
	DoublyLinkedListNode* curNode{ other.m_head };

	if (curNode != nullptr)
	{
		m_head = m_tail = PopNode(curNode->m_data);
		curNode = curNode->m_next;
	}

	while (curNode != nullptr)
	{
		DoublyLinkedListNode* newNode{ PopNode(curNode->m_data) };
		m_tail->m_next = newNode;
		newNode->m_prev = m_tail;
		m_tail = newNode;
		curNode = curNode->m_next;
	}
}

/// <summary>
/// 메모리 누수를 막기 위해 동적 생성한 노드들을 제거한다.
/// </summary>
DoublyLinkedList::~DoublyLinkedList()
{
	while (m_head != nullptr)
	{
		DoublyLinkedListNode* curNode{ m_head };
		m_head = m_head->m_next;
		delete curNode;
	}

	while (m_free != nullptr)
	{
		DoublyLinkedListNode* curNode{ m_free };
		m_free = m_free->m_next;
		delete curNode;
	}
}

 

자유 공간 리스트 구현

노드의 메모리 할당과 해제를 최소화하기 위한 자유 공간 리스트를 구현한다.

 

SinglyLinkedList.cpp

/// <summary>
/// 자유 공간 리스트에서 노드를 가져오거나 새로 생성한다.
/// </summary>
/// <param name="value">노드 생성시 초기값</param>
/// <returns>새 노드</returns>
DoublyLinkedListNode* DoublyLinkedList::PopNode(int value)
{
	DoublyLinkedListNode* newNode{ nullptr };
	if (m_free == nullptr)
	{
		newNode = new DoublyLinkedListNode(value);
	}
	else
	{
		newNode = m_free;
		m_free = m_free->m_next;

		newNode->m_data = value;
		newNode->m_next = nullptr;
	}

	return newNode;
}

/// <summary>
/// 자유 공간 리스트에 제거된 노드를 저장한다.
/// </summary>
/// <param name="node">제거된 노드</param>
void DoublyLinkedList::PushNode(DoublyLinkedListNode* node)
{
	node->m_prev = nullptr;
	node->m_next = m_free;
	m_free = node;
}

 

데이터 삽입 메서드 구현

데이터 삽입 연산에 필요한 메서드들을 구현한다.

 

DoublyLinkedList.cpp

/// <summary>
/// SinglyLinkedList의 시작 위치에 지정한 값이 포함된 새 노드를 추가한다.
/// </summary>
/// <param name="value">추가할 값</param>
void DoublyLinkedList::AddFirst(int value)
{
	DoublyLinkedListNode* newNode{ PopNode(value) };
	AddFirst(newNode);
}

/// <summary>
/// SinglyLinkedList의 시작 위치에 지정한 노드를 추가한다.
/// </summary>
/// <param name="node">추가할 새 노드</param>
void DoublyLinkedList::AddFirst(DoublyLinkedListNode* node)
{
	if (node == nullptr || node->m_prev != nullptr || node->m_next != nullptr)
	{
		throw std::invalid_argument("node");
	}

	node->m_next = m_head;
	if (m_head != nullptr)
	{
		m_head->m_prev = node;
		m_head = node;
	}
	else
	{
		m_head = m_tail = node;
	}

	m_count++;
}

/// <summary>
/// SinglyLinkedList의 끝 위치에 지정한 값이 포함된 새 노드를 추가한다.
/// </summary>
/// <param name="value">추가할 값</param>
void DoublyLinkedList::AddLast(int value)
{
	DoublyLinkedListNode* newNode{ PopNode(value) };
	AddLast(newNode);
}

/// <summary>
/// SinglyLinkedList의 끝 위치에 지정한 노드를 추가한다.
/// </summary>
/// <param name="node">추가할 새 노드</param>
void DoublyLinkedList::AddLast(DoublyLinkedListNode* node)
{
	if (node == nullptr || node->m_prev != nullptr || node->m_next != nullptr)
	{
		throw std::invalid_argument("node");
	}

	node->m_prev = m_tail;
	if (m_tail != nullptr)
	{
		m_tail->m_next = node;
		m_tail = node;
	}
	else
	{
		m_head = m_tail = node;
	}

	m_count++;
}

/// <summary>
/// DoublyLinkedList의 지정한 인덱스에 해당하는 위치에 지정한 값이 포함된 새 노드를 추가한다.
/// </summary>
/// <param name="index">값을 추가할 인덱스</param>
/// <param name="value">추가할 값</param>
void DoublyLinkedList::Insert(int index, int value)
{
	DoublyLinkedListNode* newNode{ PopNode(value) };
	Insert(index, newNode);
}

/// <summary>
/// DoublyLinkedList의 지정한 인덱스에 해당하는 위치에 지정된 노드를 추가한다.
/// </summary>
/// <param name="index">새 노드를 추가할 인덱스</param>
/// <param name="node">추가할 새 노드</param>
void DoublyLinkedList::Insert(size_t index, DoublyLinkedListNode* node)
{
	if (index > m_count)
	{
		throw std::out_of_range("index");
	}

	if (node == nullptr || node->m_next != nullptr)
	{
		throw std::invalid_argument("node");
	}

	DoublyLinkedListNode* curNode{ m_head };
	DoublyLinkedListNode* prevNode{ curNode != nullptr ? curNode->m_prev : nullptr };
	for (int i = 0; i < index; i++)
	{
		prevNode = curNode;
		curNode = curNode != nullptr ? curNode->m_next : nullptr;
	}

	node->m_prev = prevNode;
	if (prevNode != nullptr)
	{
		prevNode->m_next = node;
	}
	node->m_next = curNode;
	if (curNode != nullptr)
	{
		curNode->m_prev = node;
	}

	if (node->m_prev == nullptr)
	{
		m_head = node;
	}
	if (node->m_next == nullptr)
	{
		m_tail = node;
	}

	m_count++;
}

 

데이터 삭제 메서드 구현

데이터 삭제 연산에 필요한 메서드들을 구현한다.

 

DoublyLinkedList.cpp

/// <summary>
/// DoublyLinkedList에서 가장 처음 일치한 지정된 값을 포함한 노드를 제거한다.
/// </summary>
/// <param name="value">제거할 값</param>
bool DoublyLinkedList::RemoveFirst(int value)
{
	DoublyLinkedListNode* curNode{ m_head };
	while (curNode != nullptr)
	{
		if (curNode->m_data == value)
		{
			break;
		}
		curNode = curNode->m_next;
	}

	if (curNode == nullptr)
	{
		return false;
	}

	Remove(curNode);

	return true;
}

/// <summary>
/// DoublyLinkedList에서 가장 처음 일치한 지정된 값을 포함한 노드를 제거한다.
/// </summary>
/// <param name="value">제거할 값</param>
bool DoublyLinkedList::RemoveLast(int value)
{
	DoublyLinkedListNode* curNode{ m_tail };
	while (curNode != nullptr)
	{
		if (curNode->m_data == value)
		{
			break;
		}
		curNode = curNode->m_prev;
	}

	if (curNode == nullptr)
	{
		return false;
	}

	Remove(curNode);

	return true;
}

/// <summary>
/// DoublyLinkedList에서 지정된 노드를 제거한다.
/// </summary>
/// <param name="node">제거할 노드</param>
void DoublyLinkedList::Remove(const DoublyLinkedListNode* node)
{
	if (node == nullptr)
	{
		throw std::invalid_argument("node");
	}

	DoublyLinkedListNode* curNode{ m_head };
	while (curNode != nullptr)
	{
		if (curNode == node)
		{
			break;
		}
		curNode = curNode->m_next;
	}

	if (curNode == nullptr)
	{
		throw std::out_of_range("node");
	}

	DoublyLinkedListNode* prevNode{ curNode->m_prev };
	DoublyLinkedListNode* nextNode{ curNode->m_next };
	if (prevNode != nullptr)
	{
		prevNode->m_next = nextNode;
	}
	else
	{
		m_head = nextNode;
	}

	if (nextNode != nullptr)
	{
		nextNode->m_prev = prevNode;
	}
	else
	{
		m_tail = prevNode;
	}

	PushNode(curNode);

	m_count--;
}

/// <summary>
/// DoublyLinkedList의 모든 노드를 제거한다.
/// </summary>
void DoublyLinkedList::Clear()
{
	while (m_head != nullptr)
	{
		DoublyLinkedListNode* curNode{ m_head };
		m_head = m_head->m_next;
		PushNode(curNode);
	}
	m_count = 0;
}

 

기능 메서드 구현

자료구조를 효율적으로 사용하기 위한 기능 메서드를 구현한다.

 

DoublyLinkedList.cpp

/// <summary>
/// 지정한 값을 포함한 노드가 존재하는지 확인한다.
/// </summary>
/// <param name="value">찾을 값</param>
/// <returns>값의 존재 여부</returns>
bool DoublyLinkedList::Contains(int value)
{
	DoublyLinkedListNode* curNode{ m_head };
	while (curNode != nullptr)
	{
		if (curNode->m_data == value)
		{
			return true;
		}
		curNode = curNode->m_next;
	}
	return false;
}

/// <summary>
/// 지정한 노드가 DoublyLinkedList에 포함되는지 확인한다.
/// </summary>
/// <param name="node">찾을 노드</param>
/// <returns>노드의 포함 여부</returns>
bool DoublyLinkedList::Contains(const DoublyLinkedListNode* node)
{
	DoublyLinkedListNode* curNode{ m_head };
	while (curNode != nullptr)
	{
		if (curNode == node)
		{
			return true;
		}
		curNode = curNode->m_next;
	}
	return false;
}

/// <summary>
/// 지정한 값을 포함하는 가장 처음 일치하는 노드를 반환한다.
/// </summary>
/// <param name="value">찾을 값</param>
/// <returns>지정한 값을 포함하는 노드(없는 경우: nullptr)</returns>
DoublyLinkedListNode* DoublyLinkedList::Find(int value)
{
	DoublyLinkedListNode* curNode{ m_head };
	while (curNode != nullptr)
	{
		if (curNode->m_data == value)
		{
			return curNode;
		}
		curNode = curNode->m_next;
	}
	return nullptr;
}

/// <summary>
/// 지정한 값을 포함하는 가장 마지막 일치하는 노드를 반환한다.
/// </summary>
/// <param name="value">찾을 값</param>
/// <returns>지정한 값을 포함하는 노드(없는 경우: nullptr)</returns>
DoublyLinkedListNode* DoublyLinkedList::FindLast(int value)
{
	DoublyLinkedListNode* curNode{ m_tail };
	while (curNode != nullptr)
	{
		if (curNode->m_data == value)
		{
			return curNode;
		}
		curNode = curNode->m_prev;
	}
	return nullptr;
}

 

참고문헌

Microsoft MSDN.LinkedList<T> 클래스 (System.Collections.Generic)