[C++기본] 28.연결 리스트

연결 리스트란?

연결 리스트는 가변 배열과 뭐가 다를까?

가변 배열은 힙 메모리 공간에 동적 할당을 통해, 일정 크기만큼 사용하는

연속적인 메모리 구조이다.

하지만 연결 리스트는 딱 하나의 메모리만이 들어갈 공간만 만든다.

이는 연속적이지 않은 구조를 가지고 있다.

즉, 3번째 데이터를 찾고 싶다면, 첫번째 데이터부터 각 데이터들이 가진 포인터를 이용해 2번 이동해 3번쨰 위치까지 가는 것이다.

이떄, 이 하나 하나의 구조들을 NODE,노드라고 한다.

노드 하나 하나에는 데이터와 다음 노드로 가는 주소도 같이 들어있다!

이렇게 구성 되어 있을 것이다.

이 노드들의 구성 방식에 따라 대표적으로 세 가지 종류의 연결 리스트가 있는데,

단일 연결 리스트

각 노드가 다음 노드만을 기리키는 일반적인 형태의 연결 리스트이다.

이 경우 다음 노드로는 갈 수 있지만, 이전 노드로 가는 주소값이 없기 때문에

이전으로 돌아가는 것은 불가능하다.

이중 연결 리스트

이중 연결 리스트에서는 각 노드는 2개의 주소값을 가진다.

하나는 이전노드, 하나는 다음 노드를 기리킨다.

이렇게 된다면 아까 말했던 이전노드로 가지 못하는 문제를 해결할 수 있다!

원형 연결 리스트

마지막 노드는 첫번쨰 노드를 가리키고 있는 연결 리스트이다.

이 경우 모든 노드를은 순환하게 되며, 한바퀴 돌면 어는 원소든 접근이 가능해진다!

---

리스트 만들기!

구조체부터 선언하자!

일단, 가변 배열을 만들 때와 비슷한 점을 찾아보자.

1.현재 개수 카운트 → 현재 얼마나 만들었는지는 필요할 것이다!

2.최대 개수 카운트 → 가변 배열에서는 연속적이 메모리 구조라서 필요했지만,

연결형 리스트에서는 최대치를 정하고 늘릴 필요가없을 것이다!

3.최초 노드의 주소 → 노든 노드는 첫번째 노드부터 연결되어 있다.

첫번째 노드의 주소만 기억해 놓으면, 2번쨰 노드는 첫번쨰 노드와 연결시켜 주기만 하면 된다!

다시말해 N번째 노드는 N-1번째 노드에서 기억해 주므로 우리는 첫번쨰 노드의 주소만 알면 된다

4.노드 → 리스트가 첫번째 노드의 주소를 알기 위해서는 노드라는 구조체를 하나 더 만들어 주어야 한다. 노드 하나는 저장할 데이터와, 다음노드의 주소를 멤버 변수로 받는다.

typedef struct NODE {

    int Data;
    NODE* NextNode;

}NODE;

노드의 구조체이다. 데이터 하나와 다음 노드의 주소를 가진다.

즉, 자기 자신과 같은 형태의 포인터 변수가 필요하다!!

typedef struct LINKEDLIST {

    NODE* HeadNode;
    int iCount;

}LINKEDLIST;

그렇게 완성된 연결 리스트이다.

한 연결 리스트는, 최초의 노드 주소와, 현재 얼마나 만들었는지를 저장할 변수 하나를 포함한다.

---

리스트의 기능은???

1.초기화

void InitList(LINKEDLIST* Plist) {
    Plist->HeadNode = nullptr;
    Plist->iCount = 0;
}

리스트는 가변 배열과 다르게 미리 데이터를 할당해 놓는 것이 아니라, 데이터가 추가될 때마다

노드를 생성한다.

즉, 초기화시에는 헤드노드는 없고, 카운트는 0이다.

2.노드 추가

void Push_Back(LINKEDLIST* Plist,int data) {
}

일단 리스트와 입력받을 데이터를 인자로 받는 함수를 작성하자.

어떤 기능부터 들어가야 할까?

NODE* InputNode=(NODE*)malloc(sizeof(NODE));

우선적으로, 힙 메모리 공간에 노드 하나만큼의 크기를 할당해 주어야 할 것이다!

    InputNode->Data = data;

그러고, 데이터를 넣어준다!

지금 추가하는 노드는 연결 리스트의 맨 마지막에 들어가야 하는 노드이다.

그래서 함수명도 Push_back이라고 지은 것이다.

그럼, 이 다음 주소를 가리키는 포인터 변수, Nextnode는?

//다음 주소 초기화
    InputNode->NextNode = nullptr;

당연히 null값으로 지정을 해 준다.

그럼 끝일까?

연결 리스트는 말 그대로 데이터들이 연결되어있는 구조이다.

