자료구조...25

단일 원형 연결 리스트 구현

SinglyLinkedList를 변형하여 단일 원형 연결 리스트를 구현한다.

 

SinglyCircularLinkedList.h

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

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

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

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

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

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

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

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

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

 

- 생성자, 소멸자 구현

 

SinglyCircularLinkedList.cpp

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

	SinglyCircularLinkedListNode* curNode{ other.m_head };
	SinglyCircularLinkedListNode* prevNode{ PopNode(curNode->m_data) };

	m_head = prevNode;
	curNode = curNode->m_next;

	while (curNode->m_next != other.m_head)
	{
		SinglyCircularLinkedListNode* newNode{ PopNode(curNode->m_data) };
		prevNode->m_next = newNode;
		prevNode = newNode;
		curNode = curNode->m_next;
	}
}

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

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