c++ Doubly Linked List

스마트 포인터를 이용한 Doubly Linked List구현

#pragma once

#include <memory>

namespace lab10
{
	template<typename T>
	class Node
	{
	public:
		Node(std::unique_ptr<T> data);
		Node(std::unique_ptr<T> data, std::shared_ptr<Node<T>> prev);
		std::unique_ptr<T> Data;
		std::shared_ptr<Node<T>> Next;
		std::weak_ptr<Node<T>> Previous;

	};
	
	template<typename T>Node<T>::Node(std::unique_ptr<T> data)
		: Data(std::move(data))
	{
	}

	template<typename T>Node<T>::Node(std::unique_ptr<T> data, std::shared_ptr<Node<T>> prev)
		: Data(std::move(data))
		, Previous(prev)
	{
	}
}

#pragma once

#include <memory>
//#include<iostream>

namespace lab10
{
	template<typename T>
	class Node;

	template<typename T>
	class DoublyLinkedList
	{
	public:
		DoublyLinkedList();
		void Insert(std::unique_ptr<T> data);
		void Insert(std::unique_ptr<T> data, unsigned int index);
		bool Delete(const T& data);
		bool Search(const T& data) const;

		std::shared_ptr<Node<T>> operator[](unsigned int index) const;
		unsigned int GetLength() const;
	private:
		void insert(std::shared_ptr<Node<T>> node, std::unique_ptr<T> data);
		std::shared_ptr<Node<T>> getNodeByData(const T& data) const;
		std::shared_ptr<Node<T>> getNodeByIndex(unsigned int index) const;
		
		std::shared_ptr<Node<T>> mFirst;
		size_t mSize;
	};

	template<typename T>DoublyLinkedList<T>::DoublyLinkedList()
		: mFirst(nullptr)
		, mSize(0)
	{
	}

	template<typename T>
	void DoublyLinkedList<T>::Insert(std::unique_ptr<T> data)
	{
		Insert(std::move(data), mSize);
	}

	template<typename T>
	void DoublyLinkedList<T>::Insert(std::unique_ptr<T> data, unsigned int index)
	{
		if (mFirst == nullptr)
		{
			mFirst = std::make_shared<Node<T>>(std::move(data));
			mSize++;
			return;
		}

		std::shared_ptr<Node<T>> node = getNodeByIndex(index);
		if (node == nullptr)
		{
			// 해당 index에 node가 없으면 맨뒤에 추가한다.
			insert(getNodeByIndex(mSize - 1), std::move(data));
		}
		else
		{
			// 해당 index에 node가 있으면 node의 previous node 뒤에 붙여준다.
			insert(node->Previous.lock(), std::move(data));
		}
	}

	template<typename T>
	void DoublyLinkedList<T>::insert(std::shared_ptr<Node<T>> node, std::unique_ptr<T> data)
	{
		std::shared_ptr<Node<T>> newNode = std::make_shared<Node<T>>(std::move(data), node);
		mSize++;
		if (node == nullptr)
		{
			newNode->Next = mFirst;
			mFirst->Previous = newNode;
			mFirst = newNode;
			return;
		}

		if (node->Next != nullptr)
		{
			newNode->Next = node->Next;
			node->Next->Previous = newNode;
		}
		node->Next = newNode;
		newNode->Previous = node;
	}

	template<typename T>
	bool DoublyLinkedList<T>::Delete(const T& data)
	{
		std::shared_ptr<Node<T>> node = getNodeByData(data);
		if (node == nullptr)
			return false;

		std::shared_ptr<Node<T>> prevNode = node->Previous.lock();
		if (prevNode == nullptr)
		{
			node->Next->Previous.lock() = nullptr;
			mFirst = node->Next;
		}
		else
		{
			prevNode->Next = node->Next;

			if (node->Next != nullptr)
			{
				node->Next->Previous = node->Previous;
			}
		}
		--mSize;

		return true;
	}

	template<typename T>
	bool DoublyLinkedList<T>::Search(const T& data) const
	{
		if (getNodeByData(data) == nullptr)
			return false;

		return true;
	}
	
	template<typename T>
	std::shared_ptr<Node<T>> DoublyLinkedList<T>::getNodeByData(const T& data) const
	{
		if (mFirst == nullptr)
			return nullptr;

		std::shared_ptr<Node<T>> node = mFirst;
		while (node != nullptr)
		{
			if (*node->Data == data)
			{
				break;
			}

			node = node->Next;
		}
		return node;
	}

	template<typename T>
	std::shared_ptr<Node<T>> DoublyLinkedList<T>::getNodeByIndex(unsigned int index) const
	{
		if (index >= mSize)
			return nullptr;

		unsigned int i = 0;
		std::shared_ptr<Node<T>> node = mFirst;
		while (node != nullptr)
		{
			if (i == index)
			{
				break;
			}

			node = node->Next;
			i++;
		}
		return node;
	}

	template<typename T>
	std::shared_ptr<Node<T>> DoublyLinkedList<T>::operator[](unsigned int index) const
	{
		return getNodeByIndex(index);
	}

	template<typename T>
	unsigned int DoublyLinkedList<T>::GetLength() const
	{
		return mSize;
	}
}