[C++] LinkedList (링크드리스트 구현)

<사용된 기본적인 링크드 리스트의 구성도 - 리스트는 Node들의 연결로 이루어져 있다.
연결이란 포인터를 이용하여 연결되어 있다는 의미이다.
삽입 삭제는 이 포인터를 이용해 연결을 해제하거나, 새로운 연결을 짓는 과정을 통하여 이루어 진다.
배열보다 좋은 점은 역시 가변적, 동적이라는 점이어서 많은 부분에서 사용되며 가장 기본적인 내용이다.
또한 포인터의 개념을 잡는데 매우 도움이 되는 자료구조이다.>

2009년 연초 어느날 저녁을 밤 12시에 먹게 되어 -.,-;
새벽 3시까지, 잠을 안자고 있었는데,
갑자기 링크드 리스트나 구현해볼까하는 생각이 불쑥났다.
그래서 잠은 안오고, 걍 visual 6.0을 실행시켜서 백지에다가 링크드 리스트를 작성해봤다.
(다음날 생각해보니 좀 뻘짓... 차라리 Double Linked List나 해볼 것이지...)

뭐 그래도 예전처럼 무작정 한 것은 아니고,
나름 최적화(?) 되고, 쓸만한 코드를 생각하며 작성해봤다. 또한 예전 링크드 리스트 작성시 힘들었던 부분들을 상당수 고려하여 다시 작성하여 보았다.

CPP로 작성하였고, 삽입, 삭제, 출력 이 구현되어 있다.
검색기능을 넣으려고 했는데, 넣어봤자 삽입이나 삭제시 써먹지도 못해서 구현하지 않았다. (검색의 경우 찾은 노드를 가리키는 포인터를 반환하는 것이 직관적이다. 그러나 그럴 경우 전 노드를 알려주기 힘들다. - 삽입, 삭제시 해당노드의 전 노드를 알아야 한다.)
뭐 억지로 해당노드의 전노드를 반환하면 되겠지만, 함수의 목적에 위배되는 느낌이라 구현하지 않았다.
더블링크드 리스트를 다시 만들어 볼 예정인데 그때는 전 노드도 이동이 가능하니 그때 검색을 구현하여, 삽입, 삭제시 써먹으면 코드가 확실히 줄어들고 프로그램이 좀 괜찮아질 듯 싶다.

또한 단순화를 위해 노드의 자료형으로는 int형을 사용했고, (string을 사용해도 뭐 마찬가지-단 strcmp등을 사용해야함)
삽입시에는 맨 뒤에 삽입이 되도록 하였다. 그 이유는 삽입할때 정열이 되게도 가능하지만, 
차리리 정렬 함수를 따로 만들어 순수하게 받은 입력 값을 정렬하는 것이 더 도움이 될 것이라 생각했다.
(물론 정렬 함수는 여기서는 제외하였다. 허허) 

[작성환경 : Window XP  작성툴 : Visual Studio 6.0   컴파일러 : Visual Studio 6.0]
#include<iostream> using namespace std; class Node{ friend class List; public: Node(){ data=0; next=NULL; }; Node(int i){ data=i; next=NULL; } private: Node *next; int data; }; class List{ private: Node *head; public: List(){ head=NULL; }; List(Node *insertNode){ head=NULL; insert(insertNode); }; void insert(Node *insertNode); void del(int delNum); void printList(); }; void List::insert(Node *insertNode){ if(head==NULL){ head=insertNode; } else{ Node *current=head; Node *beforeCurrent=NULL; for(Node *ptr=head;ptr!=NULL;ptr=ptr->next) current=ptr; current->next=insertNode; } }; void List::del(int delNum){ if(head==NULL) cout<<"List is Empty"<<endl; else{ Node *current=head; Node *beforeCurrent=NULL; for(Node *ptr=head;ptr!=NULL;ptr=ptr->next){ beforeCurrent=current; current=ptr; if(current->data==delNum){ if(beforeCurrent==head && current==head) head=current->next; //check first Node else beforeCurrent->next=current->next; delete current; return; } } cout<<delNum<<" cannot find in List"<<endl; } return; }; void List::printList(){ if(head==NULL){ cout<<"List is Empty"<<endl; } else{ for(Node *ptr=head;ptr!=NULL;ptr=ptr->next){ cout<<ptr->data<<" "; }cout<<endl; } }; void inputSet(List *linkedList){ int select; cout<<"1.Insert 2.Delete 3.PrintList 4.Exit"<<endl<<">>"; cin>>select; switch(select){ case 1:{ int data; cout<<"Input Data(Integer) : "; cin>>data; Node *inputNode=new Node(data); linkedList->insert(inputNode); break;} case 2:{ int data; cout<<"Enter Delete Data(Integer) : "; cin>>data; linkedList->del(data); break;} case 3: linkedList->printList(); break; case 4: exit(0); break; } }; void main(){ List *linkedList=new List(); while(1) inputSet(linkedList); };

