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

3.2.1 단순 연결리스트 만들기

이번에는 간단하게 단순(단일) 연결리스트를 만들어 보아요. 여기에서 만드는 단순 연결리스트는 개념을 잡기 위해 만드는 것으로 노드에 보관할 자료 형식을 정수로 한정할게요. 뒤에서 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;   //연결리스트 맨 뒤 노드의 위치 정보

public:

 

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

    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;

        }

        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;

        }

        else

        {

이미 자료가 있을 때 맨 앞에 보관하려면 새로운 노드의 next와 head를 변경해 주어야 합니다.

 

맨 앞에 보관할 때는 새로운 노드의 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;

            }           

        }

        else//이전 노드가 있을 때

        {

이전 노드가 있을 때 새로운 노드의 next와 이전 노드의 next를 변경해 주어야 합니다.

 

            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;

        }

        if(prev)

        {

 

            prev->next = seek->next;

        }

        else

        {

prev가 0이라는 것은 seek가 head라는 것입니다. 따라서 head를 seek의 다음 노드를 가리키게 설정하세요.

 

            head = seek->next;

        }

        if(seek == tail)

        {

만약 삭제할 노드가 맨 마지막 노드일 때는 tail을 이전 노드를 가리키게 설정해야겠죠. prev의 next 링크를 설정하는 것은 if(prev) 조건문에서 수행하였기 때문에 여기에서는 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

 

다음은 단순 연결리스트의 개념을 잡기위해 앞에서 작성한 코드입니다.

//단순 연결리스트

#include <iostream>

using namespace std;

class SimpleLinkedList

{

    struct Node //단순 연결리스트의 노드

    {

        int data;

        Node *next;

        Node(int data=0)

        {

            this->data = data;

            next = 0;

        }

    };

    Node *head; //연결리스트 맨 앞 노드의 위치 정보

    Node *tail;   //연결리스트 맨 뒤 노드의 위치 정보

public:

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

    {

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

    public:

        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;

        }

    };

    SimpleLinkedList()

    {

        head = 0;

        tail = 0;

    }

 

    ~SimpleLinkedList()

    {

        Node *prev=0;

        while(head !=0)

        {           

            prev = head;

            head = head->next;

            delete prev;

        }

    }

 

    void PushBack(int data)

    {

        Node *node = new Node(data);

        if(head==0)//비어있을 때

        {

            head = tail = node;

        }

        else

        {

            tail->next = node;

            tail = node;

        }

    }

    void PushFront(int data)

    {

        Node *node = new Node(data);

        if(head==0)//비어있을 때

        {

            head = tail = node;

        }

        else

        {

            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)//연결리스트에 보관한 자료가 있을 때

            {               

                prev->next = head;

                head = prev;

            }

            else//연결리스트에 보관한 자료가 없을 때

            {

                head = tail = node;

            }           

        }

        else//이전 노드가 있을 때

        {

            node->next = prev->next;

            prev->next = node;

            if(prev == tail)//이전 노드가 tail일 때

            {

                tail = node;

            }

        }

    }

 

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

    {

        Iterator iter(head);

        return iter;

    }

 

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

    {

        Iterator iter(0);

        return iter;

    }

   

    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;

        }

 

        if(seek==0)//찾는 데이터가 없을 때

        {

            return false;

        }       

        if(prev)//이전 노드가 있을 때

        {

            prev->next = seek->next;

        }

        else//이전 노드가 없을 때

        {

            head = seek->next;

        }

        if(seek == tail)//지워야 할 노드가 맨 마지막 노드일 때

        {

            tail = prev;

        }

 

        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;

    }

 

    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;

}