[C++] Double Linked List (Template)

어제인가 그제인가 밤에 박지성 나오는 축구시합을 보면서 맥주를 마시다가, (정작 박지성은 안나왔지만 -.,-);
불현듯 생각이 나서, 듀얼모니터로 축구를 보면서 더블 링크드 리스트를 작성해보았다.
중간에 코드를 작성하다가 Template에서 막히는 부분이 있어서 하루 더 걸렸고, Sorting 기능 추가하느라 하루 더 걸렸다.
(물론 하루종일 한건 아니고, 밤에 짬내서~)

이번에는 이전 단순 링크드 리스트에서 한발 더 나아가
더블링크드 리스트를 이용하고 더불어 공부해봤던 template를 이용하여 다양한 자료형을 허용하도록 코딩하였다.
template가 이외로 까다롭게 선언해야할 부분이 있어서 처음 template를 활성화 시켜 사용해보는터라 생각외의 에러를 발견할 수 있었다.

Sorting하는 부분에서는 단순한 삽입정렬을 이용하였다. 원래 삽입정렬은 위키피디아에 있는 최적화는 한 3~4줄에 끝나지만, 리스트의 경우 2개의 노드를 교환하는 부분에서 총 6개의 연결을 고려해야 하므로 노드 교환에만 6줄이 추가되었다. 특히 노드 교환후 포인터를 복귀해주어야 해서 4줄이 추가 ㅠ.ㅜ; 그러나 정렬은 잘된다.

Linked List와 Double Linked List의 차이점에 대해 먼저 알고 가자.
linked list의 경우 이어지는 노드가 단방향성을 갖는다.
하지만 double linked list의 경우 쌍방향성을 갖기 때문에 특정노드에서 이전노드 및 다음노드로의 이동이 자유롭다.
즉 하나의 Node에 두개의 Node *변수가 존재하여 이전노드와 다음노드를 가리킨다.
이 두가지의 경우는 아래 그림과 같다.

단일 링크드 리스트의 경우 삽입 또는 삭제시 반드시 전 노드를 알아야 한다.
하지만 그러기 위해서는 항상 노드 순회시 전 노드를 따로 저장하여야 한다.
이에 비해 Double Linked List의 장점은 역시 한 노드를 알면 이전 노드와 다음노드에 자유롭게 접근이 가능하다는 것이다.
단 삽입, 삭제시 할일이 많아져 코드 작성시 약간 헷갈리고 복잡해 진다.

더블링크드리스트의 큰 특징이라면 시작시 더미노드(Dummy Node)가 있다는 것이다.
이 더미 노드는 처음 노드를 가리키는 Head가 이 노드를 가리키게 된다.
처음 아무 자료가 없을시 이 더미노드의 양쪽 노드 포인터는 자기자신을 가리키고, 삽입 될때마다
더미노드의 우측은 시작되는 처음 노드를 가리키고, 좌측 노드는 리스트의 마지막을 가리키게 된다.
이와 마찬가지로 리스트 처음노드의 좌측 포인터는 더미노드를 가리키고, 리스트 마지막 노드 우측노드도 더미노드를 가리키게 된다.
이러한 구조는 더미노드로 하여금 리스트의 환영구조를 구현한다. 꼬리가 처음을 가리키는 형식으로 시작부터 바로 마지막 노드로의 접근이 가능해지며 별도의 끝을 가리키는 노드 포인터를 필요로 하지 않는다.
또한 전체적인 알고리즘이 상당히 안정적으로 해결되는 점이 있다.
프로그램을 짜면서도 처음에는 약간의아하지만 사용하고 나면 더미노드라는 점이 상당히 편리하다는 점을 알 수 있다.