[참고사항]

솔직히 이정도 Simple LinkedList는 누구라도 구현이 가능하다.
필자가 위 코드를 하나씩 돌이켜보며 고민을 좀 했던 부분은 List전체를 순환하는 부분이다.
사실 리스트에서 중요한 부분은 첫번째 순환코드이다.
(삽입, 삭제는 각 노드에서 살짝 코드만 수정해 주면된다.)
두번째는 현재 노드와 이전노드 의 관리이다.
(이전 노드는 더블링크드리스트에서는 필요 없긴하다, 현재노드에서 바로 갈 수 있으니...)
순환코드에서 예전에 필자가 사용한 코드는
while(current->next!=NULL){ //To Do current=current->next; } //To Do
식의 루틴이다.
필자는 2학년 동안 리스트에 관한 노드 순환제어(트리나, 그래프 등등) 루틴에는 모두 위와 같은 방식을 사용했다.
근데 처음에는 생각없이 사용했는데 가장 큰 문제점은 마지막 노드를 들어가서 제어할 수가 없다는 것이다.
//To Do 부분과 current=current->next; 부분을 바꿀 경우에는 처음 노드 제어가 불가능하다.
(제어가 불가능하다는 말은 while문 밖에 while문 내부의 To Do를 한번 더 써줘야 한다는 사실이다.)
위의 코드도 보면 while문 안과 밖에 To Do가 두번 사용 된 것을 볼 수 있다.
간단하게 리스트의 마지막으로 이동하거나, 간단한 제어시에는 상관이 없으나 제어 소스가 길어지면 길어질수록 쓸데 없이 To Do 부분이 반복되며 소스양만 많아진다.

위 문제점을 해결하기 위해서는 while문 ( ) 내에 current!=NULL 로 바꿔주면 마지막 노드까지 이동이 가능하다.
while(current!=NULL){ //To Do current=current->next; }
위 코드는 모두 순환하기 때문에 ToDo는 한번만 사용하면 되지만,
하지만 이 때는 모두 순환시 마지막 current값이 null이 되기 때문에 마지막 노드를 찾아내기 힘들다.
그러기 위해서는 while문의 ()에 쓰이는 Node *변수를 current로 사용하지 말고 임의의 변수를 선언해야 한다.
while문전에 Node *ptr을 선언함으로써 가능하긴 하나, for문을 사용하면 효과적이다.

최종적인 순환코드는 다음과 같다.
for(Node *ptr=head;ptr!=NULL;ptr=ptr->next){ beforeCurrent=current; current=ptr; //To Do }
2, 3 Line는 현재 노드와 이전 노드를 지정하기 위한 코드이다. 이부분을 빼면 while보다 더 짧고 이해하기 쉽다.
순환에 쓰이는 노드 포인터 ptr과 current, beforeCurrent가 따로 사용되기 때문에 구분이 쉽다.
또한 ptr은 for문 내부에서만 사용되서 변수의 메모리 할당 공간도 더 적다.
2, 3 Line은 잘 생각해 보면 연속된 노드를 한칸 씩 당겨주는 역할을 한다.
또한 모두 순환하였을 때, current는 마지막 노드를 가리키고 있다.
필자가 예전에 생각했던 장점들과 단점을 제외한 최적의 코드 라 생각한다.

[소스설명]

3~17 Line : 리스트에 사용되는 노드를 정의한 클래스
18~72 Line : 리스트 클래스로 내부함수 입력, 출력, 삭제가 구현되어 있다.
삭제 부분은 지울 숫자를 입력하면 그 숫자를 찾아서 지운다. 이 때 살작 고려해야 할 부분은 
리스트가 비어있을 때,  지울 대상이 첫번째 노드일 경우 이다. (첫번째 노드를 지울때는 이전 노드를 사용하지 않기 때문에 처리 루틴이 일반과 다르다.) 지울 대상이 첫번째일 경우는 beforeCurrent와 current의 값이 초기값인 head일 경우 이다.
73~98 Line : 입력 인터페이스 함수
99~102 Line : 메인 함수 내부