LinkedList with class(양방)

class Node
{
private:
	int data;
	Node* next;
	Node* prev;
public:
	Node():data(-1),next(NULL) {};
	Node(int _data);	
	int GetData() { return data; };
	Node* GetNext() { return next; };
	Node* GetPrev() { return prev; };	//추가
	void SetNext(Node* ptr) { next = ptr; };
	void SetPrev(Node* ptr) { prev = ptr; };	//추가
};

노드가 next만 가리키는 것이 아니라 prev도 가리켜야하므로 prev를 추가해주었다

 

Node::Node(int _data)
{
	data = _data;
	next = NULL;
	prev = NULL;	//추가
}

prev추가

 

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

public:
	LinkedList();
	~LinkedList();

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

 

constructor와 destructor는 앞에서 보았던 것과 동일하고 밑의 메소드들이 조금씩 바뀌었다.

• PushBack(int _data)

void LinkedList::PushBack(int data)
{
	Node* temp_node = new Node(data);
	temp_node->SetPrev(tail);	// tail노드의 prev를 설정해준다
	tail->SetNext(temp_node);	// tail노드의 next를 설정해준다
	tail = temp_node;			// tail노드 뒤에 붙으므로 tail노드를 변경해준다
	CountData++;				// 전체 노드의 갯수가 하나씩 추가된다
}

• DeleteNode(int data)

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++)
		{

			if (temp_node->GetData() == data)
			{	
				if (temp_node==tail)
				{
					tail = pre_temp_node;
					pre_temp_node->SetNext(NULL);
				}
				else
				{
					temp_node->GetNext()->SetPrev(pre_temp_node);
					pre_temp_node->SetNext(temp_node->GetNext());
				}
				
				delete temp_node;
				CountData--;
				break;
			}

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

	}
}

delete 아직 안바꿨냐?? 다음에 바꿔라

 

• SelectInsert(int nodedata, int data)

void LinkedList::SelectInsert(int nodedata, int data)
{
	Node* temp_node = new Node(data);				// 새로운 노드 생성
	Node* selection_node = head->GetNext();			// 내가 찾고자 하는 노드

	for (int i = 0; i < CountData; i++)
	{
		if (selection_node->GetData() == nodedata)		// 찾고 싶은 노드를 찾았다면
		{
        	//여기는 꼬리에 삽입하는 부분
			if (selection_node == tail)					// tail노드는 next가 없어서 따로 설정
			{
				selection_node->SetNext(temp_node);		// 선택노드 next변경
				temp_node->SetPrev(selection_node);		// insertnode prev변경
				tail = temp_node;						// tail도 변경(pushback 상황)
				CountData++;							// 노드갯수 추가
				break;									// 반복문 탈출
			}
            //여기부터는 중간에 삽입하는 경우
			temp_node->SetNext(selection_node->GetNext());		// temp_node next부터 설정
			temp_node->SetPrev(selection_node->GetNext()->GetPrev());	// temp_node prev설정 
			temp_node->GetNext()->SetPrev(temp_node);	// temp_node의 next노드에서 prev설정
			selection_node->SetNext(temp_node);			// selection_node의 next 설정
			CountData++;								// 노드 갯수 추가
			break;										// 반복문 탈출
		}
		selection_node = selection_node->GetNext();		//내가 찾는 데이터를 못찾아서 하나씩 이동
		if (i + 1 == CountData)							//반복문을 다 돌았지만 해당 데이터가 없을때
		{
			cout << "찾는 데이터 "<<nodedata<<"가 존재하지 않습니다" << endl;
		}
	}


}

• Display()

void LinkedList::Display()
{
	Node* temp_node = head->GetNext();
	for (int i = 0; i < CountData; i++)
	{
		cout << i + 1 << "번째 노드의 데이터 : " << temp_node->GetData() << endl;
		if(temp_node == tail)
			cout << "next data :  " <<"no data"<<endl;
		else
			cout << "next data : " << temp_node->GetNext()->GetData() << endl;
		cout << "prev data : " << temp_node->GetPrev()->GetData() << endl;
		temp_node = temp_node->GetNext();
	}
	cout << endl;
	temp_node = head->GetNext();
	cout << "데이터 순서도 : ";		//시각적으로 리스트를 간편하게 보기 위해서 추가했다
	for (int i = 0; i < CountData; i++)
	{
		if (temp_node == tail)
			cout << temp_node->GetData() << endl;
		else
			cout << temp_node->GetData() << " -> ";
		temp_node = temp_node->GetNext();
	}
}

전체코드^O^

 

#include 

using namespace std;

class Node
{
private:
int data;
Node* next;
Node* prev;
public:
Node():data(-1),next(NULL) {};
Node(int _data);
int GetData() { return data; };
Node* GetNext() { return next; };
Node* GetPrev() { return prev; };
void SetNext(Node* ptr) { next = ptr; };
void SetPrev(Node* ptr) { prev = ptr; };
};

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


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

public:
LinkedList();
~LinkedList();

void PushBack(int _data);
void Display();
bool DeleteNode(int data);
void SelectInsert(int nodedata, 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)
{

Node* temp_node = new Node(data);
temp_node->SetPrev(tail);
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;
if(temp_node == tail)
cout << "next data :  " <<"no data"<<endl;
else
cout << "next data : " << temp_node->GetNext()->GetData() << endl;
cout << "prev data : " << temp_node->GetPrev()->GetData() << endl;
temp_node = temp_node->GetNext();
}
cout << endl;
temp_node = head->GetNext();
cout << "데이터 순서도 : ";
for (int i = 0; i < CountData; i++)
{
if (temp_node == tail)
cout << temp_node->GetData() << endl;
else
cout << temp_node->GetData() << " -> ";
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++)
{

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

delete temp_node;
CountData--;
break;
}

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

}
}
void LinkedList::SelectInsert(int nodedata, int data)
{
Node* temp_node = new Node(data);
Node* selection_node = head->GetNext();

for (int i = 0; i < CountData; i++)
{
if (selection_node->GetData() == nodedata)
{
if (selection_node == tail)
{
selection_node->SetNext(temp_node);
temp_node->SetPrev(selection_node);
tail = temp_node;
CountData++;
break;
}
temp_node->SetNext(selection_node->GetNext());
temp_node->SetPrev(selection_node->GetNext()->GetPrev());
temp_node->GetNext()->SetPrev(temp_node);
selection_node->SetNext(temp_node);
CountData++;
break;
}
selection_node = selection_node->GetNext();
if (i + 1 == CountData)
{
cout << "찾는 데이터 "<<nodedata<<"가 존재하지 않습니다" << endl;
}
}


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

list->PushBack(13);
list->PushBack(14);
list->PushBack(15);
list->PushBack(16);
list->SelectInsert(13, 88);
list->SelectInsert(18, 50);
list->Display();
cout << endl << endl;
list->DeleteNode(13);
list->Display();
cout << endl << endl;

list->DeleteNode(14);
list->DeleteNode(15);
list->Display();

cout << endl << endl;

list->Display();
return 0;
}