여러가지 연결 리스트

[연결 리스트]

1. 여러가지 연결 리스트 개념과 코드 : hello70825.tistory.com/158

2. 여러가지 연결 리스트를 이용한 알고리즘 문제 풀이: hello70825.tistory.com/159

3. 이중 연결 리스트 - 다항식의 연산(덧셈, 곱셈 : 구조체와 함수): hello70825.tistory.com/160

4. 이중 연결 리스트 - 다항식의 연산(덧셈, 곱셈 : 클래스와 operator): hello70825.tistory.com/219

5. 원형 연결 리스트 - 다항식의 연산(덧셈, 곱셈: 클래스와 operator, 반복자): hello70825.tistory.com/223

 

 

먼저 리스트는 선형 리스트(Linear List)와 연결 리스트(Linked List)로 나뉩니다.

 

• 선형 리스트

선형 리스트는 우리가 사용하고 있는 배열(Array)과 같습니다. 값들을 순서대로 나열하여 저장한 리스트를 선형 리스트(Linear List) 혹은 순차 리스트(Order List)라고 부릅니다. 리스트의 크기가 정해져 있는 것이지요.

• 선형 리스트의 장점

Random Access를 지원합니다.. 즉 Array[1], Array[7], Array[n-1] 이렇게 바로바로 접근이 가능하다는 것입니다.. 만약 N번째 값을 찾는다면 Array[N-1]을 입력하면 되는거라 O(1)의 시간이 걸립니다.

 

• 선형 리스트의 단점

배열에 어떤 값을 삭제 또는 추가할 때 O(N)의 시간이 걸립니다.

 

예를 들어 K번째 값을 삭제한다고 가정하면 선형 리스트는 빈공간이라는게 존재하지 않으므로 K+1번째 값부터 한칸씩 땡겨와서 K번째의 빈공간을 채워야합니다. 그래서 O(N-K) 의 시간이 걸립니다.

추가하는 것도 마찬가지입니다. K번째에 값을 추가한다고 가정하면 K번째값부터 한 칸씩 밀어줘야하기 때문에 O(N-K)의 시간이 걸립니다.

 

 

 

• 연결 리스트

연결 리스트는 선형 리스트와 다르게 배열을 한 칸씩 쪼개고, 그 한 칸 안에 다음 칸을 나타내는 포인터를 추가한 자료구조라고 생각하면 이해하기 쉽습니다.

이 쪼개진 한 칸을 노드라고 부르는데, 이 노드안에 저장할 값과 다음 노드를 가리키는 포인터를 넣어주는 것입니다.

참고로 맨 앞의 노드를 머리 노드(head node), 맨 뒤의 노드를 꼬리 노드(tail node)라고 부릅니다.

F의 다음 노드는 없으므로 nullptr을 적어준다.

• 연결 리스트의 장점

리스트에 값을 추가/삭제를 할 때 O(1)의 시간이 걸립니다.

만약 C노드와 D노드 사이에 Z노드를 추가한다고 가정하면 C노드의 포인터에 있는 값인 D의 주소를 Z의 주소로 바꾸고, Z노드의 포인터 값은 D의 주소로 설정하면 되므로 O(1)의 시간이 걸립니다.

삭제할 때도 마찬가지입니다. 만약 A, B, C, D, E, F노드에서 C노드를 삭제한다면 B노드의 포인터에 있는 값인 C의 주소를 D의 주소로 변경하면 되므로 O(1)의 시간이 걸립니다.

 

 

• 연결 리스트의 단점

Sequential Access를 지원합니다. 즉, N번째 노드의 값을 보고 싶으면 머리 노드부터 순차적으로 탐색하여 N번째 노드로 도달해야지 N번째 노드의 값을 볼 수 있습니다. 이 때문에 O(N)의 시간이 걸립니다.

 

• 연결 리스트의 종류

연결 리스트의 종류로는 원형 연결 리스트, 이중 연결 리스트, 원형 이중 연결 리스트가 있습니다.

 

