[ 자료구조 ] 연결 리스트 : 이중 연결 리스트

저번 글에 이어서 이중 연결 리스트와 순환 연결 리스트를 구현해보자. 저번 글과 마찬가지로 그림으로 구조를 먼저 살표보고, 어떤 기능을 구현할지 명시하고, 세부적인 기능을 구현한다. 

이중 연결 리스트

1. 구조

각 노드는 데이터와 두 개의 포인터를 가지고 있다. next 포인터는 다음 노드를, prev 포인터는 이전 노드를 가리킨다. 따라서 단일 연결 리스트와는 다르게 양방향으로 이동할 수 있는 특징이 있다. 프로그래밍을 단순화하기 위해 양 끝에 더미 노드를 추가하는 것이 좋다. header 노드는 시작점을 의미하고, trailer 노드는 끝점을 의미한다. 

 

이중 연결 리스트는 양방향으로 움직일 수 있는 장점이 있지만 그만큼 구현하기 위해 추가되는 요소들도 많다. 당장 단일 연결 리스트와 비교해봤을 때 구조적으로 많이 차이 나는 것을 알 수 있다. 이중 연결 리스트의 핵심은 데이터 삭제와 추가에 있다. 각 노드마다 포인터가 두 개가 있기 때문에 포인터의 연결 순서에 유의해야 하는데, 이에 대한 자세한 설명은 구현 파트에서 다루도록 하겠다. 곧 나온다. 

2. 클래스 정의

노드 클래스(DNode)

class DNode{
private:
    string elem; // 노드의 원소값
    DNode* prev; // 이전 노드
    DNode* next; // 다음 노드
    friend class DLinkedList;
};

 

연결 리스트 클래스 (DLinkdedList)

class DLinkedList{
public:
    DLinkedList(); // 생성자
    ~DLinkedList(); // 소멸자
    bool empty() const; // 비었는지?
    const string& front() const; // 맨 앞 노드의 값
    const string& back() const; // 맨 뒤 노드의 값
    void addFront(const string& e); // 맨 앞에 노드 추가
    void addBack(const string& e); // 맨 뒤에 노드 추가
    void removeFront(); // 맨 앞 노드 삭제
    void removeBack(); // 맨 뒤 노드 삭제
private:
    DNode* header;
    DNode* trailer;
protected:
    void add(DNode* v, const string& e); // V 앞에 노드 추가
    void remove(DNode* v); // V 노드 삭제
};

3. 구현

노드 추가 및 삭제를 제외한 간단한 멤버 함수를 먼저 구현해보자. 

// 생성자
DLinkedList::DLinkedList(){
    header = new DNode;
    trailer = new DNode;
    header->next = trailer;
    trailer->prev = header;
}

// 소멸자
DLinkedList::~DLinkedList(){
    while(!empty()) removeFront();
    delete header;
    delete trailer;
}

// 비었는지?
bool DLinkedList::empty() const
    { return (header->next == trailer); }

// 맨 앞 노드의 값
const string& DLinkedList::front() const
    { return header->next->elem; }

// 맨 뒤 노드의 값
const string& DLinkedList::back() const
    { return trailer->prev->elem; }

 

- 리스트 생성자는 header, trailer를 생성하고 서로 연결시켜주면 된다. 

- 소멸자는 먼저 header, trailer를 제외한 모든 노드를 삭제한 뒤에 header, trailer도 삭제하면 된다.

- 리스트가 비었는지는 header와 trailer가 연결되었는지로 알 수 있다.

- 맨 앞 노드의 값은 그냥 header next 노드의 값을 반환하면 된다.

- 맨 뒤 노드의 값은 그냥 trailer의 prev 노드의 값을 반환하면 된다.

 

 

1) 데이터 삽입

 

아래 그림과 같이 V, W 순서로 이어진 이중 연결 리스트가 있다고 가정해보자. 우리는 중간에 Z 노드를 추가하고 싶다. 어떻게 해야할까?

아래의 매커니즘을 그대로 따르면 된다. 

 

1.  Z->prev to V
2.  Z->next to W
3.  W->prev to Z
4.  V->next to Z

 

이해하기 쉽게 그림으로도 살펴보자. 일단 삽입하는 노드의 prev, next 링크를 연결시킨 후에 앞뒤 노드의 링크를 Z에 연결시키면 된다.

이를 그대로 코드로 구현해보자. add(v, e) 는 v라는 노드 앞에 새로운 노드를 삽입한다는 뜻이다. 

 

void DLinkedList::add(DNode* v, const string& e){
    // V 앞에 노드 추가. (v->prev  u  v) 순서
    DNode* u = new DNode;
    u->elem = e; 
    u->next = v; 
    u->prev = v->prev;
    v->prev->next = u;
    v->prev = u;
}

// 맨 앞에 노드 추가
void DLinkedList::addFront(const string& e)
    { add(header->next, e); }

// 맨 뒤에 노드 추가
void DLinkedList::addBack(const string& e)
    { add(trailer, e); }

 

 

 

2) 데이터 삭제

 

삽입과는 반대의 상황이다. 아래 그림과 같이 V, Z, W 순서로 이어진 이중 연결 리스트가 있다고 가정해보자. 우리는 중간에 Z 노드를 삭제하고 싶다. 어떻게 해야할까?

아래의 매커니즘을 그대로 따르면 된다. 

 

1.  W->prev to V
2.  V->next to W
3. delete Z

 

이해하기 쉽게 그림으로도 살펴보자. 삭제하는 노드의 앞뒤 노드를 서로 연결시켜주고 노드를 삭제하면 된다.

 

이를 그대로 코드로 구현해보자. remove(v) 는 노드 v를 삭제한다는 뜻이다.

 

void DLinkedList::remove(DNode* v){
    // (u  v  w) 에서 v 삭제
    DNode* u = v->prev;
    DNode* w = v->next;
    u->next = w;
    w->prev = u;
    delete v;
}

// 맨 앞 노드 삭제
void DLinkedList::removeFront()
    { remove(header->next); }

// 맨 뒤 노드 삭제
void DLinkedList::removeBack()
    { remove(trailer->prev); }

 

 

가장 앞, 뒤 노드만 삽입 및 삭제하는 기능만 구현해봤다. 그런데 add, remove 함수를 사용하면 어렵지 않게 원하는 위치에 노드를 삽입 및 삭제할 수 있다!

 

코드가 많아서 그런지 생각보다 글이 길어져서 순환 연결 리스트는 다음 글에 정리하도록 하겠다.