그럼 이전 데이터가, 지금 내가 만든 이 데이터를 가리켜야 되지 않을까?

근데? 지금 넣는 데이터가 연결리스트의 첫 번째 데이터라면?

이전데이터가 없는데??

//이 데이터가 처음인가?
    if (Plist->iCount == 0) {
        Plist->HeadNode = InputNode;
    }
    else {

    }
    ++Plist->iCount;

그럼, 지금 이 노드가 최초의 노드인지 아닌지는 어떻게 판달할까?

우리는 iCount라는 현재 들어가있는 리스트의 노드 개수를 세는 변수를 만들었다.

우리가 만든 이 리스트가 잘 굴어간다는 가정 하에 iCount를 통해 최초의 노드를 판단할 수 있을 것이다.

이제 else에 들어가는 부분을 만들어보자

일단! 우리는 마지막 노드를 찾아야 한다.

그래야지 마지막 노드의 NextNode를 현재 노드의 주소로 바꿔 줄 수 있다.

그럼 마지막 노드를 어떻게 찾을까?

2-1.iCount 변수 이용

아까처럼, 노드의 개수를 세는 iCount를 이용해서 iCount번만큼 이동, 마지막 노드로 이동할 수 있다.

2-2.NextNode의 값이 null이 나올 때까지 반복하기

연결 리스트의 마지막 노드는 아직 결정되지 않는 값이기 때문에 null을 기리킨다.

이를 반복문을 통해서 이동 할 수 있다.

else {
        //마지막노드를 찾아서 그 노드의 NextNode를 
        //현재의 노드 주소로 옮겨준다.
        NODE* Hnode = Plist->HeadNode;
        while (true) {
            if (Hnode->NextNode == nullptr)
                break;
            else
                Hnode = Hnode->NextNode;
        }
    }

else부분만 잘라서 가져왔다.

기존 HeadNode의 값은 변하면 안되기에, 이를 지역변수로 가져왔고,

그 변수를 null이 나올 때까지 자기 자신을 다음노드와 바꿔가면서 이동했다.

그럼, 최종적으로 Hnode가 가지는 주소는 맨 마지막 노드의 주소일 것이다.

while (Hnode->NextNode) {
                Hnode = Hnode->NextNode;
        }

더 간단하게 표현하자면 이렇게도 표현할 수 있다.

null이 아니라면, 반복을 계속할 것이기 때문에!

Hnode->NextNode = InputNode;

마지막으로 주소를 옮겨주면 끝!

void Push_Back(LINKEDLIST* Plist, int data) {
    NODE* InputNode = (NODE*)malloc(sizeof(NODE));
    InputNode->Data = data;
    //다음 주소 초기화
    InputNode->NextNode = nullptr;
    //이 데이터가 처음인가?
    if (Plist->iCount == 0) {
        Plist->HeadNode = InputNode;
    }
    else {//두번째 이상의 노드
        NODE* Hnode = Plist->HeadNode;
        while (Hnode->NextNode) {
            Hnode = Hnode->NextNode;
        }
        Hnode->NextNode = InputNode;
    }
    ++Plist->iCount;
}

완성된 Push_Back함수이다.

3.메모리 해제

이 경우에도 두가지 방법을 이요해서 처리할 수 있다.

3-1.재귀함수를 이용

void ReleaseList(LINKEDLIST* Plist) {
    Release(Plist->HeadNode);
}

void Release(NODE* PNode) {
    if (PNode->NextNode == nullptr)
        return;

    Release(PNode->NextNode);
    free(PNode);
}

Release()는 현재 인자로 들어온 노드가 nullptr이 아니라면,

자기 자신을 먼저 호출하고, 메모리 영역을 해제한다.

머넞 해제해 버리면, 다음 노드로 접근할 수 가 없기 때문!

근데, 데이터의 개수가 많다면 이런 방법은 추천되지 않느다.

데이터의 개수만큼 함수가 호출되는데, 함수 호출에는 시간이 많이 걸리기 때문.

또한 스택 오버 플로우가 나타날 수 있다.

3-2.반복문 이용

void ReleaseList(LINKEDLIST* Plist) {
    NODE* DelNode = Plist->HeadNode;

    while (DelNode) {
        NODE* NextDelNode = DelNode->NextNode;
        free(DelNode);
        DelNode = NextDelNode;
    }
}

첫 DelNode를 헤드노드로 두고,

반복문을 이용해서 이름 다음 주소로 옮겨가면서 메모리를 해제하는 방식이다.

언제까지? DelNode가 null이 될 때까지!

Plist->iCount = 0;

카운트 0으로 바꿔주는거 잊지말긔

void ReleaseList(LINKEDLIST* Plist) {
    NODE* DelNode = Plist->HeadNode;

    while (DelNode) {
        NODE* NextDelNode = DelNode->NextNode;
        free(DelNode);
        DelNode = NextDelNode;
    }
    Plist->iCount = 0;
}

