컴공 일기63

양방향 연결리스트, Double Linked List를 구현한 예제입니다.

저번에 insert 함수에서 segementation 관련 오류가 떠서 꽤나 한동안

만지작 거리고 있던 코드였는데, 어느 부분에서 문제가 생겼는지 이제 좀 확실해 져서 다시 올려봅니다. 

이게 시각적으로 보면 사실... 말도 많고 어려워 보이지만, 정말 이 그림을 그냥 코드로 만들어 놓은 것 뿐이랍니다. 컴퓨터공학이라는 분야에서 주로 다루곤 하는 코딩이라는 게, 처음 배울 때는 꽤 어렵게 다가오지만 원리를 알면 익숙해집니다. (물론, 그 과정에서 수만가지 ERROR CODE를 목도하게 되겠지만...) 

제가 생각하기에 코딩 실력을 향상할 때 가장 중요한 것은, 자신감이라고 생각해요.

지금 당장 이해가 안 되더라도, 내가 A난도 수준의 코드를 계속 공부하고 이해하려고 시도하면

어느 순간 나도 모르게 A난도 수준의 엔지니어가 됩니다. 말하자면, 계속 특정 어려운 코드를 보고

그것을 내 것으로 만들면 되는 겁니다. 근데, A난도가 아직 나에겐 벅차니까 쉬운 것만 보고 실습하면

절대로 A난도에 갈 수가 없지요. 

저는 그래서, 예제 학습을 할 때 100라인 이상 정도 되는 코드들을 짜려고 하지요.

그 정도 라인을 넘겨서 긴 호흡으로, 가독성을 지켜가면서 짤려고 노력해야, 그 수준에

제가 위치하게 될 테니 말입니다. 하여간, 말이 좀 길었고... 

우리가 일상 생활을 살다 보면, 여러가지 자료를 얻게될 때가 있어요.

하물며 개발을 하는 사람들 입장에선, 매일 매일을 데이터 속에서 살겠죠.

그렇다면, 우리가 고민해보아야 하는 건, "정리"일 것 같습니다.

다시 말해서, 이 데이터들을 어떻게 구조화시키고 정리할 것이냐가 꽤 중요한 논의가 된다는 것이죠.

그런 논의를 다뤄놓은 분야가 "자료구조"라는 분야랍니다. 말 그대로, 자료를 어떤 구조로 관리할 지를 고민하는 분야입니다. 양방향 연결 리스트라는 것도 결국 이 자료구조의 일종에 다름이 아니에요. 

말하자면, 여러 데이터들을 묶을 때, 서로가 "상호 참조" 되도록 한 것입니다. 

1번 학생의 성적, 2번 학생의 성적, 3번 학생의 성적 데이터가 있다고 할까요?

그렇다면, 양방향 연결리스트 구조는 이 세 가지의 데이터들을 정방향으로, 역방향으로 동시에 묶은 구조입니다.

이렇게 묶어 놓는다면 우리가 반 전체 성적표를 만들 때, 아주 편하게 만들어 볼 수 있죠.

1번 데이터 다음 2번, 2번 데이터 다음, 3번... 이런 식으로 순차적으로 데이터를 뽑아내기만 하면 되니까요.

또, 역순으로도 성적표를 뽑아낼 수도 있습니다. 3번 데이터가 2번을 가리키고, 2번 데이터가 1번을 가리키고 있으니까요. 양방향 연결 리스트는 이렇듯이 데이터를 정방향으로, 역방향으로 모두 출력될 수 있게 도와주는 구조인 것입니다.

제가 표현한 다음의 코드가 결국 이런 식으로 데이터를 관리한 것이랍니다.

#include <iostream>

using namespace std;

class CShape {

protected:

    int x, y;

public:

    CShape(int a, int b) : x(a), y(b) {}

  //순수가상함수 : 추상 클래스 구조로 설계

    virtual void Print() = 0;

};

template <typename T>

class CCircle : public CShape {

private:

    T Radius;

public:

    CCircle(int a, int b, T r) : CShape(a, b), Radius(r) {}

    double GetArea() { return 3.14 * Radius * Radius; }

    //가상화 

    void Print() { cout << this->GetArea() << endl; }

    template <typename U>

    friend ostream& operator << (ostream& out, CCircle<U>& rhs);

};

template <typename U>

ostream& operator << (ostream& out, CCircle<U>& rhs) {

    cout << rhs.GetArea() << endl;

    return out;

}

template <typename T>

struct Node {

    T data;

    Node<T>* next;

    Node<T>* prev;

    Node(T d, Node<T>* n = NULL) : data(d), next(NULL), prev(NULL) { }

};

template <typename T>

class ListIterator {

private:

    Node<T>* ptr;

public:

    ListIterator(Node<T>* p = 0) : ptr(p) {}

    void operator++ (int) { ptr = ptr->next; }

    void operator-- (int) { ptr = ptr->prev; }

    Node<T>* operator&() {

        return ptr;

    }

    T& operator* () { return ptr->data; }

    ListIterator<T> operator+ (int adv)

    {

        return ptr;

    }

    void operator=(Node<T>* p)

    {

        ptr = p;

    }

};

template <typename T>

class MyList {

private:

    Node<T>* start;

    Node<T>* last;

public:

    MyList() : start(NULL), last(NULL) {}

    typedef ListIterator<T> iterator;

    Node<T>* begin() { return start; }

    Node<T>* rbegin() { return last; }

    void push(T d) {

        Node<T>* temp = new Node<T>(d, NULL);

        if (start == NULL) {

            start = last = temp;

        }

        else

        {

            temp->prev = last;

            last->next = temp;

            last = temp;

        }

    }

    void insert(iterator iter, T d) {

        Node<T>* now = &iter;

        Node<T>* newnode = new Node<T>(d, NULL);

        newnode->next = now->next;

        newnode->prev = now;

        now->next = newnode;

        newnode->next->prev = newnode;

    }

};

int main()

{

    int i;

    MyList<CCircle<double> > intL;

    MyList<CCircle<double> >::iterator lIter;

    for (i = 0; i < 5; i++)

    {

        intL.push(CCircle<double>(1, 1, i + 1.1));

    }

    lIter = intL.begin();

    intL.insert(lIter, CCircle<double>(1, 1, 1.1));

   //정방향 데이터 출력

    for (i = 0; i < 6; i++) {

        cout << *lIter;

        lIter++;

    }

    lIter = intL.rbegin();

   //역방향 데이터 출력 

    for (i = 0; i < 6; i++) {

        cout << *lIter;

        lIter--;

    }

    return 0;

}