DataStructure] C++ 연결 리스트(Single Linked List)

2학년 1학기(벌써 작년이다)에 필자는 C언어로 자료구조론을 배운 적이 있다.

당시에는 C언어로 모든 것을 작성했었다.

자료구조도 복습하고, C++ 연습하는 겸,

C++로 자료구조들을 구현하는 시도를 하고 있다.

오늘은 그 첫번째 시도로 단일 연결 리스트(혹은 단순 연결 리스트;Single Linked List)를 만들어봤다.

head, tail, 중간 삽입이 모두 가능하고,

삭제하는 건 head에서만 이뤄지도록 했다.

그냥 구현에 초점을 둬서 완벽한 예외처리나, template을 활용하거나 하지는 않았지만,

근시일내에 그런 걸 다 집어넣고 다시 한 번 짤 생각이다.

(왜 remove만 핫핑크로 하이라이팅되는 거지?...)

#include <iostream>
using namespace std;
class Node
{
	friend class List;
private:
	int value;
	Node* next;
	Node(int v, Node* n)
	{
		value = v;
		next = n;
	}
	Node()
	{
		value = 0;
		next = nullptr;
	}
};
class List
{
private:
	Node* head;
	Node* tail;
	int size;

public:
	List(int);
	void insertHead(int);
	void insertTail(int);
	void insert(int, int);
	void deleteHead();
	void print();
	~List();
};
List::List(int value)
{
	head = tail = new Node(value,nullptr);
	size = 1;
}
void List::insertHead(int value)
{
	Node* newNode = new Node(value, nullptr);
	if (head == nullptr)
	{
		tail = newNode;
	}
	else
	{
		newNode->next = head;
	}
	head = newNode;
	size++;
}
void List::insertTail(int value)
{
	Node* newNode = new Node(value, nullptr);
	if (head == nullptr)
	{
		head = newNode;
	}
	else
	{
		tail->next = newNode;
	}
	tail = newNode;
	size++;
}
void List::insert(int value, int idx)
{
	/* 리스트의 시작점(Head)은 0으로 간주함 */
	Node* current = head;
	if (idx >= size || idx < 0)
	{
		cout << "인덱스 초과" << endl;
		return;
	}
	else
	{
		if (idx == 0)
		{
			insertHead(value);
		}
		else if (idx == size - 1)
		{
			insertTail(value);
		}
		else {
			Node* newNode = new Node(value, nullptr);
			int i = 0;
			while (i < idx-1)
			{
				current = current->next;
				i++;
			}
			newNode->next = current->next;
			current->next = newNode;
		}
	}
	size++;
}
void List::deleteHead()
{
	if (head != nullptr)
	{
		Node* remove = head;
		head = head->next;
		delete remove;
		size--;
	}
}
void List::print()
{
	Node* current = head;
	while (current != nullptr)
	{
		if (current->next == nullptr)
		{
			cout << current->value << endl;
		}
		else
		{
			cout << current->value << " -> ";
		}
		current = current->next;
	}
}
List::~List()
{
	Node* current = head;
	while (current != nullptr)
	{
		deleteHead();
	}
}
int main()
{
	List* list = new List(1);
	for (int i = 5; i <= 10; i++)
	{
		list->insertHead(i);
	}
	list->print();
	list->deleteHead();
	list->deleteHead();
	list->print();
	for (int i = 15; i <= 20; i++)
	{
		list->insertTail(i);
	}
	list->print();
}