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

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

Linked List - Singly Linked List

이번 포스팅에서는 링크드 리스트에 대해서 포스팅할 예정입니다. 이전에 큐, 스택을 배웠으니 링크드 리스트의 개념 또한 그렇게 어려운 개념이 아닙니다. 솔직히 말하자면, 자료구조를 학습할 때 스택과 큐 이전에 링크드 리스트를 먼저 선행하고 하는 것이 더 좋긴 하나,,, 흠 꼬여버렸네요 ^ㅜ^ 상관없습니다! 여하튼 선형 자료구조 중 가장 기본적인 구조가 되는 자료구조가 링크드 리스트입니다!!

 

그중에서도 단방향 연결리스트(Singlye Linked List)에 대해서 학습해봐야 합니다. 물론 양방향 연결리스트(Doubly Linked List) 또한 올릴 예정이니 우선 쉬운 것부터 해보자고요!

 

단방향 링크드 리스트의 추상적 형태 _ 출처 : geeksforgeeks.org

위 그림은 링크드 리스트의 추상적 형태라고 볼 수 있습니다. 데이터와 다음 노드를 가리는 포인터 변수를 담은 하나의 객체를 노드라고 보았을 때 각 노드 간 연결은 노드에 속해있는 포인터 변수의 메모리 주소 참조로 이뤄지는 거지요~! 사실 저희는 스택과 큐를 학습하면서 이 개념에 너무나도 익숙합니다! Head 노드는 단방향 연결 리스트의 인덱스 0번을 참조하게 되며 맨 마지막 노드는 nullptr을 가리키며 처음과 끝을 한정해줍니다!! 만약 스택과 큐를 통해 위 개념을 알고 싶으신 분이 계실 수 있기 때문에 아래 링크 남겨드립니다! 한 번씩 보고 오시는 것을 추천드립니다!!

 

hazarddev.tistory.com/37

C++로 구현하는 자료구조!!!스택 편@@

그리고 단방향 연결 리스트를 구현하는 데 있어서, 구현할 수 있는 방법은 많지만 저희가 시도해볼 방법은 class를 이용한 구현과 stl안에 정의되어 있는 list라는 라이브러리를 통해 해결할 예정입니다. 결코 어려운 개념이 아니니, 아래 글을 잘 읽어보시는 것을 추천드리겠습니다!

 

1. Class를 이용한 연결 리스트 구현

항상 설명이 모자라다고 생각하지만, 직접 구현해보아야 합니다. 괴물급 개발자 분들께서 개발하기 쉬우라고 기능을 만들어 주셨지만, 그분들도 처음 공부할 때는 직접 구현해보았기 때문에, 편리한 라이브러리 등을 제공하시고 계시기 때문에..... 그래서 직접 만들어 보아야 합니다! 지금부터 구현될 단방향 연결 리스트 같은 경우에는 원하는 값을 제거할 수 있게 했습니다. 물론 원하는 위치에 값을 삽입하는 것도 가능합니다! 그것은 바로 여러분들이 해야 할 일로 남겨둔 것이죠! 사실 원하는 값을 제거하는 코드만 보아도 어떻게 해야 할지 감을 잡으실 수 있으실 거라 예상합니다!! 이제 코드 영역으로 넘어갑시다!~

 

#include <iostream>
#include <string>
 
 
 
class LinkedList;
class Node{
    friend class LinkedList;
    private:
        int val;
        Node *link;
    public:
        explicit Node(int d = 0, Node *l = nullptr):val(d),link(l){}
};

 

string 헤더 파일은 무시하셔도...ㅎ  왜 들어갔는지 저도 잘 모릅니다 ㅋㅋㅋㅋㅋ... 여하튼 설명을 드리면 구현될 단방향 연결 리스트의 클래스를 전방 선언해 노드 클래스에서 프렌드 클래스로 등록할 수 있도록 합니다. 그런 다음 private 한정자 아래에 데이터와 다음 노드를 가리킬 수 있는 포인터 변수를 정의해 추가합니다! 이제 좀 길 수 도 있는 LinkedList클래스를 봅시다!

 

class LinkedList{
    private:
        Node *head;
        int size;
    public:
        explicit LinkedList(int s = 0, Node *h = nullptr):
            size(s),head(h){}
        void push(int val);int pop(int findVal);
        void show()const;
};
 
void LinkedList::push(int val){
    Node *newNode = new Node();
    newNode -> val = val;
    if (head == nullptr){
        head = newNode;
        head -> link = nullptr;
        size++;
        return;
    }else{
        Node *temp = head;
        while (temp -> link != nullptr){
            temp = temp -> link;
        }
        temp -> link = newNode;
        newNode -> link = nullptr;
        size++;
        return;
    }
}
 
int LinkedList::pop(int findVal){
    Node *temp = head;
    Node *deleteNode;
    if (size != 0){
        while (temp -> link != nullptr){
            if (temp -> val == findVal){
                Node *temp2 = head;
                while (temp2 -> link != temp){
                    temp2 = temp2 -> link;
                }
                deleteNode = temp -> link;
                temp2 -> link = deleteNode;
                free(temp);
                return findVal;
            }else{
                temp = temp -> link;
            }
        }
        std::cerr << "Can't find value" << std::endl;
        return -1;
    }else{
        int returnVal = temp -> val;
        free(temp);
        head = nullptr;
        this -> size--;
        return returnVal;
    }
}
 
void LinkedList::show()const{
    Node *temp = head;
    while (temp -> link != nullptr){
        std::cout << temp -> val << std::endl;
        temp = temp -> link;
    }
    std::cout << temp -> val << std::endl;
}

int main(){
    LinkedList *ll = new LinkedList();
    ll->push(1);ll->push(2);ll->push(3);ll->push(4);ll->push(5);
    ll -> pop(4);
    ll -> show();
    return 0;
}
RESULT > 
1
2
3
5

위와 같이 4가 제거되고 출력이 아주 잘 된 것을 확인할 수 있습니다!! 꼭 반드시 실습하세요!!

 

그리고 이제 stl로 정의된 list입니다!!

 

2. STL을 활용한 list 이용!

뭐 너무 간단합니다!! 정의되어 있는 함수들을 사용해서 간단하게 사용할 수 있어서 결코 어렵지 않으니까요~ 코드로 제가 부연 설명까지 다 해놓고 stl을 활용한 리스트는 설명을 마칩니다. 그리고 stl로 사용되는 list는요, 양방향 연결 리스트입니다. 앞, 뒤 어디든 데이터의 삽입과 제거가 가능합니다!!! 이점은 꼭 참고...

int main(){
    std::list<int> ll; // 연결 리스트의 데이터 타입 선언
    ll.push_front(1); // 연결 리스트의 전방 데이터 삽입
    ll.push_front(2);
    ll.push_back(3); // 연결 리스트의 후방 데이터 삽입
    ll.push_back(4);
    for(auto elem: ll)
        std::cout << elem << std::endl;
    ll.pop_back(); // 연결 리스트의 후방 데이터 제거 물론 전방 데이터 제거를 위해선
    // pop_front()를 활용해 사용가능
    std::cout << "Line ----- " << std::endl;
    for(auto elem: ll)
        std::cout << elem << std::endl;
    if (ll.empty()){ // 연결 리스트가 비어있는지 상태 
        std::cout << "Empty" << std::endl;
    }else{
        std::cout << "Not Empty" << std::endl;
    }
    return 0;
}
RESULT > 
2
1
3
4
Line ----- 
2
1
3
Not Empty