자료구조...29

이중 원형 연결 리스트 구현

DoublyLinkedList를 변형하여 이중 원형 연결 리스트를 구현한다.

 

DoublyCircularLinkedList.h

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

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

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

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

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

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

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

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

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

 

- 생성자, 소멸자 구현

 

DoublyCircularLinkedList.cpp

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

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

	DoublyCircularLinkedListNode* curNode{ other.m_head };

	m_head = m_tail = PopNode(curNode->m_data);
	curNode = curNode->m_next;

	while (curNode->m_prev != other.m_tail)
	{
		DoublyCircularLinkedListNode* newNode{ PopNode(curNode->m_data) };
		m_tail->m_next = newNode;
		newNode->m_prev = m_tail;
		m_tail = newNode;
		curNode = curNode->m_next;
	}

	m_head->m_prev = m_tail;
	m_tail->m_next = m_head;
}

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

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