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;   //연결리스트 맨 뒤 노드의 위치 정보

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

public:
    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;
        }

보관한 자료가 있을 때는 tail의 next 링크를 새로운 노드를 가리키게 하고 tail을 새로운 노드로 설정합니다.

보관한 자료가 있을 때 연결리스트에 노드 매달기
        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;
        }
맨 앞에 노드 매달기

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

        else
        { 
            //맨 앞에 보관할 때는 새로운 노드의 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;
            }            
        }
특정 노드 뒤에 매달기

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

        else//이전 노드가 있을 때
        { 
            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;
        }

이전 노드가 있다면 이전 노드의 next 링크를 seek의 next로 설정합니다.

노드 삭제
        if(prev)
        { 
            prev->next = seek->next;
        }

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

노드 삭제
        else
        { 
            head = seek->next;
        }
노드 삭제

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

        if(seek == 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