C++로 구현하는 자료구조!!이중연결리스트(Doubly Linked List)@@

강력한 언어, C++로 구현하는 자료구조

Implementation Doubly Linked List Using C++

  저번 시간에는 단방향 연결 리스트 즉, Singly Linked List에 대해서 글을 올렸었습니다. 이번 시간에 설명드릴 내용은, Doubly Linked List입니다! Singly Linked List와는 다르게 양방향에서 즉, 앞 뒤로 데이터의 삽입이 가능한 자료구조의 형태입니다! 이해가 잘 안 가신다면, 아래 링크를 통해 단방향 연결 리스트에 대한 설명을 읽고 오시는 것을 추천드립니다!!

 

hazarddev.tistory.com/39

C++로 구현하는 자료구조!!!연결리스트(LinkedList)@@

대략적인 이중 연결 리스트의 추상적 형태는 아래 그림과 같습니다!

 

Doubly Linked List               출처 : geeksforgeeks.org

복잡하시다구요? 네! 복잡하죠 어느 정도 단방향 연결 리스트에 비해선 복잡한 것 맞습니다. 대략적으로 설명드리자면, 위 그림의 A, B, C, D는 노드 객체입니다. 그리고 객체 안에 자신의 앞과 뒤를 가리키는 포인터 변수가 포함되어 있습니다. 그렇기 때문에 자신의 앞과 뒤를 모두 가리킬 수 있는 노드 객체가 되는 것이지요! 아 굳이 이렇게 해야 하는 이유를 모르시겠다고요? 저도 그랬습니다. 그런데 생각해보세요! 하지만 이렇게 하면 할수록 탐색과 삽입, 제거에 매우 유리해집니다! 객체의 안전성 또한 확실하게 보장되겠죠! 또한 원형 연결 리스트라는 자료구조가 하나 더 남아 있는데, 글을 올릴 예정이긴 하지만, 간략하게 설명드리면, 맨 앞의 노드와 맨 마지막 노드를 연결하는 구조로서 추상적 형태가 원형을 띄는 자료구조입니다!! 

 

Data Structure on STL  출처 : geeksforgeeks.org

아 이렇게 완벽한 STL이라는 친구가 있는데 굳이 class로 구현하는 이유가 궁금하다면, 아직 좀 더 심도 깊은 이해가 필요할 것 같습니다! 당연히 실제 퍼블리싱 되는 프로그램이나, 사용되어야 하는 프로그램을 제작하는 과정에선 내가 한 엉망의 코드보다는 전문가가 만든 완벽한 코드의 집합을 사용하는 것이 좀 더 유리한 건 팩트니까요! 그런데 그런 것들을 어떻게 개발했는지, 어떻게 흐름인지 이해하지 않고 사용하신다면 절대로 잘 사용하실 수 없습니다! 

 

여하튼 정리하자면, 저는 class로 구현해볼 예정입니다! 그냥 stl로 사용된 버전이 보고싶으신 분은 위의 링크를 타고 들어가셔서 아래로 스크롤하시다 보면, stl로 간략하게 구현한 Linked List가 있으니 보시는 것을 추천드립니다!

 

Implementation Doubly Linked List by class

우선, 뭐부터 해줘야할까요? 당연히 연결 리스트의 값이 되어줄 노드 객체를 선언해주어야 합니다! 이제부터 코드로 어느 정도 설명이 들어가니 두 눈 잘 뜨고 보시면 나중에 다 이해가 돼있을 것이라 생각합니다!

 

Node Class 

#include <iostream>
#include <string>
 
class DoubleLinkedList;
 
class Node{
    friend class DoubleLinkedList;
    private:
        int val;
        Node *next; // -> 그 다음 노드를 가리키는 포인터 변수
        Node *prev; // -> 자신의 앞 노드를 가리키는 포인터 변수
    public:
        Node(Node *n, Node *p, int v){
            next = n;
            prev = p;
            val = v;
        } // -> 생성자는 총 두개로 다형성의 원칙으로 
        Node(int v){next = prev = NULL; val = v;}
};

class DoubleLinkedList{
    public:
        explicit DoubleLinkedList(int); // 생성자
        ~DoubleLinkedList(); // 소멸자
        void insertHead(int); // 헤드 노드에 삽입하는 멤버 함수
        void insertTail(int); // 꼬리 노드에 삽입하는 멤버 함수
        void insert(int, int); // 노드를 삽입하는 멤버 함수
        void deleteHead(); // 노드를 제거하는 멤버 함수
        void print(); // 클래스 내부의 객체들을 출력해줄 멤버 
 
    private:
        Node * head;
        Node * tail;
        int size;
};
 

DoubleLinkedList::DoubleLinkedList(int value){
    tail = head = new Node(value);
    size = 1;
} // 생성자의 초기화
 
void DoubleLinkedList::insertHead(int value){
    Node * newNode = new Node(value); // 새로운 노드 선언
    if(head == NULL){
        tail = head; // 만약 헤드노드가 널일 때, 꼬리노드에 헤드노드를 삽입해 연결시켜줌
    }else{
        newNode -> next = head; //헤드노드가 널이 아닐 때, 헤드노드의 다음을 현재의 헤드노드로 연결
        head -> prev = newNode; // 헤드노드의 앞을 가리키는 포인터 변수에 새로운 노드 대입
    }
    head = newNode; // 헤드노드에 새로운 노드를 대입
    size++;
}
 
