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;
}
'알고리즘' 카테고리의 다른 글
LinkedList with class(단일) (0) | 2019.11.11 |
---|---|
C++ 클래스와 constructor, destructor 간단 정리 (0) | 2019.11.10 |
Big-O 표기법 (0) | 2019.11.08 |