3.2.2 이중 연결리스트 만들기 [디딤돌 자료구조와 알고리즘 with C++]

3.2.2 이중 연결리스트 만들기

이번에는 노드에 링크가 두 개 있는 이중 연결리스트를 만듭시다. 그리고 연결리스트의 head와 tail이 가리키는 노드를 초기에 만들기로 할게요.

 

링크가 두 개 있으면 이전 노드의 위치 정보를 갖고 있으므로 삭제나 추가할 때 이전 노드의 위치를 기억하는 변수를 별도로 선언할 필요가 없습니다.

 

그리고 연결리스트 초기화 과정에서 head와 tail이 가리키는 각 노드를 초기에 만들면 자료를 보관하는 노드를 맨 앞이나 맨 뒤에 보관하지 않아 연산을 단순하게 표현할 수 있습니다. 이 부분은 실제 구현하면서 설명하기로 할게요.

 

참고로 자료를 보관할 목적이 아닌 연결리스트를 운영하기 쉽게 생성한 노드를 더미 노드(Dummy Node)라 부릅니다. 여기서 만들 이중 연결리스트는 head와 tail이 더미 노드를 가리키게 할 거예요.

 

제공할 기능은 생성자, 해제화, 맨 뒤에 보관, 맨 앞에 보관, 원하는 위치에 보관, 탐색 가능한 반복자 제공, 데이터 제거, 데이터 보관 유무 확인, 전체 보기 기능입니다.

 

이제 연결리스트를 구현합시다. 클래스 이름은 DoubledLinkedList로 정하기로 해요.

class DoubledLinkedList

{

먼저 노드를 정의합시다. 이번에는 노드에 링크가 두 개 있어야겠죠.

 

    struct Node

    {

        int data;

        Node *prev;

        Node *next;

        Node(int data=0)

        {

입력 인자로 받은 data를 노드의 멤버 필드 data에 설정하고 두 개의 링크는 0으로 설정하세요.

            this->data = data;

            prev = next = 0;

        }

    };

맨 앞의 노드의 위치와 맨 뒤의 노드의 위치를 기억할 멤버 필드를 선언하세요.

    Node *head;

    Node *tail;

public:

연결리스트에 보관한 데이터를 탐색하기 위한 반복자를 제공합시다. 클래스 이름은 Iterator로 할게요.

    class Iterator//연결 리스트에 보관한 데이터를 탐색하기 위한 반복자

    {

연결리스트를 탐색할 때 현재 노드의 위치 정보를 멤버 필드로 기억하고 있어야 합니다.

        Node *node;//현재 노드의 위치 정보

    public:

연결리스트에서는 모든 멤버에 접근할 수 있게 friend로 지정하세요.

        friend class DoubledLinkedList;//연결리스트에서는 모든 멤버에 접근 권한 부여

생성자에서는 현재 노드의 위치 정보를 입력 인자로 받아 멤버 필드를 설정합니다.

        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;

        }

    };

 

생성자를 구현합시다.

    DoubledLinkedList()

    {

생성자에서는 더미 노드를 생성하여 head와 tail에 설정하고 링크를 조절합니다.

 

        head = new Node();//더미 노드 생성

        tail = new Node();//더미 노드 생성

        head->next = tail;

        tail->prev = head;

    }

 

소멸자를 구현합시다.

    ~DoubledLinkedList()

    {

연결리스트를 소멸할 때 모든 노드를 함께 소멸하는 것은 단순 연결리스트와 다르지 않습니다.

        Node *prev=0;

head가 존재하면 소멸하는 것을 반복합니다.

        while(head !=0)

        {

head의 이전 노드를 기억한 후에 head를 다음 노드를 가리키게 설정합니다.

            prev = head;

            head = head->next;

기억한 이전 노드를 소멸합니다.

            delete prev;

        }

    }

 

순차 보관하는 PushBack 메서드를 구현합시다.

    void PushBack(int data)

    {

보관할 data를 입력 인자로 노드를 생성하세요.

        Node *node = new Node(data);

순차 보관은 tail 앞에 새로운 노드를 연결해야겠죠. 연결하는 메서드는 별도로 정의하기로 해요. 더미있는 이중 연결리스트에서는 언제나 head와 tail은 더미 노드를 가리키고 있습니다. 따라서 새로 추가하는 노드는 연렬리스트 중간에 보관하는 것을 보장해요.

 

여기에서는 순차 보관, 맨 앞 보관, 특정 위치 앞에 보관하는 기능을 제공할 것이며 새로 생성한 노드를 연결하는 논리는 같아서 별도의 메서드로 정의하는 것입니다.

        HangNode(node,tail);

    }