void DoubleLinkedList::insertTail(int value){
    Node * newNode = new Node(value); // 새로운 노드 선언
    if(tail == NULL){
        head = tail; //꼬리 노드가 널일 때 헤드노드에 꼬리노드 대입
    }else{
        newNode -> prev = tail; //새로운 노드의 앞 부분을 꼬리 노드로 대입
        tail -> next = newNode; // 꼬리 노드의 다음을 가리키는 포인터 변수에 새로운 노드 대입
    } 
    tail = newNode; // 꼬리 노드에 새로운 노드 
    size++;
}

글로 설명드려야지 했는데, 주석 달고보니, 딱 저 정도만 이해해도 삽입하는 함수는 이해가 끝났다고 무방합니다..ㅎㅎ 그냥 헤드 노드와 꼬리 노드에 삽입하는 함수이기 때문에 뭐 특별한 내용은 없습니다. 그냥 insert()와 delete()가 조금 복잡합니다!

 

void DoubleLinkedList::insert(int idx, int value){
    if( idx < 0 || idx >= size){
        std::cout << "IndexError" << std::endl;
        return;
    }
    else if(idx == 0){
        insertHead(value); // 0일때는 당연히 헤드 노드로 삽입하겠죠?
    }else if(idx == size - 1){
        insertTail(value); // -1이면, 맨 마지막 노드를 가리키니, 꼬리 노드로 삽입합니다
    }else{
        Node * newNode = new Node(value); //새로운 노드 선언
        Node *cur = head; // 새로운 노드를 선언해 헤드 노드를 대입시킴
        int i = 0;
        while(i < idx - 1){ // 인덱스 노드의 전 노드가 될 때까지 반복
            cur = cur -> next;
            i++;
        }
        newNode -> prev = cur; //새로운 노드의 앞부분은 당연히 cur노드입니다.
        newNode -> next = cur -> next; //새로운 노드의 다음 노드는 원래 cur노드가 가리키고 있던 다음 노드를 대입
        cur -> next = newNode; //위의 이유로 cur의 다음 노드는 새로들어온 노드를 
        cur -> prev = newNode -> prev;
    }
    size++;
}

조금 복잡할 수 있는데, 잘 읽어보시면 답이 다 나와있습니다! 그냥 우리가 생각한대로 그대로죠!?

 

deleteHead(), print(), 소멸자

위 함수들은 사이즈가 작아서 한번에 코드 블록에 삽입을 했습니다. 앞선 포스팅들을 보시고 오신 분들이라면 사실 쉽게 이해가 갈 것이라고 생각합니다!!

void DoubleLinkedList::deleteHead(){
    if(head != NULL){ //헤드 노드가 널이 아닐때,
        Node *remove = head;
        head = head -> next;
        head -> prev = NULL; //하나씩 밀려남
        delete remove; //메모리 해제
        size--;
    }
}
 
void DoubleLinkedList::print(){
    Node *cur = head;
    while(cur != NULL){ // 다음 노드가 널일 때 까지 반복
        if(cur -> next == NULL){
            std::cout << cur -> val << std::endl;
        }else{
            std::cout << cur -> val << " " << "<- ->" << " ";
        }
        cur = cur -> next;
    }
}
 
DoubleLinkedList::~DoubleLinkedList(){
    Node *cur = head;
    while (cur != NULL){
        deleteHead(); //소멸자에서는 모든 객체의 메모리가 해제되어야 하기 때문에
    } //널이 아닐 때 까지 
}

DoubleLinkedList();
//코드를 좀 수정하겠습니다. DoubleLinkedList의 public 아래에 위의 코드를 삽입해주세요!
 
DoubleLinkedList::DoubleLinkedList(){
    tail = head = NULL;
    size = 0;
}
//그리고 DoubleLinkedList 클래스 아래에 위 생성자 코드를 삽입해주세요!
 
int main(){
    DoubleLinkedList* list = new DoubleLinkedList(); 
    for (int i = 0; i < 6; i++)
        list -> insertHead(i);
    list -> print();
    list -> deleteHead();
    list -> print();
}
 
RESULT > 
5 <- -> 4 <- -> 3 <- -> 2 <- -> 1 <- -> 0
4 <- -> 3 <- -> 2 <- -> 1 <- -> 0

코드 블럭의 내용대로, 코드를 수정해주시고 아래 main() 함수를 정의해서 컴파일해보시길 바랍니다!! 생성자가 하나 선언이 안되었네요ㅠㅠㅠㅠ 여하튼, 이렇게 코드가 수정되어 실행됐을 때, 아래 결과 값대로 잘 나온 것을 볼 수 있습니다!!

 

다음 글은 그래프로 할지,,, 힙으로 할지 고민이 되네요... 사실 지금까지의 내용도 그렇게 막 쉬운 내용은 아니기 때문에요 완벽하게 이해하는 것이 중요합니다! 하루를 이걸로 지새워도 이해를 해야 합니다!!

 

봐주셔서 감사합니다!!

 

댓글로 문의, 피드백, 질문 모두 환영합니다!!