C/c++ 단순 연결 리스트 C++ 클래스 화

개요

전 글에서 공부한 단순 연결 리스트의 구성과 함수를 C++의 클래스로 바꿔 작성해 보았다. 전 글과 함수의 구현 로직은 같기에 코드와 실행 결과만 첨부하고자 한다.

클래스가 되며 바뀐 점

사실 Node에 대한 것은 structure을 사용하나 class를 사용하나 별 차이가 없다. LinkedList에 대해 살펴볼 점은 first의 위치이다. 기존 structure을 사용할 때는 모든 함수에 기본적으로 인자로 first를 줘서 어떤 연결 리스트의 시작점을 기준으로 하는지 필요했다. 하지만, 클래스가 되면서 연결 리스트를 객체로 생성하면, 해당 객체는 첫 시작의 주소를 알고 있으며 멤버 함수는 당연히 해당 객체의 연결 리스트에 대한 함수이기에 굳이 인자로 줄 필요가 없었다. 또한, 생성자에 create함수의 로직을 사용했다는 점에서 차이가 있다.

작성한 코드

#include <iostream>

using namespace std;

class Node
{
    public:
        int data;
        Node* next;
};

class LinkedList
{
private:
    Node* first;

public:
    LinkedList()
    {
        Node* first = NULL;
    };

    LinkedList(int A[], int n);
    ~LinkedList();

    int Count();
    void Display();
    Node* Search(int key);
    void Insert(int x, int index);
    int Delete(int index);
    void Reverse();
    int isLoop();
};

LinkedList::LinkedList(int A[], int n)
{
    Node* t;
    Node* last;
    first = new Node;
    first->data = A[0];
    first->next = NULL;
    last = first;

    for (int i = 1; i < n; i++)
    {
        t = new Node;
        t->data = A[i];
        t->next = NULL;
        last->next = t;
        last = t; 
    }
}

LinkedList::~LinkedList()
{
    Node* p = first;
    Node* t = NULL;

    while(p)
    {
        if(p)
        {
            t = p;
            p = p->next;
            delete t;
        }
    }
}

int LinkedList::Count()
{
    Node* p = first;
    int count = 0;

    while(p)
    {
        if (p)
            count++;

        p = p->next;
    }

    return count;
}

void LinkedList::Display()
{
    Node* t = first;

    while(t)
    {
        cout << t->data << " ";
        t = t->next;
    }
    cout << endl;
}

int LinkedList::Delete(int index)
{
    Node* p;
    Node* q;
    int x;

    if (index < 1 || index > Count())
        return -1;

    if (index == 1)
    {
        p = first;
        x = p->data;
        first = p->next;
        delete p;
        return x;
    }
    else
    {
        p = first;

        for (int i = 0; i < index - 1 && p; i++)
        {
            q = p;
            p = p->next;
        }

        q->next = p->next;
        x = p->data;
        delete p;
        return x;


    }
}

void LinkedList::Insert(int index, int x)
{
    Node* t = new Node;
    t->data = x;
    t->next = NULL;

    Node* p = first;
    Node* q;

    if (!p)
    {
        first = t;
    }
    else
    {
        if (index == 0)
        {
            t->next = first;
            first = t;
        }

        for (int i = 0; i < index - 1; i++)
        {
            p = p->next;        
        }
        t->next = p->next;
        p->next = t;
    }
}

void LinkedList::Reverse()
{
    Node* p = first, *q = NULL, *r = NULL;

    while(p)
    {
        r = q;
        q = p;
        p = p->next;

        r = q->next;
    }
    first = q;
}

Node* LinkedList::Search(int key)
{
    Node* q = NULL, *p = first;

    while(p)
    {
        if (p->data == key)
            return p;

        if (key == p->data)
        {
            q->next = p->next;
            p->next = first;
            first = p;
            return p;
        }
        q = p;
        p = p->next;
    }
    return NULL;
}

int LinkedList::isLoop()
{
    Node* p = first, *q = first;


    do {
        p = p->next;
        q = q->next;

        q = q ? q->next : q;
    } while(p && q && p != q);

    if (p == q)
        return 1;
    else
        return 0;
}

main함수에서의 객체 생성 후, 실행 결과

int main()
{
    int A[]={1,6,8,12,56};
    LinkedList l(A,5);

    l.Insert(2,67);

     l.Display();

    cout<<"lenght "<<l.Count()<<endl;


    l.Delete(1);
    cout<<"After deletion"<<endl;
    l.Display();
    return  0;
}

실행 결과

1 6 67 8 12 56

lenght 6

After deletion

6 67 8 12 56

올바른 결과가 나옴을 알 수 있다.