맨 앞에 보관하는 PushFront 메서드를 구현합시다.

    void PushFront(int data)

    {

보관할 data를 입력 인자로 노드를 생성하세요.

        Node *node = new Node(data);

생성한 노드는 맨 앞 더미 노드 뒤에 보관하면 자료를 보관하는 노드 중에는 맨 앞이 되겠죠.

        HangNode(node,head->next);

HangNode는 맨 마지막에 작성할게요.

    }

 

특정 노드 앞에 보관하는 Insert 메서드를 구현합시다.

    void Insert(Iterator iter,int data)

    {

보관할 data를 입력 인자로 노드를 생성하세요.

        Node *node = new Node(data);

생성한 노드를 입력 인자로 받은 반복자의 node 앞에 연결하면 되겠죠.

        HangNode(node,iter.node);

    }

 

탐색에 사용할 반복자를 구하는 기능을 제공해야 합니다. 탐색을 시작하는 반복자와 탐색을 끝낼 조건의 반복자를 제공하세요.

    Iterator Begin()//탐색에 사용할 시작 반복자

    {

탐색을 시작할 노드는 head의 다음 노드부터입니다. head가 가리키는 노드는 더미 노드임을 주의하세요.

        Iterator iter(head->next);

        return iter;

    }

 

탐색에 사용할 마지막 반복자를 구하는 기능을 제공합시다.

    Iterator End() //탐색에 사용할 마지막 반복자

    {

탐색에 사용할 마지막 반복자는 tail입니다. tail이 가리키는 노드가 더미 노드임을 주의하세요. 여기에서 End는 탐색하는 로직에서 반복문을 탈출할 조건에 사용할 것이므로 실제 자료를 보관하는 마지막 노드의 다음 위치를 의미합니다.

        Iterator iter(tail);

        return iter;

    }

 

 

보관한 자료를 찾아 노드를 제거하는 Erase 메서드를 구현합시다.

    bool Erase(int data)

    {

이중 연결리스트이므로 이전 노드를 기억하는 변수를 선언할 필요가 없어요.

        Node *pos=0;

head는 더미 노드를 가리키므로 검색할 노드는 head의 다음 노드부터입니다. 그리고 탐색할 링크가 맨 뒤 노드를 가리키는 tail과 같으면 검색할 자료가 없는 것이죠.

        for(pos = head->next; pos !=tail ; pos = pos->next)

        {

만약 같은 자료가 있으면 반복문을 탈출합니다.

            if(pos->data == data)

            {

                break;

            }

        }

만약 검색하지 못하였으면 pos는 tail과 같습니다.

        if(pos==tail)

        {

            return false;

        }       

이 곳에 도달하였다면 pos가 tail이 아니므로 삭제할 노드를 탐색하였을 때입니다.

 

삭제할 노드의 앞쪽 노드의 next 링크를 삭제할 노드의 다음 노드를 가리키게 설정합니다.

        pos->prev->next = pos->next;

삭제할 다음 노드의 prev 링크를 삭제할 노드의 이전 노드를 가리키게 설정합니다.

        pos->next->prev = pos->prev;

노드를 소멸합니다.

        delete pos;

        return true;

    }

 

    bool Exist(int data)

    {

존재하는지 확인하는 기능에서도 head의 다음 노드부터 tail 이전까지 확인하세요.

        Node *seek=0;

        for(seek = head->next; seek !=tail ; seek = seek->next)

        {

만약 원하는 조건의 데이터가 있으면 참을 반환하세요.

            if(seek->data == data)

            {

                return true;

            }

        }

여기에 도달했다는 것은 원하는 조건의 데이터가 없는 것이므로 거짓을 반환하세요.

        return false;

    }

 

전체 자료를 출력하는 메서드를 구현합시다.

    void ViewAll()const

    {       

        Node *seek=0;

전체 정보를 출력하는 기능에서도 head의 다음 노드부터 tail 이전까지 출력하세요. head와 tail이 가리키는 노드는 더미 노드임을 주의하세요.

        for(seek = head->next; seek !=tail ; seek = seek->next)

        {

            cout<<seek->data<<" ";

        }

        cout<<endl;

    } 

 

    private:

특정 노드 앞에 노드를 연결하는 메서드를 구현합시다.

    void HangNode(Node *now,Node *pos)

    {

 

새로운 노드의 prev는 pos 이전 노드 위치로 설정합니다.

        now->prev = pos->prev;

새로운 노드의 next는 pos로 설정하세요.

        now->next = pos;

새로운 노드는 pos 이전 노드의 뒤에 보관할 거죠. pos의 이전 노드의 next를 새로운 노드로 설정하세요.

        pos->prev->next = now;

새로운 노드는 pos 앞에 보관할 거예요.

        pos->pres = now;

    }

};

 

사용하기 편하게 타입 재지정하세요.

typedef class DoubledLinkedList DList;

int main()