원형 연결 리스트(Circular Linked List)란 꼬리 노드가 가지고 있는 주소값이 nullptr이 아니라 머리 노드의 주소를 가리키고 있는 것입니다. 이러면 그림이 원처럼 나오므로 원형 연결 리스트라고 부릅니다.

이중 연결 리스트(Doubly Linked List)란 어떠한 노드가 가지고 있는 주소값이 다음 노드(next_node)의 주소뿐만 아니라 이전 노드(pre_node)의 주소까지 가지고 있는 연결 리스트를 말합니다. 이러면 노드에 저장할 값, 다음 노드의 주소, 이전 노드의 주소 총 3개의 값을 가지고 있습니다.

 

원형 이중 연결 리스트(Circular Doubly Linked List)란 원형 연결 리스트와 이중 연결 리스트를 합친 연결 리스트 입니다. 머리 노드의 이전 노드의 주소값이 nullptr이 아닌 F노드의 주소값을 가지고, 꼬리 노드의 다음 노드의 주소 값이 nullptr이 아닌 A노드의 주소값을 가지고 있는 것입니다.

코드는 원형 이중 연결 리스트만 볼거에요.

왜냐하면 원형 이중 연결 리스트에서 필요없는 기능들만 빼면 연결 리스트, 원형 연결 리스트, 이중 연결 리스트 모두 구현이 가능하기 때문해서 그냥 이중 연결 리스트로 바로 넘어가는게 좋습니다.

 

============================================================================

 

처음에는 노드를 만들어줍니다.

1. friend class circular_doubly_linked_list는 circular_doubly_linked_list 클래스에서 Node의 private 값을 변경하기 위해 넣어주었습니다.

2. 위에 원형 이중 연결 리스트 사진과 같이 노드에 저장할 값인 value, 다음 노드의 주소값인 next_node, 이전 노드의 주소값인 pre_node를 넣어주기 위해 변수들을 선언합니다.

3. 노드를 만들 때는 Node(v, n, p)로 value, *next_node, *pre_node 순서대로 값을 넣을 수 있도록 만들어줍니다.

 

 

다음은 원형 이중 연결 리스트를 만들어주기 위해 circular_doubly_linked_list라는 클래스를 만들어줍니다.

1. private

개념을 설명할 때는 꼬리노드가 나왔지만 꼬리노드를 추가한다면 코드가 더 길어지기 때문에 머리노드만 만들었습니다.

어차피 머리노드를 추가/삭제할 때 head의 pre_node는 tail이기 때문에 이를 적절히 활용하면 됩니다.

ex)머리노드를 삭제할때 꼬리노드의 다음 노드 주소값 변경: head->pre_node -> next_node = head -> next_node

위 내용을 해석하면 머리노드의 이전노드의 다음노드. 즉 꼬리노드의 다음노드는 머리노드의 다음노드로 변경한다는 뜻입니다.

그리고 size는 연결리스트를 출력할 때, 연결리스트의 길이만큼 출력해야하므로 size를 추가해주었습니다.

 

2. public

circular_doubly_linked_list를 불러오면 처음엔 아무런 노드가 없으니 size=0이고 머리노드의 주소도 nullptr이 됩니다.

 

 

2-1. push_back

연결 리스트의 맨 오른쪽인 꼬리노드에 값을 넣어주는 함수입니다.

head의 주소값이 nullptr이면 아무런 노드가 없는 것이기 때문에 아래 그림처럼 노드를 만들어줘야합니다.

아래 그림에서 A노드는 머리노드이자 꼬리노드입니다.

 

head의 주소값이 nullptr이 아니라면 꼬리쪽에 노드가 추가된다는 것이므로 아래 사진과 같이 꼬리노드가 노드B에서 노드C로 바뀝니다.

코드에서 new_node가 위 사진의 노드C와 같습니다.

새 노드의 다음노드 = 머리노드

새 노드의 다음노드 = 변경하기전의 꼬리노드(=머리노드의 이전노드)

꼬리노드의 다음노드(=머리노드의 이전노드의 다음노드) = 새 노드

