[자료구조]연결리스트 SLL(SinglyLinkedList) / 템플릿 /C++

이번엔 링크드 리스트다. 

 

장점:

- 새로운 노드의 추가/삽입/삭제 쉽고 빠름( 배열은 요소를 삽입하거나 제거하기 어렵)

 

 

단점 :

- 다음 노드를 가리키려는 포인터 때문에 각 노드마다 4바이트의 메모리가 추가로 필요.

- 특정 위치에 있는 노드를 얻는데 드는 비용이 크며, 속도도 느리다.

 

 

 

링크드리스트의 필요한 기본 연산은 5가지

- 노드생성/소멸

- 노드 추가

- 노드 탐색

- 노드 삭제

- 노드 삽입

 

 

코드 :

기본 노드 클래스

 

 

 

 

 

 

 

 

 

 

 

 

#include <iostream>
using namespace std;

template<typename T> class Node {
public:
	Node() {};
	Node(T _data)
		:data(_data)
	{}
	~Node() {};

	T data; //현재 노드에 있는 데이터
	Node * next; //현재 노드의 다음 노드를 가리키는 포인터
};

template<typename T> class SingleLinked_List {
public:
	SingleLinked_List() :head(nullptr), tail(nullptr) {};
	~SingleLinked_List() {};

	void AddHeadNode(T _data); //맨앞에 노드 추가

	void AddNode(T _data); //맨뒤에 노드 추가 
	void RemoveNode(T _data);//해당 값의 노드 삭제

	void AddTargetPosition(int index, T _data);//지정 된 인덱스에 값 추가

	void RemoveTail(); //맨 뒤 노드 삭제
	void RemoveHead(); //맨 앞 노드 삭제

	void DeleteList(); //모든 노드 삭제

	void SearchData(T _data);//해당 값 검색
	void ShowAllList(); //모든 노드 보기

	int GetSize() const {
		return LinkSize;
	}
private:
	int LinkSize = 0;
	Node<T> * head; 
	Node<T> * tail; 

};



template<typename T>
void SingleLinked_List<T>::SearchData(T _data){
	Node<T> *ptr = head; 
	int index = 0;
	bool isFind = false;
	cout << "검색 : 리스트에서 "<<_data<<" 찾기결과 -> ";
	//찾앗는지 확인하는 bool 값
	while (ptr != nullptr) {
		index++; 
		if (ptr->data == _data){
			cout << _data << " 값은 " << index << "번 인덱스에 있습니다" << endl;
			isFind = true;
			break; 
		}
		ptr = ptr->next;
	} //못찾았을 경우
	if (isFind == false) { 
		cout << _data << " 값은 리스트 안에 없습니다. " << endl;
	}
}//end of SearchData


template<typename T>
void SingleLinked_List<T>::AddTargetPosition(int _index, T _data){
	if (LinkSize < _index || 0>_index){
		cout << "해당하는 인덱스 값은 없습니다." << endl; 
		return;
	} 
	Node<T> *ptr = head;
	Node<T> *tmp = ptr;
	Node<T> *node = new Node<T>;
	node->data = _data;
	node->next = nullptr;
	for (int i = 0; i < _index-1; i++) { 
		tmp = ptr; // 들어갈 노드의 전 위치
		ptr = ptr->next; // 들어갈 노드의 위치 
	} 
	tmp->next = node;
	node->next = ptr; //새노드는 기존에 있는 노드위치를 가리킨다.
	LinkSize++;		
}//end of AddTargetPosition



template<typename T>
void SingleLinked_List<T>::AddHeadNode(T _data){
	cout << "추가 :맨앞 head 에 " << _data << " 추가 하기" << endl;
	Node<T> *ptr = new Node<T>();
	LinkSize++;
	ptr->next = head;
	ptr->data = _data; 
	head = ptr;
}//end of AddHeadNode



