연결 자료구조 - 단일 연결 리스트(SinglyLinkedList)

  연결 자료구조 

메모리에 연속적으로 저장되어 연결되는 것이 아니라 각 원소가 가진 포인터를 통해 다음 원소를 가리키는 것으로 연결된다. 순차 자료구조의 삽입과 삭제에 추가 연산이 필요하고 메모리 사용에 비효율적이라는 문제를 개선한 방법이다.

 

노드

자료구조에서는 연결 자료구조의 표현을 위한 데이터와 다음 원소를 가리키는 포인터의 묶음으로 이루어진 구조를 노드라고 한다. 데이터를 저장하는 부분을 데이터 필드(Data Field), 포인터 부분을 링크 필드(Link Field)라고 한다.

다음의 순차 자료구조로 표현된 데이터를 연결 자료구조로 표현하면 다음과 같이 표현된다.

- 순차 자료구조 표현

인덱스	0	1	2	3
데이터	10	20	30	40

 

- 연결 자료구조 표현

 

※ 연결 자료구조는 인덱스를 저장하는 것이 아닌 주소를 저장한다.

 

연결 자료구조의 종류

• 단일 연결 리스트 노드가 하나의 링크 필드로 연결되어 다음 노드를 가리키는 구조

  

• 이중 연결 리스트 노드가 두 개의 링크 필드로 연결되어 다음 노드와 이전 노드를 가리키는 구조

  

• 원형 연결 리스트 마지막 노드가 첫 번째 노드를 가리키는 순환식 구조

  

 

※ 원형 연결 리스트는 단일 연결 리스트와 이중 연결 리스트에서 모두 사용할 수 있다.

 

  단일 연결 리스트 

단일 연결 리스트는 다음 노드의 주소만을 관리하기 때문에 삽입과 삭제에 이전 노드가 필요하다.

 

- 삽입(Insert) 연산

기존 노드가 가리키는 삽입 노드를 가리키도록 하고 기존 노드가 삽입 노드를 가리키도록 한다.

 

* 원본 데이터

 

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

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

 

리스트 중간에 노드를 삽입하는 경우 삽입할 위치의 이전 노드가 가리키던 노드를 삽입 노드가 가리키도록 만들고 이전 노드가 삽입 노드를 가리키도록 만들어준다.

 

- 삭제(Delete) 연산

삭제할 노드가 가리키는 노드를 삭제할 노드의 이전 노드가 가리키도록 한다.

 

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

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

 

리스트 중간에서 노드를 삭제하는 경우 삭제할 노드의 이전 노드가 삭제할 노드가 가리키던 노드를 가리키도록 만들어준다.

 

※ 삭제할 노드가 가리키는 노드는 변경하지 않는다.

 

  단일 연결 리스트 구현 

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

 

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

 

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

 

SinglyLinkedList.h

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

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

	int m_data{ 0 };
	SinglyLinkedListNode* m_next{ nullptr };
};

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

#pragma region 속성
	const int Count() { return m_count; }
	SinglyLinkedListNode& Front() { return *m_head; }
#pragma endregion

#pragma region 메서드
	void Add(int value);
	void Add(SinglyLinkedListNode* node);
	void Insert(int index, int value);
	void Insert(int index, SinglyLinkedListNode* node);

	bool Remove(int value);
	void Remove(const SinglyLinkedListNode* node);
	void Clear();

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

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

 

생성자/소멸자 구현

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

 

SinglyLinkedList.cpp

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

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

	m_head = prevNode;
	curNode = curNode->m_next;

	while (curNode != nullptr)
	{
		SinglyLinkedListNode* newNode{ PopNode(curNode->m_data) };
		prevNode->m_next = newNode;
		prevNode = newNode;
		curNode = curNode->m_next;
	}
}

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

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

 

자유 공간 리스트 구현

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

 

SinglyLinkedList.cpp

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

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

 

데이터 삽입 메서드 구현

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

 

SinglyLinkedList.cpp

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

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

	node->m_next = m_head;
	m_head = node;

	m_count++;
}

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

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

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

	if (index > m_count)
	{
		index = m_count;
	}

	SinglyLinkedListNode* prevNode{ nullptr };
	SinglyLinkedListNode* curNode{ m_head };
	while (index--)
	{
		prevNode = curNode;
		curNode = curNode->m_next;
	}

	node->m_next = curNode;

	if (prevNode == nullptr)
	{
		m_head = node;
	}
	else
	{
		prevNode->m_next = node;
	}

	m_count++;
}

 

데이터 삭제 메서드 구현

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

 

SinglyLinkedList.cpp

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

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

	if (prevNode == nullptr)
	{
		m_head = curNode->m_next;
	}
	else
	{
		prevNode->m_next = curNode->m_next;
	}
	PushNode(curNode);

	m_count--;
	return true;
}

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

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

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

	if (prevNode == nullptr)
	{
		m_head = curNode->m_next;
	}
	else
	{
		prevNode->m_next = curNode->m_next;
	}
	PushNode(curNode);

	m_count--;
}

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

 

기능 메서드 구현

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

 

SinglyLinkedList.cpp

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

/// <summary>
/// 지정한 노드가 SinglyLinkedList에 포함되는지 확인한다.
/// </summary>
/// <param name="node">찾을 노드</param>
/// <returns>노드의 포함 여부</returns>
bool SinglyLinkedList::Contains(const SinglyLinkedListNode* node)
{
	SinglyLinkedListNode* 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>
SinglyLinkedListNode* SinglyLinkedList::Find(int value)
{
	SinglyLinkedListNode* curNode{ m_head };
	while (curNode != nullptr)
	{
		if (curNode->m_data == value)
		{
			break;
		}
		curNode = curNode->m_next;
	}
	return curNode;
}

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

 

참고문헌

위키백과.연결 리스트

나무위키.연결 리스트

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

Microsotf MSDN.forward_list 클래스