C++ 싱글 링크드 리스트 구현 (Singly Linked List C++)

 

싱글 링크드 리스트는 단일 방향으로 한 노드는 값과 다음 노드를 가리키는 주소를 가지고 있다.

싱글 링크드의 제일 앞에 있는 값을 Front 또는 Head라고 함

싱글 링크드의 제일 뒤에 있는 값을 Back 또는 Tail이라고 함

node->value 현재의 노드가 저장한 값

node->next 다음 노드를 가리키는 주소

 

 

싱글 링크드 리스트에서 노드가 삭제될 때 전 노드는 삭제되는 노드의 다음 값만 가리키면 된다.

그 후 삭제될 노드는 delete를 이용해 동적 할당을 해제해 준다.

 

 

싱글 링크드 리스트에서 노드가 중간에 삽입될떄 새로 들어오는 노드는 기존에 있던 자리의 노드가 가리킨 앞의 노드를 가리키고 기존의 노드는 새로 들어온 노드를 가리키면 된다.

(빨간색: 새로운 노드, 파란색: 기존 노드, 초록색: 다음 노드)

 

 

싱글 링크드 리스트 코드(C++)

/*  템플릿과 클래스를 이용한 싱글 링크드 리스트 구현 - 2019/04/21 xtar.tistory */
#include<iostream>
using namespace std;

template <typename T>
struct Node // 노드 구조체
{
public:
	T value;
	struct Node<T> *next = nullptr;
};

template <typename T>
class SingleLinked_List //싱글 링크드 리스트 
{
private:
	Node<T> *head; //머리(front)
	Node<T> *tail; //꼬리(back)
	int size = 0; // 링크의 길이
public:
	SingleLinked_List() : head(nullptr), tail(nullptr) {} // 생성자 리스트
	~SingleLinked_List() {} //소멸자

	void AddNode(T _value) // 노드 추가하기(back)
	{
		Node<T> *node = new Node<T>; //노드 동적 할당

		size++;
		node->value = _value;
		node->next = nullptr;

		if (head == nullptr) //만약 머리가 없을경우
		{
			head = node;
			tail = node;
		}
		else // 만약 머리가 있을경우 뒤에 연결
		{
			tail->next = node;
			tail = tail->next;
		}

	}
	void RemoveNode(T _value) // 찾는 값 노드 지우기 
	{
		Node<T> *ptr = head;
		Node<T> *tmp = ptr;

		while (ptr != nullptr) // ptr 반복
		{
			if (ptr->value == _value) //만약 값을 찾앗다면
			{
				break;
			}
			else
			{
				tmp = ptr; //목표의 전 노드
				ptr = ptr->next;
			}
		}

		if (ptr == nullptr)
		{
			cout << "찾을 수 없는 노드 입니다" << endl;
		}
		else
		{
			size--;
			cout << "삭제된 노드의 값: " << ptr->value << endl;
			tmp->next = ptr->next; //삭제할 노드를 제외하고 연결
			delete ptr; // 동적 할당 해제

		}

	}

	void Show() // 리스트 안에 값 보여주기
	{
		Node<T> *node = head;

		while (node != nullptr) // 노드값이 null
		{
			cout << node->value << "->";
			node = node->next;
		}
		cout << endl;
	}
	void DeleteList() // 리스트 삭제하기 (동적할당 풀기)
	{
		Node<T> *ptr = head;

		while (ptr != nullptr)
		{
			head = ptr->next;
			delete ptr;
			ptr = head;
		}
		delete head; // null 포인터 삭제
		size = 0;
		cout << "리스트가 삭제되었습니다" << endl;
	}
	void RemoveTail() // 꼬리(back) 삭제하기
	{
		Node<T> *ptr = head;
		Node<T> *tmp = new Node<T>;

		while (ptr->next != nullptr)
		{
			tmp = ptr;
			ptr = ptr->next;
		}
		size--;
		tail = tmp;
		tail->next = nullptr;
		delete ptr; // 꼬리 동적할당 해제
	}
	void RemoveHead() // 헤드(front) 삭제하기
	{
		Node<T> *ptr = head;
		head = ptr->next;
		size--;
		delete ptr;

	}
	void AddHead(T _value) // 헤드(front)에 값넣기
	{
		Node<T> *ptr = new Node<T>();

		size++;
		ptr->next = head;
		ptr->value = _value;
		head = ptr;

	}
	void AddPosition(int _index, T _value)
	{
		if (size < _index || 0>_index) // 인덱스가 잘못될 경우
		{
			cout << "해당하는 인덱스 값은 없습니다." << endl;
			return;
		}

		Node<T> *ptr = head;
		Node<T> *tmp = ptr;
		Node<T> *node = new Node<T>; //새로 추가된 노드

		node->value = _value;
		node->next = nullptr;

		for (int i = 0; i < _index-1; i++)
		{
			tmp = ptr; // 들어갈 노드의 전 위치
			ptr = ptr->next; // 들어갈 노드의 위치 
		}
		tmp->next = node; 
		node->next = ptr; //새노드는 기존에 있는 노드위치를 가리킨다.
		size++;
		

	}
	void SearchValue(T _value) // 원하는 값이 몇 번쨰에 있는지 확인하기
	{
		Node<T> *ptr = head;
		int index = 0;
		bool isFind = false; //찾앗는지 확인하는 bool 값

		while (ptr != nullptr)
		{

			index++;
			if (ptr->value == _value) // ptr 값이랑 같을떄 인덱스값 반환
			{
				cout << _value << " 값은 인덱스 " << index << " 번쨰에 있습니다" << endl;
				isFind = true;
				break;
			}
			ptr = ptr->next;
		}

		//못찾았을 경우
		if (isFind == false)
		{
			cout << _value << " 값은 리스트 안에 없습니다. " << endl;
		}
	}


	int Size() // 리스트 크기를 반환
	{
		return size;
	}

};
int main()
{
	// 리스트 동적할당의 경우
	//SingleLinked_List<int> *List = new SingleLinked_List<int>(); 
	//List->add_node(10);
	//List->add_node(11);
	//List->show();
	//delete List;

	SingleLinked_List<int> List; //리스트 정적할당
	//리스트에 노드 추가하기
	List.AddNode(10);
	List.AddNode(11);
	List.AddHead(14);
	List.AddHead(18);
	List.AddHead(1);
	List.AddPosition(2, 7); // 인덱스 2번쨰에 값 7넣기
	List.Show();
	List.SearchValue(10);
	cout << "리스트의 크기 " << List.Size() << endl; // 리스트 크기 반환

	List.AddHead(4); // 리스트 헤드에 값넣기
	List.AddNode(9);
	List.Show();
	cout << "리스트의 크기 " << List.Size() << endl; // 리스트 크기 반환

	List.RemoveHead(); //리스트 헤드 삭제
	List.RemoveTail(); //리스트 꼬리 삭제
	List.RemoveNode(14); //리스트에서 값이 14인 노드 삭제
	List.SearchValue(14); //삭제된 14값 찾기

	List.Show();
	cout << "리스트의 크기 " << List.Size() << endl; // 리스트 크기 반환

	List.DeleteList(); //리스트 삭제하기 (모든 노드 동적할당 해제)
	List.AddNode(10);
	List.Show();
	cout << "리스트의 크기 " << List.Size() << endl; // 리스트 크기 반환

	return 0;
}

TestCase

 

이미지출처 - https://en.wikipedia.org/wiki/Linked_list