{

테스트 코드를 작성하고 테스트 해 보세요.

    DList dl;

    dl.PushBack(3);//3

    dl.PushBack(5);//3 5

    dl.PushBack(8);//3 5 8

    dl.PushBack(2);//3 5 8 2

    dl.PushBack(9);//3 5 8 2 9

    dl.PushBack(7);//3 5 8 2 9 7

    dl.PushFront(1);//1 3 5 8 2 9 7

    dl.ViewAll();

    dl.Erase(8);//1 3 5 2 9 7

    dl.ViewAll();

 

    DList::Iterator seek = dl.Begin();

    DList::Iterator last = dl.End();

    for(   ;seek != last; seek.MoveNext())

    {

        if(seek.GetData()==5)

        {

            break;

        }

    }

 

    dl.Insert(seek,6);//1 3 6 5 2 9 7

    dl.ViewAll();

    return 0;

}

 

▷ 실행 결과

1 3 5 8 2 9 7

1 3 5 2 9 7

1 3 6 5 2 9 7

 

 

다음은 더미 있는 이중 연결리스트의 개념을 잡기위해 앞에서 작성한 코드입니다.

 

//이중 연결리스트

#include <iostream>

using namespace std;

 

class DoubledLinkedList

{

    struct Node

    {

        int data;

        Node *prev;

        Node *next;

 

        Node(int data=0)

        {

            this->data = data;

            prev = next = 0;

        }

    };

 

    Node *head;

    Node *tail;

public:

     class Iterator//연결 리스트에 보관한 데이터를 탐색하기 위한 반복자

    {

        Node *node;//현재 노드의 위치 정보

 

    public:

        friend class DoubledLinkedList;//연결리스트에서는 모든 멤버에 접근 권한 부여

 

        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;

        }

    };

 

    DoubledLinkedList()

    {

        head = new Node();//더미 노드 생성

        tail = new Node();//더미 노드 생성

        head->next = tail;

        tail->prev = head;

    }

 

    ~DoubledLinkedList()

    {

        Node *prev=0;       

        while(head !=0)

        {           

            prev = head;

            head = head->next;

            delete prev;

        }

    }

    void PushBack(int data)

    {

        Node *node = new Node(data);

       

        HangNode(node,tail);

    }

    void PushFront(int data)

    {

        Node *node = new Node(data);

        HangNode(node,head->next);

    }

    void Insert(Iterator iter,int data)

    {

        Node *node = new Node(data);

        HangNode(node,iter.node);

    }

 

    Iterator Begin()//탐색에 사용할 시작 반복자

    {

        Iterator iter(head->next);

        return iter;

    }

    Iterator End() //탐색에 사용할 마지막 반복자

    {

        Iterator iter(tail);

        return iter;

    }

    bool Erase(int data)

    {               

        Node *pos=0;

        for(pos = head->next; pos !=tail ; pos = pos->next)

        {

            if(pos->data == data)

            {

                break;

            }           

        }

 

        if(pos==tail)

        {

            return false;

        }       

 

        pos->prev->next = pos->next;

        pos->next->prev = pos->prev;

       

        delete pos;

        return true;

    }

    bool Exist(int data)

    {       

        Node *seek=0;

        for(seek = head->next; seek !=tail ; seek = seek->next)

        {

            if(seek->data == data)

            {

                return true;

            }

        }

        return false;

    }

 

    void ViewAll()const

    {       

        Node *seek=0;

        for(seek = head->next; seek !=tail ; seek = seek->next)

        {

            cout<<seek->data<<" ";

        }

        cout<<endl;

    }

 

    private:

    void HangNode(Node *now,Node *pos)

    {

        now->prev = pos->prev;

        now->next = pos;

        pos->prev->next = now;

        pos->prev = now;

    }

};

 

typedef class DoubledLinkedList DList;

int main()

{

    DList dl;

    dl.PushBack(3);//3

    dl.PushBack(5);//3 5

    dl.PushBack(8);//3 5 8

    dl.PushBack(2);//3 5 8 2

    dl.PushBack(9);//3 5 8 2 9

    dl.PushBack(7);//3 5 8 2 9 7

    dl.PushFront(1);//1 3 5 8 2 9 7

    dl.ViewAll();

    dl.Erase(8);//1 3 5 2 9 7

    dl.ViewAll();

 

    DList::Iterator seek = dl.Begin();

    DList::Iterator last = dl.End();

    for(   ;seek != last; seek.MoveNext())

    {

        if(seek.GetData()==5)

        {

            break;

        }

    }

 

    dl.Insert(seek,6);//1 3 6 5 2 9 7

    dl.ViewAll();

    return 0;

}

 

▷ 실행 결과

1 3 5 8 2 9 7

1 3 5 2 9 7

1 3 6 5 2 9 7