본 포스팅은 [Data Structure & Algorithm in C++ -Goodrich]의 내용을 많이 참조하여 작성되었습니다.
C++로 List의 ADT(Abstract Data Type)을 구현하는 방법은 여러가지 이다.
더블 링크드 리스트
// Doubly_linked_list.cpp : This file contains the 'main' function. Program execution begins and ends there.
//
#include <iostream>
using namespace std;
typedef int Elem;
class NodeList {
private:
struct Node {
Elem elem;
Node* prev;
Node* next;
};
public:
class Iterator { //리스트를 위한 반복자
public:
Elem& operator*() { return v->elem; }; //원소의 참조자
bool operator ==(const Iterator& p) const { return v == p.v; }; //위치 비교
bool operator !=(const Iterator& p) const { return v != p.v; };
Iterator& operator++() { v = v->next; return *this; };//다음 원소
Iterator& operator--() { v = v->prev; return *this; };//이전 원소
friend class NodeList;//노드 리스트에게 접근권을 줌
private:
Node* v;// 현재 가리키고 있는 노드
Iterator(Node* u) { v = u; }; // 노드로 부터 반복자를 생성
};
public:
NodeList() {//default 생성자
n = 0;
header = new Node;
trailer = new Node;
header->next = trailer;
trailer->prev = header;
};
int size() const { return n; };
bool empty() const { return n == 0; };
Iterator begin() { return Iterator(header->next); };
Iterator end() const { return Iterator(trailer); };
void insert(const Iterator& p, const int& e) {
Node* w = p.v; //p's node
Node* u = w->prev;
Node* v = new Node;
v->elem = e;
v->next = w; w->prev = v;
v->prev = u; u->next = v;
n++;
};
void insertFront(const Elem& e) { insert(begin(), e); };
void insertBack(const Elem& e) { insert(end(), e); };
void erase(const Iterator& p) {
Node* v = p.v;
Node* w = v->next;
Node* u = v->prev;
u->next = w; w->prev = u;
delete v;
n--;
};
void eraseFront() { erase(begin()); };
void eraseBack() { erase(--end()); };
private:
int n;
Node* header;
Node* trailer;
};
int main()
{
NodeList nl;
nl.insertFront(3);
nl.insertBack(4);
nl.insertBack(5);
nl.insertBack(6);
nl.insertBack(1);
for (NodeList::Iterator it = nl.begin(); it != nl.end(); ++it) {
cout << *it << endl;
}
}
실행 결과
