이번에는 간단하게 단순(단일) 연결리스트를 만들어 보아요. 여기에서 만드는 단순 연결리스트는 개념을 잡기 위해 만드는 것으로 노드에 보관할 자료 형식을 정수로 한정할게요. 뒤에서 STL을 모델로 list를 만들 때 어떠한 자료 형식도 보관할 수 있게 만들거예요.
제공할 기능은 생성자, 해제화, 맨 뒤에 보관, 맨 앞에 보관, 원하는 위치에 보관, 탐색 가능한 반복자 제공, 데이터 제거, 데이터 보관 유무 확인, 전체 보기 기능입니다.
단순 연결리스트를 정의할 클래스 이름을 SimpleLinkedList라 정합시다.
class SimpleLinkedList
{
단순 연결리스트의 노드는 데이터와 다음 노드의 위치 정보를 기억하는 링크로 구성합니다.
노드는 연결리스트에서 접근하기 쉽게 구조체로 정의합시다. 사용하는 개발자는 노드 형식을 알 필요가 없습니다. 따라서 Node 형식은 디폴트 가시성인 private으로 접근 지정할게요.
struct Node //단순 연결리스트의 노드
{
//노드는 데이터와 링크로 구성합니다.
//여기에서 만들 연결리스트는
//단순 연결리스트이므로 링크의 개수는 한 개입니다.
int data;
Node *next;
Node(int data=0)
{
//멤버 data는 입력 인자로 받은 data로 설정하세요.
this->data = data;
//next 링크의 값은 0(널)로 설정하세요.
next = 0;
}
};
여기에서는 연결리스트의 맨 앞의 노드의 위치 정보와 맨 마지막 노드의 위치 정보를 기억하는 멤버 head와 tail이 있는 구조로 정의하기로 해요.
Node *head; //연결리스트 맨 앞 노드의 위치 정보
Node *tail; //연결리스트 맨 뒤 노드의 위치 정보
연결리스트에 보관한 데이터를 탐색하기 위한 반복자를 제공합시다. 클래스 이름은 Iterator로 할게요.
public:
class Iterator//연결 리스트에 보관한 데이터를 탐색하기 위한 반복자
{
//연결리스트를 탐색할 때 현재 노드의 위치 정보를 멤버 필드로 기억하고 있어야 합니다.
Node *node;//현재 노드의 위치 정보
public:
//연결리스트에서는 모든 멤버에 접근할 수 있게 friend로 지정하세요.
friend class SimpleLinkedList;//연결리스트에서는 모든 멤버에 접근 권한 부여
//생성자에서는 현재 노드의 위치 정보를 입력 인자로 받아 멤버 필드를 설정합니다.
Iterator(Node *node=0)
{
this->node = node;
}
//현재 노드에 보관한 자료를 접근할 수 있어야겠죠.
int GetData()const //현재 노드에 보관한 자료 접근자
{
if(node==0)//현재 노드가 없을 때
{
throw "유효한 노드를 가리키고 있지 않습니다.";
}
return node->data;
}
//탐색하기 위한 형식이므로 다음 노드의 위치로 이동하는 메서드를 제공합시다.
bool MoveNext()//다음 노드의 위치로 이동
{
if(node->next)//다음 노드가 있을 때
{
node = node->next;//다음 노드 위치 정보로 변경
return true;
}
return false;
}
//탐색할 끝인지 판별하기 위해서는 같은지 다른지 판별하는 기능이 필요합니다.
bool operator==(const Iterator &iter)//같은지 판별
{
return node == iter.node;
}
bool operator!=(const Iterator &iter)//다른지 판변
{
return node != iter.node;
}
};
생성할 때 노드가 없으므로 head와 tail을 0으로 초기화합니다.
SimpleLinkedList()
{
head = 0;
tail = 0;
}
맨 앞의 노드부터 순차적으로 소멸합시다. 그런데 노드를 소멸한 후에 다음 노드의 위치를 알 수 없기 때문에 노드의 위치를 이동한 후에 이전 노드를 지우는 형태로 작성해야 합니다.
~SimpleLinkedList()
{
Node *prev=0;
//head가 존재하면 반복합니다.
while(head !=0)
{
//head를 이동하기 전에 prev에 head를 대입하고 head를 이동하세요.
prev = head;
head = head->next;
//기억해 두었던 prev를 소멸합니다.
delete prev;
}
}
순차보관하는 PushBack 메서드를 구현합시다.
void PushBack(int data)
{
//입력한 자료를 보관할 노드를 생성하세요.
Node *node = new Node(data);
비어있는 상태라면 head와 tail이 새로 생성한 노드를 가리키게 설정하세요.
if(head==0)//비어있을 때
{
head = tail = node;
}
보관한 자료가 있을 때는 tail의 next 링크를 새로운 노드를 가리키게 하고 tail을 새로운 노드로 설정합니다.
else
{
tail->next = node;
tail = node;
}
}
맨 앞에 보관하는 PushFront 메서드를 구현합시다.
void PushFront(int data)
{
//data를 보관하는 노드를 생성하세요.
Node *node = new Node(data);
if(head==0)//비어있을 때
{
//비어있을 때 head와 tail은 새로 생성한 노드의 위치 정보로 설정하세요.
head = tail = node;
}
이미 자료가 있을 때 맨 앞에 보관하려면 새로운 노드의 next와 head를 변경해 주어야 합니다.
else
{
//맨 앞에 보관할 때는 새로운 노드의 next는 현재 맨 앞의 노드 정보로 설정해야겠죠.
node->next = head;
//그리고 새로 생성한 노드가 연결리스트의 맨 앞 노드입니다.
head = node;
}
}
특정 노드 뒤에 자료를 보관하는 기능을 구현합시다. 사용하는 개발자는 반복자를 이용하여 원하는 위치를 찾은 후에 반복자와 보관할 자료를 전달합니다.
void InsertNext(Iterator iter,int data)
{
//노드를 생성하세요.
Node *node = new Node(data);
//전달받은 반복자가 가리키는 노드를 구합니다.
Node *prev = iter.node;
//이전 노드가 없을 때와 없을 때 구현 동작이 다릅니다.
if(prev==0)//이전 노드가 없을 때
{
if(head)//연결리스트에 보관한 자료가 있을 때
{
//연결리스트에 보관한 자료가 있을 때는
//이전 노드의 next와 head를 변경해 주어야 합니다.
//이 부분은 맨 앞에 노드를 보관할 때의 동작과 같습니다.
prev->next = head;
head = prev;
}
else//연결리스트에 보관한 자료가 없을 때
{
//연결리스트에 보관한 자료가 없을 때는
//새로운 노드가 맨 앞이면서 맨 뒤 노드죠.
head = tail = node;
}
}
이전 노드가 있을 때 새로운 노드의 next와 이전 노드의 next를 변경해 주어야 합니다.
else//이전 노드가 있을 때
{
node->next = prev->next;
prev->next = node;
if(prev == tail)//이전 노드가 tail일 때
{
//이전 노드가 tail이면
//새로운 노드가 맨 뒤에 노드로 변경해 주어야겠죠.
tail = node;
}
}
}
탐색에 사용할 반복자를 구하는 기능을 제공해야 합니다. 탐색을 시작하는 반복자와 탐색을 끝낼 조건의 반복자를 제공하세요.
Iterator Begin()//탐색에 사용할 시작 반복자
{
//탐색을 시작하는 반복자는 head를 인자로 생성하여 반환하세요.
Iterator iter(head);
return iter;
}
Iterator End() //탐색에 사용할 마지막 반복자
{
//탐색을 끝낼 조건은 0입니다.
//마지막 자료까지 탐색하므로
//tail의 다음인 0을 종료 조건의 반복자입니다.
Iterator iter(0);
return iter;
}
자료를 삭제하는 Erase 메서드를 구현합시다. 노드를 삭제하려면 이전 노드의 링크를 변경해야죠.
bool Erase(int data)
{
Node *prev=0;
Node *seek=0;
for(seek = head; seek !=0 ; seek = seek->next)
{
//만약 삭제할 데이터가 있는 노드를 찾았으면 반복문을 탈출하세요.
if(seek->data == data)
{
break;
}
//탐색할 노드의 위치를 이동하기 전에
//이전 노드를 기억할 변수에 대입하세요.
prev = seek;
}
만약 원하는 자료가 없다면 seek는 0이므로 메서드를 반환합니다.
if(seek==0)
{
return false;
}
이전 노드가 있다면 이전 노드의 next 링크를 seek의 next로 설정합니다.
if(prev)
{
prev->next = seek->next;
}
prev가 0이라는 것은 seek가 head라는 것입니다. 따라서 head를 seek의 다음 노드를 가리키게 설정하세요.
else
{
head = seek->next;
}
만약 삭제할 노드가 맨 마지막 노드일 때는 tail을 이전 노드를 가리키게 설정해야겠죠. prev의 next 링크를 설정하는 것은 if(prev) 조건문에서 수행하였기 때문에 여기에서는 tail 만 변경하세요.
if(seek == tail)
{
tail = prev;
}
seek를 소멸하세요.
delete seek;
return true;
}
존재하는지 확인하는 메서드는 삭제할 때 삭제할 노드를 찾는 부분과 흡사합니다.
bool Exist(int data)
{
Node *seek=0;
for(seek = head; seek !=0 ; seek = seek->next)
{
if(seek->data == data)
{
return true;
}
}
return false;
}
전체 보기 기능도 head가 가리키는 노드부터 순차적으로 방문하여 출력합니다.
void ViewAll()const
{
Node *seek=0;
for(seek = head; seek !=0 ; seek = seek->next)
{
cout<<seek->data<<" ";
}
cout<<endl;
}
};
사용하기 편하게 타입 재지정할게요.
typedef class SimpleLinkedList SList;
간단하게 정상적으로 동작하는지 테스트 하세요.
int main()
{
SList sl;
//순차 보관하는 부분도 있어야겠죠.
sl.PushBack(3);//3
sl.PushBack(5);//3 5
sl.PushBack(8);//3 5 8
sl.PushBack(2);//3 5 8 2
sl.PushBack(9);//3 5 8 2 9
sl.PushBack(7);//3 5 8 2 9 7
//맨 앞에 보관하는 부분도 작성하세요.
sl.PushFront(1);//1 3 5 8 2 9 7
//현재 상태를 출력합시다.
sl.ViewAll();
//자료를 삭제하는 부분도 작성하세요.
sl.Erase(8);//1 3 5 2 9 7
//현재 상태를 출력합시다.
sl.ViewAll();
//원하는 위치 뒤에 보관하는 부분도 작성합시다.
//원하는 위치는 반복자를 이용합니다.
//탐색 시작 위치를 갖는 반복자를 구하세요.
SList::Iterator seek = sl.Begin();
//탐색 종료 조건의 반복자도 구하세요.
SList::Iterator last = sl.End();
//순차적으로 반복자를 이동하면서 원하는 조건의 위치를 찾습니다.
for( ;seek != last; seek.MoveNext())
{
if(seek.GetData()==5)
{
//원하는 조건을 만족하면 반복문을 탈출하세요.
break;
}
}
//원하는 위치 뒤에 자료를 보관하는 부분도 작성하세요.
sl.InsertNext(seek,6);//1 3 5 6 2 9 7
//현재 상태를 출력하세요.
sl.ViewAll();
return 0;
}
▷ 실행 결과
1 3 5 8 2 9 7 1 3 5 2 9 7 1 3 5 6 2 9 7