template<typename T>
void SingleLinked_List<T>::ShowAllList(){
	Node<T> *node = head;
	//cout << "현재 노드 상태 : ";
	if (node == nullptr) {
		cout << "보여 줄 수 있는 노드가 없습니다." << endl;
	}
	while (node != nullptr)  {
		cout << node->data << "->";
		node = node->next;
	} 
	cout << endl;
}//end of ShowAllList


template<typename T>
void SingleLinked_List<T>::DeleteList(){
	Node<T> *ptr = head;
	cout << "리스트가 비워졌습니다" << endl;
	while (ptr != nullptr) { 
		head = ptr->next;
		delete ptr; 
		ptr = head;
	} 
	delete head; // null 포인터 삭제
    size = 0;
    cout << "리스트가 삭제되었습니다" << endl;

}//end of DeleteList


template<typename T>
void SingleLinked_List<T>::RemoveHead(){
	Node<T> *ptr = head;
	head = ptr->next;
	LinkSize--;
	delete ptr;
}//end of RemoveHead


template<typename T>
void SingleLinked_List<T>::RemoveTail(){
	Node<T> *ptr = head;
	Node<T> *tmp = new Node<T>;

	while (ptr->next != nullptr) {
		tmp = ptr; ptr = ptr->next;
	}
	LinkSize--;
	tail = tmp;
	tail->next = nullptr;
	delete ptr;

}//end of RemoveTail

template<typename T>
void SingleLinked_List<T>::RemoveNode(T _data){
	Node<T> *ptr = head; 
	Node<T> *tmp = ptr;

	while (ptr != nullptr) { 
		if (ptr->data == _data) {//값 찾기 성공
			break;
		}
		else { //값 찾기 실패 시 
			tmp = ptr;
			ptr = ptr->next;
		}
	}//end of while
	if (ptr == nullptr) 
		cout << _data<<" 삭제 실패(값 존재x)" << endl;
	else{
		LinkSize--;
		cout << "삭제 된 노드의 값 " << ptr->data<< endl;
		tmp->next = ptr->next;
		delete ptr; //생성해제
	}
}//end of RemoveNode


template<typename T>
void SingleLinked_List<T>::AddNode(T _data){
	Node<T> * node = new Node<T>; //노드 할당

	LinkSize++;

	node->data = _data;
	node->next = nullptr;

	if (head == nullptr) { //머리노드 없으면 추가
		head = node;
		tail = node;
	}
 	else {//머리노드 있으면 뒤에 추가
		tail->next = node;
		tail = tail->next;
	}
}//end of AddNode




int main() {
	SingleLinked_List<int> List; 	
	cout << "1. 노드 추가 :" << endl;
	 List.AddNode(10); List.AddNode(11);
	 List.ShowAllList();
	 cout << "------------------------------" << endl;
	 cout << "2. 노드 위치 지정 추가 :" << endl;
	 List.AddTargetPosition(2, 7); // 인덱스 2번쨰에 값 7넣기 
	 List.ShowAllList();
	 cout << "------------------------------" << endl;
	 cout << "3. 값 검색 :" << endl;
	 List.SearchData(10);
	 List.ShowAllList();
	 cout << "------------------------------" << endl;
	 List.AddHeadNode(4);
	 List.AddNode(9); 	 
	 List.ShowAllList();
	 cout << "------------------------------" << endl;
	 cout << "4. 값 삭제 :" << endl;
	 List.RemoveNode(14); //리스트에서 값이 14인 노드 삭제 
	 List.SearchData(14); //삭제된 14값 찾기
	 List.RemoveNode(7);
	 List.ShowAllList();
	 cout << "------------------------------" << endl;
	 cout << "4-2.맨앞/맨뒤 값 삭제 :" << endl;
	 List.RemoveHead(); //리스트 헤드 삭제
	 List.RemoveTail(); //리스트 꼬리 삭제
	 List.ShowAllList();
	 cout << "------------------------------" << endl;
	 cout << "5. 전부 삭제 :" << endl;
	 List.DeleteList(); //리스트 삭제하기 (모든 노드 동적할당 해제) 
	 List.ShowAllList();
	 cout << "------------------------------" << endl;
	return 0;
}//end of main