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

자료구조 스터디를 옆자리 짝꿍과 다시 시작했다.

매주 1개씩 구현해보기로 했다.

오랜만에 다시 짜니까 2시간 정도 걸렸다. 

 

아래는 C++로 구현한 싱글링크드리스트!

private member로 Head와 Count변수를 썼다.

노드 추가 시 Count++,

노드 제거 시 Count--해서 노드 수를 카운트 해줬다.

/*23-10-15 다시 짜본 싱글링크드리스트*/
#include <iostream>
using namespace std;

typedef struct Node
{
	int Data;
	Node* NextNode;

	Node(int NewData) : Data(NewData), NextNode(nullptr) {};
};
class SingleLinkedList
{
public:
	SingleLinkedList() : Head(nullptr), Count(0) {};
	~SingleLinkedList()
	{		
		while (Head != nullptr)
		{
			Node* DeleteNode = Head;
			Head = Head->NextNode;
			delete DeleteNode;
		}
	}

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

	/*추가*/
	void AddNode(Node* NewNode)
	{
		if (Head == nullptr)
		{
			Head = NewNode;
		}
		// 헤드가 있을 경우 꼬리 뒤에 붙인다
		else
		{
			Node* Tail = Head;
			while (Tail->NextNode != nullptr)
			{
				Tail = Tail->NextNode;
			}
			Tail->NextNode = NewNode;
		}
		// 노드 수 카운트 
		Count++;
	}

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

		// 헤드부터 노드의 데이타들 출력
		Node* Current = Head;
		while (Current->NextNode != nullptr)
		{
			cout << Current->Data << ' ';
			Current = Current->NextNode;
		}
		cout << Current->Data << ' ' << endl;
	}

	/*탐색*/
	Node* SearchNode(int SearchIndex)
	{
		Node* Current = Head;

		// 헤드부터 카운트하는데...
		while (Current->NextNode!= nullptr && --SearchIndex > 0)
		{
			Current = Current->NextNode;
		}

		return Current;
	}

	/*뒤에 삽입*/
	void InsertAfterNode(int Index, Node* NewNode)
	{
		// 탐색해서 어떤 애 뒤에 연결할지를 알아야 함
		Node* Current = SearchNode(Index);

		// 새로운 애를 먼저 연결하고, 앞에 있는 애를 새로운 애한테 연결		
		NewNode->NextNode = Current->NextNode;
		Current->NextNode = NewNode;

		Count++;
	}

	/*노드 소멸*/
	void DestroyNode(Node* DeleteTarget)
	{
		free(DeleteTarget);
	}

	/*노드 삭제*/
	void DeleteNode(Node* DeleteTarget)
	{
		// 딜리트 할 애가 Head일 때
		if (DeleteTarget == Head)
		{
			Head = DeleteTarget->NextNode;
		}
		// 헤드가 아닐 경우
		else
		{
			Node* Current = Head;
			while (Current != nullptr && Current->NextNode != DeleteTarget)
			{
				Current = Current->NextNode;
			}
			if (Current != nullptr)
			{
				Current->NextNode = DeleteTarget->NextNode;
			}			
		}
		DestroyNode(DeleteTarget);
		Count--;
	}

private:
	Node* Head;
	int Count;
};

int main()
{
	SingleLinkedList SLL;

	SLL.AddNode(SLL.CreateNode(1));
	SLL.AddNode(SLL.CreateNode(2));
	SLL.AddNode(SLL.CreateNode(3));
	SLL.AddNode(SLL.CreateNode(4));
	SLL.AddNode(SLL.CreateNode(5));
	SLL.Print();
	
	SLL.InsertAfterNode(3, SLL.CreateNode(9));
	SLL.Print();

	SLL.DeleteNode(SLL.SearchNode(4));
	SLL.Print();

	return 0;
}