언어 자료구조 알고리즘/[C++]디딤돌 자료구조와 알고리즘

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

언제나휴일 2016. 4. 4. 10:42
반응형

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

        {

prev0이라는 것은 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;

}

반응형