[자료구조]연결리스트-양방향 DLL(DoublyLinkedList) / 템플릿 /C++

 

#include <iostream>
using namespace std;

template<typename T>
class Node {
public:
	Node() 
		: mdata(static_cast<T>(0))
		, mPre(nullptr)
		, mNext(nullptr)
	{};
	Node(T _data)
		: mdata(_data)
		, mPre(nullptr)
		, mNext(nullptr)
	{}
	~Node() 
	{
		delete mPre;
		delete mNext;
	};

public:
	T mdata;
	Node * mPre;
	Node * mNext;
};

template<typename T>
class DoubleLinked_List {
public:
	DoubleLinked_List()
		: mHead(nullptr)
		, mTail(nullptr) 
	{};
	~DoubleLinked_List() 
	{
		delete mHead;
		delete mTail;
	};

	Node<T>* CreateNode(const T& data); //노드 생성
	void DestroyNode(Node<T>* _node);//노드삭제

	void InsertNode(const T& _data);//노드추가
	void RemoveNode(Node<T>* _node); //해당 노드 삭제


	void InsertAfter(Node<T>* _CurNode, Node<T>* _NewNode); //해당 노드 다음에 추가

	Node<T> * GetNodeAt(int index); //인덱스값 노드 가져오기
	void ShowAllList();

	int GetSize() const {
		return mLinkSize;
	}
private:
	int mLinkSize = 0;
	Node<T>* mHead;
	Node<T>* mTail;

};

template<typename T>
void DoubleLinked_List<T>::ShowAllList()
{
	for (int i = 0; i < mLinkSize; i++)
	{
		cout << i << " : " << GetNodeAt(i)->mdata << endl;
	}
}

template<typename T>
void DoubleLinked_List<T>::InsertAfter(Node<T>* _CurNode, Node<T>* _NewNode)
{
	_NewNode->mNext = _CurNode->mNext; //새로운 노드의 다음노드-> 현재노드의 다음노드
	_NewNode->mPre = _CurNode;  //새로운노드의 이전 노드-> 현재노드

	if (_CurNode->mNext != nullptr)
	{
		_CurNode->mNext->mPre = _NewNode;//a와b 사이의 새로운 노드가 추가되면, b노드의 전노드를 추가되는 노드로
	}

	_CurNode->mNext = _NewNode; //현재노드의 다음 노드가 추가된 노드 지정
}

template<typename T>
void DoubleLinked_List<T>::RemoveNode(Node<T>* _TargetNode)
{
	if (mHead == _TargetNode)  //지우는게 첫번째 노드면
	{
		mHead = _TargetNode->mNext; //지울 노드의 다음 노드 헤드로 만들어주기 

		if (mHead != nullptr)
		{
			mHead->mPre = nullptr; //지울 헤드노드의 이전 노드 지우기(현재 지워질노드)
		}

		_TargetNode->mPre = nullptr;
		_TargetNode->mNext = nullptr;
	}
	else {
		_TargetNode->mPre->mNext = _TargetNode->mNext;//(노드)이전->현재->다음을 이전->다음으로 이어줌

		if (_TargetNode->mNext != nullptr) //지워지는 노드가 마지막노드가 아니라면
		{
			_TargetNode->mNext->mPre = _TargetNode->mPre;//(노드)다음의 뒤노드를 현재의 뒤노드와 이어줌
		}

		_TargetNode->mPre = nullptr;
		_TargetNode->mNext = nullptr;
		delete _TargetNode;
	}

	mLinkSize--;
}

template<typename T>
Node<T> * DoubleLinked_List<T>::GetNodeAt(int index)
{
	if (index < 0 || mLinkSize < index)
	{
		return nullptr;
	}
	Node<T>* Current = mHead;

	while (Current != nullptr && (--index) >= 0) //현재노드가 비어있지 않고, 입력된 인덱스값을 찾으며 전위감소
	{
		Current = Current->mNext;
	}

	return Current;
}

template<typename T>
void DoubleLinked_List<T>::InsertNode(const T& _data)
{
	Node<T>* _newNode = CreateNode(_data);

	if (mHead == nullptr)
	{
		mHead = _newNode; 
		mTail = _newNode;
	}
	else //비어있지 않다면
	{
		mTail->mNext = _newNode; //현재 꼬리 = 추가 노드 

		_newNode->mPre = mTail;  //추가 노드의 이전 노드 = 현재의 꼬리노드

		mTail = _newNode; // 꼬리 = 추가 노드 갱신
	}

	mLinkSize++;
}

template<typename T>
void DoubleLinked_List<T>::DestroyNode(Node<T>* _node)
{
	delete _node;
}

template<typename T>
Node<T> * DoubleLinked_List<T>::CreateNode(const T& data)
{
	Node<T> * newNode = new Node<T>(data); //노드 할당

	return newNode;
}

int main() {
	DoubleLinked_List<int> DList;


	DList.InsertNode(1);
	DList.InsertNode(2);
	DList.InsertNode(3);
	DList.InsertNode(4);
	DList.InsertNode(5);
	DList.InsertNode(6);

	DList.ShowAllList();


	cout << "----------------------------" << endl;
	DList.RemoveNode(DList.GetNodeAt(1));
	cout << "1번 인덱스 삭제" << endl;
	cout << "----------------------------" << endl;

	DList.ShowAllList();


	cout << "----------------------------" << endl;
	cout << "1번 인덱스 다음에 새로운 노드 추가" << endl;
	DList.InsertAfter(DList.GetNodeAt(1), DList.CreateNode(7));

	cout << "----------------------------" << endl;

	DList.ShowAllList();

	return 0;
}//end of main