꼬리노드(=머리노드의 이전노드) = 새 노드

세번째 줄과 네 번째 줄의 순서를 조심해야합니다.

`

그리고 노드 한 개가 추가되었으므로 size의 값에 1을 더해주면 push_back 함수가 끝나게 됩니다.

 

2-2. insert

k번째 노드에 value를 넣어주는 함수입니다.

이러면 원래 k번째 노드부터 꼬리노드까지는 한 칸씩 밀려나게 됩니다.

 

만약 노드를 첫번째 노드인 머리노드에 값을 넣는 것이라면

새 노드의 다음 노드 = 변경하기전의 머리노드

새 노드의 이전 노드 = 꼬리노드(= 변경하기전 머리노드의 이전노드)

머리노드의 이전노드 = 새 노드

머리노드 = 새노드 

 

만약 노드를 K=0이 아닌 K번째에 값을 추가해주려면 연결 리스트는 Sequential Access를 지원하기 때문에 for문을 이용하여 머리노드부터 K번째 노드까지 이동해야 K번째 노드를 찾을 수 있습니다.

만약 위 사진에서 A 노드, B 노드 사이에 Z 노드를 넣어준다면 아래 사진과 같이 됩니다.

코드에서 새 노드는 Z 노드이구요.

위 사진을 일반화시켜서 N개의 노드(N>=k)가 있다고 가정하고 k-1번째 노드와 k번째 노드의 사이에 새로운 노드를 넣으려면, 먼저 k번째 노드를 구한다음 k-1번째 노드의 다음노드, k번째 노드의 이전노드의 주소값을 새 노드로 변경하면 됩니다.

그러므로 코드는 아래와 같고, 코드에서 dest 노드는 k번째 노드입니다.

새 노드의 이전 노드 = k-1번째 노드(=k번째 노드의 이전노드)

새 노드의 다음 노드 = k번째 노드

k-1번째 노드(=k번째 노드의 이전노드)의 다음 노드 = 새 노드

k번째 노드의 이전 노드 = 새 노드

 

그리고 마지막으로 insert함수는 연결 리스트에 값을 하나 추가해주는 것이니 size에 1을 더해줍니다.

 

 

2-3. erase

k번째 노드를 지우는 함수입니다.

erase함수를 사용하면 k-1번째 노드의 다음노드의 주소와 k+1번째 노드의 이전노드의 주소가 k번째 노드의 주소가 아닌 각각 k+1번째 노드의 주소, k-1번째 노드의 주소로 변경해야합니다.  그리고 k번째 노드를 삭제하면 됩니다.

 

만약 머리노드를 지운다고 할 때(= 0번째 노드 삭제를 삭제할 때)

temp라는 노드를 만들어서 head의 다음 노드로 설정합니다. 이것은 머리노드가 사라지면 머리노드의 다음노드가 머리노드가 되야하므로 temp 노드를 만들어둔 것입니다.

꼬리노드(=머리노드의 이전노드)의 다음노드 = temp 노드(=머리노드의 다음노드)

temp노드(=머리노드의 다음노드)의 이전노드 = 꼬리노드(=머리노드의 이전노드)

이렇게 설정해주면 이제 head를 지워도 되니 head를 삭제하고, 헤드의 빈자리를 temp노드로 변경해줍니다.

 

k=0이 아닌 양수일 경우, 연결 리스트는 Sequential Access를 지원하기 때문에 for문을 이용하여 머리노드부터 k번째 노드까지 순차적으로 탐색하여 찾아야합니다.

이때 코드에서 k번째 노드는 dest 노드입니다.

k-1번째 노드(= k번째 노드의 이전노드)의 다음노드 = k+1번째 노드(=k번째 노드의 다음노드)

k+1번째 노드(=k번째 노드의 다음노드)의 이전노드 = k-1번째 노드(=k번째 노드의 이전노드)

이제 k번째 노드(=dest 노드)의 주소값을 다 없앴으니 k번째 노드를 삭제하면 됩니다.

 

마지막으로 노드가 삭제되었으니 size에 1을 빼줍니다.

 

 

2-4. print

이것은 그냥 연결 리스트에 있는 노드들이 어떤 값을 갖고 있는지 머리노드부터 꼬리노드까지 순차적으로 출력해주는 함수입니다.

순차적으로 출력하기 위해 head노드와 같은 temp노드를 만들어주고, for문을 이용하여 temp->value를 출력한 뒤 temp -> next_node를 사용하여 다음 노드로 넘어갑니다.

 

 

============================================================================

 

이렇게 해서 완성된 코드는 아래와 같습니다.

 

 

#include <bits/stdc++.h>
using namespace std;
 
class Node{
    friend class circular_doubly_linked_list;
private:
    int value;
    Node *next_node;
    Node *pre_node;
public:
    Node(int v, Node* n, Node* p):value(v),next_node(n), pre_node(p){}
};
 
class circular_doubly_linked_list{
private:
    Node* head;
    int size;
 
public:
    circular_doubly_linked_list(){
        size = 0;
        head = nullptr;
    }
    void push_back(int value){
        Node* new_node = new Node(value, nullptr, nullptr);
        if(head == nullptr){
            head = new_node;
            new_node->next_node = new_node;
            new_node->pre_node = new_node;
        }
        else{
            new_node -> next_node = head;
            new_node->pre_node = head -> pre_node;
            head->pre_node->next_node = new_node;
            head->pre_node = new_node;
        }
        size++;
    }
 
    void insert(int k, int value){
        Node* new_node = new Node(value, nullptr, nullptr);
        if(k==0)
        {
            new_node -> next_node = head;
            new_node -> pre_node = head -> pre_node;
            head -> pre_node = new_node;
            head = new_node;
        }
        else{
            Node *dest = head;
            for(int i=0; i<k;i++)\
                dest = dest -> next_node;
            new_node -> pre_node = dest -> pre_node;
            new_node -> next_node = dest;
            dest -> pre_node -> next_node = new_node;
            dest -> pre_node = new_node;
        }
        size++;
    }
 
    void erase(int k)
    {
        if(k==0){
            Node* temp = head -> next_node;
            head -> pre_node -> next_node = head -> next_node;
            head -> next_node -> pre_node = head -> pre_node;
            delete head;
            head = temp;
        }
        else{
            Node *dest = head;
            for (int i = 0; i < k; i++)
                dest = dest->next_node;
            dest -> pre_node -> next_node = dest -> next_node;
            dest -> next_node -> pre_node = dest -> pre_node;
            delete dest;
        }
        size--;
    }
 
    void print(){
        Node* temp = head;
        cout << "[ ";
        for(int i=0; i<size+1; i++){
            cout << temp->value << " ";
            temp = temp -> next_node;
        }
        cout << "]" << endl;
    }
};
 
int main()
{
    circular_doubly_linked_list CDLL;
    for(int i=0; i<9; i++)
        CDLL.push_back(i);
    CDLL.print();
    CDLL.insert(1,9);
    CDLL.print();
    CDLL.erase(2);
    CDLL.print();
}
 

 

 

위 원형 이중 연결 리스트 코드에서 pre_node를 없애주면 원형 연결 리스트가 되는 것이고, 머리노드의 이전노드와 꼬리노드의 다음노드의 주소값을 nullptr로 변경해주면 이중 연결 리스트가 됩니다. 그리고 위 두가지 기능을 없애주면 일반적인 연결 리스트가 됩니다.

그래서 어떤 연결리스트를 만들때, 아예 이중 원형 연결 리스트 코드를 외운다음 코드를 제거하는 식으로 만들면 훨씬 더 받아들이기 쉬운 것 같네요.

 

 

 

 

 

 

 

참고 글

연결 리스트 코드 개념 - blog.naver.com/kks227/220781402507

원형 이중 연결 리스트 코드 참조 - hackerjacob.tistory.com/60

선형 리스트와 연결 리스트 장점, 단점 - www.studytonight.com/data-structures/linked-list-vs-array