[자료구조] Double Linked List (C++)

오늘 아침에 새로운 스터디에서 다시 더블링크드리스트를 공부했다.

이전과 다르게 private member로 Tail을 추가했다.

공부한 날 다시 짜서일까? 1시간 반 정도만에 완성했다.

 

/*1023 더블링크드리스트*/
#include <iostream>
using namespace std;

typedef struct Node
{
	int Data;
	Node* PrevNode;
	Node* NextNode;
	Node(int NewData) : Data(NewData), PrevNode(nullptr), NextNode(nullptr) {};
};
class DoubleLinkedList
{
public:
	DoubleLinkedList() : Head(nullptr), Tail(nullptr), Count(0) {};
	~DoubleLinkedList()
	{
		while (Head != nullptr)
		{
			Node* DeleteTarget = Head;
			Head = Head->NextNode;

			delete DeleteTarget;
		}
	}

public:
	/*생성*/
	Node* CreateNode(int NewData)
	{
		Node* NewNode = new Node(NewData);
		return NewNode;
	}

	/*추가*/
	void AddNode(Node* NewNode)
	{
		if (Head == nullptr) // 뉴노드가 헤드가 됨
		{
			Head = NewNode;
			Tail = NewNode;
		}
		else // 테일 뒤에 연결
		{
			NewNode->PrevNode = Tail;
			Tail->NextNode = NewNode;
		
			Tail = NewNode;
		}
		Count++;
	}

	/*출력*/
	void Print()
	{
		cout << "노드 수: " << Count << '\n';

		Node* Current = Head;
		while (Current->NextNode != nullptr)
		{
			cout << Current->Data << " ";
			Current = Current->NextNode;			
		}
		cout << Current->Data << " " << endl;
	}

	/*탐색*/
	Node* SearchNode(int Index)
	{
		Node* SearchTarget = Head;
		while (--Index > 0 && SearchTarget != nullptr )
		{
			SearchTarget = SearchTarget->NextNode;
		}

		//cout << "\n" << SearchTarget->Data << endl;
		
		return SearchTarget;
	}

	/*삽입*/
	void InsertAfter(int Index, Node* NewNode)
	{
		// Index로 받아온 노드 뒤에 삽입!
		Node* Current = SearchNode(Index);

		// 헤드가 테일이면 한개 밖에 없고, 그 애 뒤에 붙이는 것!
		if (Head == Tail)
		{
			NewNode->PrevNode = Head;
			Head->NextNode = NewNode;
			NewNode = Tail;
		}
		else
		{
			// Current 뒤에 NewNode를 붙일 예정
			NewNode->PrevNode = Current;
			NewNode->NextNode = Current->NextNode;

			Current->NextNode->PrevNode = NewNode;
			Current->NextNode = NewNode;
		}

		Count++;
	}

	/*소멸: 끊긴 노드 지우기*/
	void DestroyNode(Node* DeleteTarget)
	{
		delete DeleteTarget;
	}
	
	/*삭제: 노드 끊기*/
	void DeleteNode(Node* DeleteTarget)
	{
		// 타겟 prev의 nextnode를 타겟의 next로 먼저 연결하자

		if (DeleteTarget == Head)
		{
			Head = DeleteTarget->NextNode;
			Head->PrevNode = nullptr;

			if (Head == nullptr)
			{
				Tail == nullptr;
			}
		}
		else
		{
			DeleteTarget->PrevNode->NextNode = DeleteTarget->NextNode;
			DeleteTarget->NextNode = DeleteTarget->PrevNode;
		}

		DestroyNode(DeleteTarget);
		Count--;
	}

private:
	Node* Head;
	Node* Tail;
	int Count;
};
int main()
{
	DoubleLinkedList DLL;
	DLL.AddNode(DLL.CreateNode(1));
	DLL.AddNode(DLL.CreateNode(2));
	DLL.AddNode(DLL.CreateNode(3));
	DLL.AddNode(DLL.CreateNode(4));
	DLL.AddNode(DLL.CreateNode(5));
	DLL.Print();
	
	DLL.InsertAfter(3, DLL.CreateNode(6));	
	DLL.Print();

	DLL.DeleteNode(DLL.SearchNode(3));
	DLL.Print();


	return 0;
}