완성된 메모리 해제 함수

4.중간 노드 삽입, 삭제

중간 데이터가 삭제되거나, 삽입시에는 어떤 연산이 이루어질까?

가변 배열은 연속적인 메모리 구조이기 때문에 삽입하거나 삭제한 데이터 기준 으로

뒤의 데이터를 복사해 가며 이동해야 하기 때문에 한칸씩 밀릴 것이다. 이 과정에서 많은 시간이

발생한다.

연결 리스트는 연속적인 메모리 공간을 사용하지 않기 떄문에, 여러 데이터의 삽입, 삭제에 효율적이다.

중간의 데이터의 삽입과 삭제가 이루어진다면, 그저 이전 노드의 주소만 바꿔주면 된다.

즉, 데이터를 옮길 필요 없이 데이터들의 관계만 바꿔준다면 제 기능을 할 수 있따.

이런 연결리스트에도 단점이 존재한다.

바로 데이터 구조가 연속이지 않다는 것이다. 연속적이지 않는 데이터 구조는 여러 불편함이 있다.

특정 위치를 접근 하는데 있어 시간이 오래 걸린다는 것이다.

가변 배열에서는 주소 연산을 통해 한번에 특정 데이터로 접근이 가능했지만,

연결 리스트는 특정 데이터로 접근할 때, 노드를 타고 타고 타고 가야할 것이다,

최악의 경우는 마지막 노드로 접근 할 때일 것이다.

void Push_Front(LINKEDLIST* Plist, int data) {
    //새로 생성한 노드의 다음을 헤드로 바꿔준다.
    NODE* InputNode = (NODE*)malloc(sizeof(NODE));
    InputNode->Data = data;
    InputNode->NextNode = Plist->HeadNode;

    //Plist의 헤드노드의 주소를 바꿔준다.
    Plist->HeadNode = InputNode;

    ++Plist->iCount;
}

이 코드는 리스트의 맨 앞에 노드를 추가하는 함수이다.

가변 배열이라면, 데이터가 한칸씩 뒤로 밀렸겠지만, 연결 리스트에서는

헤드 노드의 주소만 바꿔주면 된다는 것을 알 수 있다.

---

완성

LinkedList.h

typedef struct LINKEDLIST {

    NODE* HeadNode;
    int iCount;

}LINKEDLIST;

typedef struct NODE {

    int Data;
    NODE* NextNode;

}NODE;

//리스트 초기화 함수
void InitList(LINKEDLIST* Plist);

//리스트 맨 뒤에 노드 삽입
void Push_Back(LINKEDLIST * Plist, int data);

//리스트 맨 앞에 노드 삽입
void Push_Front(LINKEDLIST * Plist, int data);

//리스트 메모리 해제
void ReleaseList(LINKEDLIST * Plist) ;

LinkedList.cpp

#include "LinkedList.h"
#include <iostream>

//리스트 초기화 함수
void InitList(LINKEDLIST* Plist) {
    //헤드노드는 null
    Plist->HeadNode = nullptr;
    //들어있는 개수는 0
    Plist->iCount = 0;
}

//리스트 맨 뒤에 노드 삽입
void Push_Back(LINKEDLIST* Plist, int data) {
    //새로운 노드 메모리 공간 할당
    NODE* InputNode = (NODE*)malloc(sizeof(NODE));
    //데이터 삽입
    InputNode->Data = data;
    //다음 주소 초기화
    InputNode->NextNode = nullptr;

    //이 데이터가 처음인가?
    if (Plist->iCount == 0) {
        Plist->HeadNode = InputNode;
    }
    else {//마지막 노드로 이동
        NODE* Hnode = Plist->HeadNode;
        while (Hnode->NextNode) {
            Hnode = Hnode->NextNode;
        }
        Hnode->NextNode = InputNode;
    }
    //개수 증가
    ++Plist->iCount;
}
void Push_Front(LINKEDLIST* Plist, int data) {
    //새로 생성한 노드의 다음을 헤드로 바꿔준다.
    NODE* InputNode = (NODE*)malloc(sizeof(NODE));
    InputNode->Data = data;
    InputNode->NextNode = Plist->HeadNode;

    //Plist의 헤드노드의 주소를 바꿔준다.
    Plist->HeadNode = InputNode;

    ++Plist->iCount;
}
void ReleaseList(LINKEDLIST* Plist) {
    NODE* DelNode = Plist->HeadNode;
    //반복문을 통해 마지막 노드로 이동 후 뒤로 오면서 해제
    while (DelNode) {
        NODE* NextDelNode = DelNode->NextNode;
        free(DelNode);
        DelNode = NextDelNode;
    }
    Plist->iCount = 0;
}