[작성환경 : Window XP  작성툴 : Visual Studio 6.0  컴파일러 : Visual Studio 6.0  사용언어 : C++]
#include<iostream> using namespace std; template<typename T> class DLL; template<typename T> class Node{ friend class DLL<T>; private: T data; Node<T> *left; Node<T> *right; public: Node<T>(){data=0,left=right=NULL;}; Node<T>(T input){data=input,left=right=NULL;}; }; template<typename T> class DLL{ //dll is Double Linked List private: Node<T> *head; //Head is Special "First "Node public: DLL<T>(){ head=new Node<T>(); head->left=head; head->right=head; }; Node<T> *searchNode(T); //Find Target Node void insertNode(Node<T> *); Node<T> *deleteNode(T); void sortDLL(); void printDLL(); }; template<typename T> Node<T> *DLL<T>::searchNode(T input){ if(head->left==head&&head->right==head){ cout<<"Double Linked List is Empty"<<endl; return NULL; } else{ for(Node<T> *ptr=head->right;ptr!=head;ptr=ptr->right){ if(input==ptr->data) return ptr; } } cout<<input<<" don't exist in List"<<endl; return NULL; }; template<typename T> void DLL<T>::insertNode(Node<T> *in){ //Insert on Tail Node if(head->left==head&&head->right==head){ head->right=in; head->left=in; in->left=head; in->right=head; } else{ head->left->right=in; in->left=head->left; in->right=head; head->left=in; } }; template<typename T> Node<T> *DLL<T>::deleteNode(T inputData){ Node<T> *temp=searchNode(inputData); if(temp==NULL){ cout<<"Delete Data don't exist."<<endl; return NULL; } else{ temp->left->right=temp->right; temp->right->left=temp->left; return temp; } }; template<typename T> void DLL<T>::printDLL(){ if(head->left==head&&head->right==head){ cout<<"Double Linked List is Empty"<<endl; } else{ for(Node<T> *ptr=head->right;ptr!=head;ptr=ptr->right){ cout<<ptr->data<<" "; }cout<<endl; } }; template<typename T> void DLL<T>::sortDLL(){ // Insert Sort if(head->left==head&&head->right==head){ cout<<"Double Linked List is Empty"<<endl; } else{ Node<T> *j=head->right; // 1st Node Node<T> *i=head->right->right; // 2nd Node while(i!=head){ j=i,i=i->right; while(j!=head->right){ if(j->data>(j->left->data)) break; else{ Node<T> *temp=j->left; //Swap [temp Node] and [J Node] temp->left->right=j; //[temp Node] locate before [J Node] j->left=temp->left; temp->right=j->right; j->right->left=temp; //Connected 3 Node have 6 Linked Pointer, so need 6 code j->right=temp; temp->left=j; //End Swap Node<T> *tempJ=j; //Swap J and Temp j=temp; //Because Node Change, Need to Return Pointer(J,Temp) temp=tempJ; j=j->left; //Move Left one Node } } } cout<<"Sorting Complete"<<endl; } } void main(){ DLL<int> *dblist=new DLL<int>(); int ask; int idata; cout<<"[Double Linked List]"<<endl<<endl; while(1){ cout<<"Select Command (1.Insert 2.Delete 3.Print 4.Sort 5.Quit) : "; cin>>ask; switch(ask){ case 1:{ cout<<"Input [Insert Data(int)] : "; cin>>idata; Node<int> *iNode=new Node<int>(idata); dblist->insertNode(iNode); break; } case 2:{ cout<<"Input [Delete Data(int)] : "; cin>>idata; dblist->deleteNode(idata); break; } case 3: dblist->printDLL(); break; case 4: dblist->sortDLL(); break; case 5: cout<<"Exit Program, Good Bye"<<endl; exit(0); default: cout<<"Plz Re-Enter Command"<<endl; break; } } }

5~14 Line 은 Node의 선언이다. template 선언을 하였다.

6 Line에서는 DLL 클래스에서 Node의 멤버변수를 사용하도록 friend선언을 해주었다. 이 선언은 곧 Node Type과 DLL Type이 같아야 접근이 가능하다는 의미이기도 하다. (template)
또한 중요한점은 3 Line에서 Class DLL의 템플릿 전방선언을 해주어야 한다. 
미리 선언해야 DLL Class를 friend 선언에 사용할 수 있다. 

15~30 Line은 DLL(Double Linked List)의 선언부이다. 내부의 타입에 일일이 T선언을 해주어야 한다.
예전에 말했다시피 클래스의 템플린선언시에는 크기를 미리 알려줘야 메모리에 공간을 잡기 때문이다.

31~43 Line의 경우 search 함수의 구현이다. search의 경우 입력한 수와 같은 노드의 위치를 리턴한다.
후에 삽입이나 삭제시 필요한 노드의 위치를 얻어와서 쉽게 제어하기 위해서 만든 함수이다.

45~58 Line에서는 삽입인데, 삽입은 맨 마지막 노드에 넣어주도록 하였다. 이경우 더미노드인 Head에서 왼쪽으로 움직여 노드를 연결해준다. (더미노드에서 왼쪽으로 가면 바로 마지막 노드를 가리키기 때문이다.)

60~71 Line의 경우 삭제부분이다. 삭제시 삭제할 노드를 Search함수를 이용해 찾아낸후 바로 지운다. 함수자체가 삭제할 노드를 리턴한다. 중요한점은 여기서 내부적으로 삭제할 노드를 리턴하지 자체적으로 delete로 메모리 영역에서 지우지 않기 때문에  리턴값을 받은후 외부에서 delete코드를 이용하여야 한다. 사실 코드에서 132 Line 에서 리턴값을 받은후 메모리 영역에서 삭제(delete 문)해 주어야 하는데, 필자가 까먹고 코드를 넣지 않았다. 반드시 넣어주어야 한다.

83 Line~112 Line은 리스트를 정렬하는 알고리즘이다. 가장 구현이 쉬운 삽입정렬을 이용하였다. 알고리즘은 그대로 이용하고 노드간 이동을 구현하였다. 노드를 연결하는데 더블링크드리스트라 6번의 수술(?)이 필요했다. 그리고 노드간 이동후에는 포인터를 다시 원래되로 돌려주는 코드(103~105 Line) 부분이 반드시 들어가야 한다. 필자도 이부분을 간과했다가 애먹었다.

113~149 Line은 Main의 루틴이다. 중요한점은 각 Class 선언시 꺽쇄(<>)를 이용하여 템플릿 타입선언을 일일이 다해주어야 한다. 단 Node와 DLL의 type이 다르면 compile Error를 맛볼 수 있을 것이다.

<삭제와 입력 후 print 테스트, 정렬후 테스트, 삭제후 테스트 결과이다.>