이제 STL의 list를 모델로 정의한 list를 구현합시다. 설명은 주석으로 해 놓았어요.
#pragma once
namespace ehlib
{
template<typename Data>
class list
{
//리스트 내부에 노드를 정의합시다.
//여기에서는 링크가 두 개 있는 노드를 정의할게요.
struct node
{
Data data;
node *prev;
node *next;
node(Data data=0)
{
this->data = data;
prev = next = 0;
}
};
//리스트에는 맨 앞 노드와 맨 뒤 노드를 기억하는
//head와 tail 멤버를 선언하세요.
node *head;
node *tail;
//보관한 데이터 개수를 기억하는 멤버도 선언하세요.
int count;
public:
class iterator
{
//반복자는 보관한 자료의 위치를 기억하고 있어야 합니다.
//리스트에는 자료를 노드에 보관하므로 노드의 위치를 멤버로 선언하세요.
node *now;
public:
//생성자는 기본 생성이 가능하게 디폴트 인자를 사용하세요.
iterator(node *now=0)
{
this->now = now;
}
//간접 연산으로 보관한 자료를 반환하게 구현하세요.
Data operator *()const
{
return now->data;
}
//리스트 내부에서는 반복자 내부
//노드의 위치 정보를 알 수 있어야 합니다.
//여기에서는 묵시적 형 변환 연산을 정의할게요.
operator node *()
{
return now;
}
//증가 연산자에서는 now를 다음 위치로 이동하세요.
iterator &operator++()
{
now = now->next;
return (*this);
}
//나머지 증가 연산자도 now를 다음 위치로 이동하세요.
const iterator operator++(int)
{
iterator re(*this);
now = now->next;
return re;
}
bool operator !=(const iterator &iter)const
{
return now != iter.now;
}
bool operator ==(const iterator &iter)const
{
return now == iter.now;
}
};
typedef iterator const_iterator;
//생성자를 정의합시다.
list()
{
//생성자에서는 head와 tail에 더미 노드를 생성하고 링크를 조절하세요.
//여기에서 작성하는 이중 연결리스트는 3.2.2에서 작성했던
//더미있는 이중 연결리스트입니다.
head = new node();
tail = new node();
head->next = tail;
tail->prev = head;
//보관한 자료의 개수를 0으로 설정하세요.
count = 0;
}
//소멸자를 정의합시다.
~list()
{
//맨 앞의 노드부터 순차적으로 소멸하세요.
node *prev=0;
//head가 존재하면 반복하세요.
while(head !=0)
{
//head를 이동하기 전에 prev에 기억하세요.
prev = head;
head = head->next;
//기억해 두었던 prev의 노드를 소멸하세요.
delete prev;
}
}
//순차적으로 보관하는 push_back 메서드를 구현합시다.
void push_back(Data data)
{
//순차 보관하는 push_back에서는
//insert 메서드를 이용하여 맨 끝에 보관합니다.
insert(end(),data);
}
//특정 위치 앞에 보관하는 insert 메서드를 구현합시다.
void insert(iterator at, Data data)
{
//자료를 보관할 노드를 생성하세요.
node *now = new node(data);
//반복자 형식에는 node * 형식으로 묵시적 형 변환을 정의하였습니다. node * 형식으로 얻어오세요.
node *pos = at;
//now 노드를 pos 앞에 매달기 위해 링크를 조절하세요.
//자세한 내용은 3.2.2를 참고하세요.
now->next = pos;
now->prev = pos->prev;
pos->prev->next = now;
pos->prev = now;
//보관한 자료 개수를 1 증가하세요.
count++;
}
//특정 위치의 자료를 제거하는 erase 메서드를 구현합시다.
void erase(iterator at)
{
node *now = at;
//삭제할 노드의 링크를 끊어야겠죠.
now->prev->next = now->next;
now->next->prev = now->prev;
//자료를 보관한 노드를 소멸하고 보관한 자료 개수를 1 감소하세요.
delete now;
count--;
}
iterator begin()
{
//head는 더미 노드를 가리키므로
//head의 next가 자료를 보관하고 있는 첫 번째 노드입니다.
iterator iter(head->next);
return iter;
}
iterator end()
{
//end는 맨 마지막 자료를 보관한 다음 위치를 의미하죠.
//tail이 가리키는 노드는 맨 마지막 자료를 보관한 다음 위치입니다.
iterator iter(tail);
return iter;
}
const_iterator begin()const
{
iterator iter(head->next);
return iter;
}
const_iterator end()const
{
iterator iter(tail);
return iter;
}
size_t size()
{
//보관한 자료 개수를 반환하세요.
return count;
}
};
}