LinkedList with class(단일)

class Node
{
private:
	int data;
	Node* next;

public:
	Node():data(0),next(NULL) {};	//dummy node만들어서 head가 가리키게 만든다
	Node(int _data);	//생성자로서 멤버변수 data와 next를 결정한다
	int GetData() { return data; };		// data를 토해낸다
	Node* GetNext() { return next; };	// next를 토해낸다
	void SetNext(Node* ptr) { next = ptr; }	// next를 재설정한다
	
};

node를 만들었다.

접근자 영역을 멤버변수에 private으로 제한을 두고 나머지 메소드들은 public으로 두었다.

 

• 생성자 Node() : 디폴트 생성자로 data를 0, next를 NULL로 초기화
• 인자를 갖는 생성자 Node(int _data) : 해당 input값을 data에 넣어서 노드를 만들다

Node::Node(int _data)
{
	data = _data;
	next = NULL;
}

• GetData() : data값을 return한다
• GetNext() : next값을 return한다
• SetNext(Node* ptr) : 해당 노드의 next가 가리키는 곳을 ptr로 바꾼다

class LinkedList
{
private:
	Node* head;
	Node* tail;
	int CountData;

public:
	LinkedList();
	~LinkedList();

	void PushBack(int _data);
	void Display();
	bool DeleteNode(int data);
};

• 멤버 변수를 head(리스트에서 가장 앞부분을 가리킨다)와 tail(리스트에서 가장 마지막 부분을 가리킨다)과 CountData(해당 리스트가 몇개인지)를 정의
• LinkedList() : 디폴트 생성자로 head와 tail은 새로운 노드(dummy node)를 가리킨다

LinkedList::LinkedList()
{
	head = new Node();	//dummy node
	tail = head;
	CountData = 0;
}

• ~LinkedList() : 소멸자로 동적할당을 삭제해준다

LinkedList::~LinkedList()
{
	Node* temp_node = head;
	delete head;
	head = temp_node->GetNext();


	for (int i = 0; i < CountData; i++)
	{
		temp_node = temp_node->GetNext();
		delete head;
		head = temp_node->GetNext();
	}

	cout << head->GetData() << endl;

}

• PushBack(int data) : 대입하고 싶은 데이터 값을 연결 리스트 가장 마지막부분에 덧대어서 붙인다. push를 할 때는 tail의 위치가 계속 바뀌므로 주의하자.

void LinkedList::PushBack(int data)
{
	if (head->GetNext() == NULL)
	{
		Node* temp_node = new Node(data);	// data값을 가진 노드 생성하여 temp_node에 임시저장
		head->SetNext(temp_node);			// head의 next값을 바꿔준다
	}
	else
	{
		Node* temp_node = new Node(data);	
		tail->SetNext(temp_node);			// tail의 next값을 바꿔준다
	}
    tail = temp_node;						// tail이 가리키는 값을 변경한다
	CountData++;							// 리스트의 수가 하나씩 증가하게 된다
}

• DeleteNode(int data) : 지우고 싶은 데이터를 head부터 순차적으로 검사를 진행하여 해당 노드를 지우게 되는 과정이다. 데이터가 아무것도 없을때는 false를 반환하고 있을때는 2개의 임시노드를 만들어서 값을 비교해주면서 지워나가면 된다

tail 노드를 지울 경우 tail앞의 노드가 tail이 되어야한다

bool LinkedList::DeleteNode(int data)
{
	if (head->GetNext() == NULL)		//데이터가 하나도 없는 경우
	{
		cout << "데이터 없는뎁숑" << endl;
		return false;
	}
	else
	{
		Node* pre_temp_node = head;		//head를 가리키는 노드 하나 지정
		Node* temp_node = pre_temp_node->GetNext();	// 더미노드를 제외한 첫번째 노드

		for (int i = 0; i < CountData; i++)
		{
			if (temp_node->GetData() == data)	//내가 찾고자 하는 데이터가 나오면
			{
				
				if (temp_node->GetNext() == NULL)	//내가 찾고자 하는 데이터의 노드가 tail이면
				{
					tail = pre_temp_node;
					pre_temp_node->SetNext(NULL);
				}
				else								//보통의 경우
				{
					pre_temp_node->SetNext(temp_node->GetNext());
				}
				
				delete temp_node;					// 노드를 삭제하고
				CountData--;						// 리스트의 갯수 하나감소시킨다
				break;
			}

			pre_temp_node = pre_temp_node->GetNext();
			temp_node = temp_node->GetNext();
		}

	}
}

 

 

이렇게 하면 단일 Linked List가 완성된다

 

그림은 직접 그리시오

 

다음은 전체코드이니 참고하면 좋겠다.

#include 

using namespace std;

class Node
{
private:
int data;
Node* next;

public:
Node():data(0),next(NULL) {}; //dummy node만들어서 head가 가리키게 만든다
Node(int _data); //생성자로서 멤버변수 data와 next를 결정한다
int GetData() { return data; }; // data를 토해낸다
Node* GetNext() { return next; }; // next를 토해낸다
void SetNext(Node* ptr) { next = ptr; } // next를 재설정한다

};

Node::Node(int _data)
{
data = _data;
next = NULL;
}


class LinkedList
{
private:
Node* head;
Node* tail;
int CountData;

public:
LinkedList();
~LinkedList();

void PushBack(int _data);
void Display();
bool DeleteNode(int data);
};

LinkedList::LinkedList()
{
head = new Node();
tail = head;
CountData = 0;
}
LinkedList::~LinkedList()
{
Node* temp_node = head;
delete head;
head = temp_node->GetNext();

for (int i = 0; i < CountData; i++)
{
temp_node = temp_node->GetNext();
delete head;
head = temp_node->GetNext();
}

cout << head->GetData() << endl;

}
void LinkedList::PushBack(int data)
{
if (head->GetNext() == NULL)
{
Node* temp_node = new Node(data);
head->SetNext(temp_node);
tail = temp_node;
}
else
{
Node* temp_node = new Node(data);
tail->SetNext(temp_node);
tail = temp_node;
}
CountData++;
}
void LinkedList::Display()
{
Node* temp_node = head->GetNext();
for (int i = 0; i < CountData; i++)
{
cout << i + 1 << "번째 노드의 데이터 : " << temp_node->GetData() << endl;
temp_node = temp_node->GetNext();
}
}
bool LinkedList::DeleteNode(int data)
{
if (head->GetNext() == NULL)
{
cout << "데이터 없는뎁숑" << endl;
return false;
}
else
{
Node* pre_temp_node = head;
Node* temp_node = pre_temp_node->GetNext();

for (int i = 0; i < CountData; i++)
{
cout << "pre_temp_node : " << pre_temp_node->GetData() << endl;
cout << "temp_node : " << temp_node->GetData() << endl;
if (temp_node->GetData() == data)
{

if (temp_node->GetNext() == NULL)
{
tail = pre_temp_node;
pre_temp_node->SetNext(NULL);
}
else
{
pre_temp_node->SetNext(temp_node->GetNext());
}

delete temp_node;
CountData--;
break;
}

pre_temp_node = pre_temp_node->GetNext();
temp_node = temp_node->GetNext();
}

}
}
int main()
{
LinkedList *list = new LinkedList();

list->PushBack(13);
list->PushBack(14);
list->PushBack(15);
list->PushBack(16);
list->Display();

list->DeleteNode(16);
list->Display();

list->DeleteNode(13);
list->Display();

list->DeleteNode(21);
list->Display();
return 0;
}