[자료구조/알고리즘] 02. 연결 리스트 Linked List

CH 02 연결 리스트(Linked List)

목표

연결 리스트가 나오게 된 배경과 연결 리스트의 개념에 대해서 알아보고, 연결 리스트의 삽입, 조회, 삭제 연산이 어떻게 동작하는지 이해해 보세요. 그 후 C/C++ 프로그래밍 언어로 구현해봄으로써 한 층 더 자료구조의 이해의 깊이를 늘려보세요!

목차

1. 연결 리스트란 무엇인가?
   • 배열의 한계
   • 연결 리스트에 대해서
2. 연결 리스트 ADT
3. C로 구현하기
4. C++로 바꿔보기
5. 결론
   • 연결 리스트 정리
   • 연결 리스트 응용

1. 연결 리스트란 무엇인가?

배열의 한계

배열은 충분히 좋은 자료구조입니다. 인덱스를 통해서 조회, 추가, 삭제에 대한 연산이 가능하지요. 하지만, 프로젝트가 커지고 복잡해질수록 배열로는 한계가 있습니다. 제일 큰 한계는 다음과 같습니다.

1. 배열은 길이가 정해져 있어야 한다. 즉, 무한에 가까운 자료를 저장할 수 없다.
2. 배열 중간에서 삽입/삭제 과정이 일어날 때 데이터의 이동 및 복사가 매우 빈번히 일어나게 됩니다.

이것의 한계를 극복하기 위해 나타난 것이 리스트입니다. 리스트는 대표적으로 동적 배열을 이용한 배열 리스트와, 자기 참조 구조체의 동적 메모리 연산을 이용한 연결 리스트가 존재합니다. 우리는 이 중에서, 연결 리스트만을 알아보도록 하겠습니다.

연결 리스트에 대해서

앞서 연결 리스트는 자기 참조 구초체의 동적 메모리 연산을 이용한 자료구조라고 설명하였습니다. 간단히 말하면 위의 그림처럼 자기 참조 구조체들을 잇달아 동적으로 생성해서 연결하는 구조체입니다. 뭔가 간단하지 않죠? ㅎㅎ 하나 하나 뜻을 파악하면 그리 어렵지 않습니다. 

우선 동적 메모리 연산이란, C를 기준으로 malloc/free(C++은 new/delete) 함수를 이용하여 힙 메모리 공간에 동적으로 메모리를 올리고 지우는 것을 말합니다. 왜 이렇게 하느냐면, 스택 메모리는 컴파일 이전에 데이터가 초기화가 이루어져야 하기 때문에 수 없이 많은 데이터가 생성될 수 있을 때, 이를 모두 포함시킬 수 없습니다. 그래서 힙이라는 공간에, 데이터가 생길때마다 그 주소를 만들어두는 것이죠. 이 떄 주의할 점은 반드시, 동적 할당이 이루어졌다면 해제도 쌍으로 이루어져야 한다는 것입니다. 안그러면 메모리 누수 현상이 발생됩니다. 

이번에는 자기 참조 구조체에 대해서 알아보겠습니다.

일반적으로 연결 리스트를 포함한 많은 자료구조에서, Node라는 이름으로 자기 참조 구조체를 사용합니다. 노드는 일반적으로 데이터를 표현하는 데이터 부분과, 자기 참조 포인터형을 가지는 포인터 부분으로 나뉘어져 있습니다. 연결 리스트를 기준으로 노드의 포인터 영역은 다음 노드를 가리키는 부분입니다. 그림으로 따지자면 1이 들어 있는 곳이 데이터, 빨간 색 포인터가 저장된 곳이 포인터 영역입니다. 이것은 C 코드로 살펴보죠.

typedef struct _node{
    int data;
    struct _node * next;
}Node;

코드에서도 아시다시피 일반적으로 노드는 자료의 데이터를 표현하는 데이터 부분, 다음 혹은 떨어져 있는 노드를 가리키는 자기 참조 부분으로 나누어져 있습니다. 노드 추가/삭제 시에, 각 노드끼리 연결해야 합니다. 이 때 세심하게 코드를 짜지 않으면 연결해야 할 노드의 위치를 잃어버려서 접근할 방법이 사라지게 되는데 이를 메모리 누수 현상이라고 합니다. 이것은 심각한 오류이니, 주의해서 코드를 짜야 합니다. 이는 3절에서 더 설명하도록 하겠습니다.

2. 연결 리스트 ADT

연결 리스트의 ADT는 다음과 같습니다.

ADT LinkedList

• characters
  1. head: Node *
     • 연결 리스트의 머리 노드를 가리킴
  2. tail: Node *
     • 연결 리스트의 꼬리 노드를 가리킴
  3. size: int
     • 연결 리스트의 크기(=원소들의 개수)
• operations
  1. LInit(list: LinkedList *)
     • 리스트를 생성한 후에, 초기화가 진행됩니다.
  2. LCount(list: LinkedList *): int
     • 리스트의 크기를 반환합니다.
  3. LIsEmpty(list: LinkedList *): bool
     • 리스트가 비었는지 여부를 반환합니다.
     • 리스트가 비어있다는 것은 size가 0과 같다는 뜻입니다.
  4. LPushFront(list: LinkedList *, data: T): void
     • 리스트의 첫 번째 부분에 데이터를 저장합니다.
  5. LPushBack(list: LinkedList *, data: T): void
     • 리스트 마지막 부분에 데이터를 저장합니다.
  6. LPopFront(list: LinkedList *): T
     • 리스트의 첫번째 데이터가 삭제됩니다.
     • 삭제된 데이터는 반환됩니다.
  7. LPopBack(list: LinkedList *): T
     • 리스트의 마지막 데이터가 삭제됩니다.
     • 삭제된 데이터는 반환합니다.
  8. LGet(list: LinkedList *, index: int): T
     • 리스트의 index 번째 원소를 반환합니다.
  9. LDestroy(list: LinkedList *): void
     • 리스트의 모든 리소스를 해제합니다.
     • 이후 리스트를 사용하려면 다시 초기화가 진행되어야 합니다.

참고적으로 T는 Node의 데이터 영역을 표현합니다. 즉, 노드는 다음과 같이 표현될 수 있습니다.

typedef struct _node{
    T data;
    struct _node * next;
}Node;

3. C로 구현하기

자 이제 C로 구현해봅시다. 먼저 LinkedList.h 를 만들어서 다음 코드를 작성해주세요.

#pragma once

#include<stdio.h>
#include<stdbool.h>
#include<stdlib.h>
#include<assert.h>

typedef int T;

typedef struct _node {
    T data;
    struct _node * next;
}Node;

typedef struct _linked_list {
    Node * head;
    Node * tail;
    int size;
}LinkedList;


void LInit(LinkedList * list);
int LCount(LinkedList * list);
bool LIsEmpty(LinkedList * list);
void LPushFront(LinkedList * list, T data);
void LPushBack(LinkedList * list, T data);
T LPopFront(LinkedList * list);
T LPopBack(LinkedList * list);
T LGet(LinkedList * list, int index);
void LDestroy(LinkedList * list);

하나 하나 살펴보도록 하겠습니다.

# pragma once

이 부분은 proguard 부분입니다. 이 코드를 삽입하면, 컴파일 시에 헤더가 중복 삽입되는 것을 막을 수 있습니다.

#include<stdio.h>
#include<stdbool.h>
#include<stdlib.h>
#include<assert.h>

이 부분은 연결 리스트를 만들 때 필요한, 표준 라이브러리입니다. stdio.h는 NULL 키워드를, stdbool.h는 bool 타입을 stdlib.h는 malloc/free 함수들, assert.h는 assert 함수를 위해서 넣어두었습니다.

typedef int T;            //int를 노드의 데이터 타입 T로 지정

typedef struct _node {    //노드 지정
    T data;
    struct _node * next;
}Node;

typedef struct _linked_list {    //연결 리스트 지정
    Node * head;
    Node * tail;
    int size;
}LinkedList;

이 부분은 연결 리스트를 위해서 사용자 정의 타입들을 지정해 놓은 곳입니다. C에서 구현할 때 int 타입을 데이터 영역이라고 가정하겠습니다. 따라서, 데이터 영역을 표현하게 T로 재정의 해 두었습니다. Node는 앞서 언급했던대로 만들어 두었습니다. 이제 연결 리스트 ADT에 따라 characters 부분을 순차적으로 선언해 두었습니다. head/tail은 Node * 형으로 각각 첫 노드/마지막 노드를 가리키는 포인터 변수입니다. size는 리스트의 저장된 원소들의 수를 나타냅니다.

void LInit(LinkedList * list);
int LCount(LinkedList * list);
bool LIsEmpty(LinkedList * list);
void LPushFront(LinkedList * list, T data);
void LPushBack(LinkedList * list, T data);
T LPopFront(LinkedList * list);
T LPopBack(LinkedList * list);
T LGet(LinkedList * list, int index);
void LDestroy(LinkedList * list);

이 부분은 연결 리스트 ADT의 operations 부분을 C 코드로 바꿔둔 것입니다. 2절과 비교해서 보시면 좋을 것 같습니다. 이제 본격적으로 구현해보도록 하죠.

• 리스트 초기화 함수 LInit

LInit 함수는 매개 변수로 리스트의 포인터로 받고 해당 리스트를 초기화하는 역할을 합니다. 리스트 선언 시, 바로 불려지는 함수이지요. 제가 짠 초기화 함수는 다음과 같습니다.

void LInit(LinkedList * list) {
    list->head = NULL;
    list->tail = NULL;
    list->size = 0;
}

초기화 될 때 연결 리스트의 머리 부분 head, 꼬리 부분 tail은 가리키는 곳이 없습니다. 따라서 NULL 값으로 초기화하면 되지요. 그리고 저장된 원소가 없으니까 size를 0으로 초기화해주면 됩니다. 그림으로 보면 다음과 같습니다.

• 리스트 크기 반환 함수 LCount

LCount 함수는 매개 변수로 리스트의 포인터로 받습니다. 리스트 자체에서 크기에 대한 것을 내부 속성으로 가지고 있기 때문에 이것을 바로 반환할 수 있습니다. 코드로 구현하면 다음과 같습니다.

int LCount(LinkedList * list) {
    return list->size;
}

• 리스트가 비었는지 여부를 반환하는 함수 LIsEmpty

LIsEmpty는 매개변수로 리스트의 포인터로 받습니다. 리스트가 비었는지 여부를 판단하는 것은 현재 내부 속성으로 봤을 때 2가지 방법이 있습니다.

1. head, tail 이 모두 NULL 일 때.
2. size == 0일 때

저는 이 2가지 중 size를 이용하는 방법으로 다음과 같이 코드를 구현하였습니다.

bool LIsEmpty(LinkedList * list) {
    return (LCount(list) == 0);
}

• 리스트 머리 삽입 함수 LPushFront

LPushFront는 매개변수로 리스트의 포인터와 머리에 삽입될 데이터를 받습니다. 우리는 머리 부분에 삽입할 때 한 가지 부분을 주의해야 합니다. 바로 머리 부분이 NULL일 때, 바꿔 말해 리스트가 비어있을 때와 아닐 떄를 구분해서 코드를 짜야 한다는 것입니다.

1. 리스트가 비어 있을 때

먼저 리스트가 비어 있다면, 함수의 흐름은 다음과 같습니다.

    1. 새로운 노드를 만듭니다.
    2. 노드에 데이터를 넣습니다.
    3. head와 tail이 새로운 노드를 가리키게 합니다.
    4. size에 1을 더합니다.

그림으로 보면 다음과 같습니다.

2. 리스트의 비어 있지 않을 때  

비어 있지 않다면, 즉 원소가 존재한다면 함수의 흐름은 다음과 같습니다.

    1. 새로운 노드를 만듭니다.
    2. 노드에 데이터를 넣습니다.
    3. 노드의 포인터 부분과 현재 리스트의 head가 가리키는 노드와 연결합니다.
    4. head를 새로운 노드의 위치로 옮깁니다.
    5. size에 1을 더합니다.

    그림으로 보면 다음과 같습니다.

이를 코드로 구현하면 다음과 같습니다.

void LPushFront(LinkedList * list, T data) {
    Node * newNode = (Node *) malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;

    if (LIsEmpty(list) == true) {
        list->head = newNode;
        list->tail = newNode;
    } else {
        newNode->next = list->head;
        list->head = newNode;
    }

    list->size += 1;
}

• 리스트 꼬리 삽입 함수 LPushBack

LPushBack은 매개변수로 리스트의 포인터와 꼬리에 삽입될 데이터를 받습니다. 우리는 꼬리 부분에 삽입할 때 역시 머리 부분과 마찬가지로 리스트가 비어 있을 때 여부에 따라 코드를 달리 작성해야 합니다. 역시, 먼저 어떤 흐름으로 함수가 작성되어야 하는지 기술하고 코드를 작성하겠습니다.

1. 리스트가 비어 있을 때

먼저 리스트가 비어 있다면, 함수의 흐름은 다음과 같습니다.(머리 삽입과 동일)

    1. 새로운 노드를 만듭니다.
    2. 노드에 데이터를 넣습니다.
    3. head와 tail이 새로운 노드를 가리키게 합니다.
    4. size에 1을 더합니다.

그림으로 보면 다음과 같습니다.

2. 리스트의 비어 있지 않을 때  

비어 있지 않다면, 즉 원소가 존재한다면 함수의 흐름은 다음과 같습니다.

    1. 새로운 노드를 만듭니다.
    2. 노드에 데이터를 넣습니다.
    3. tail이 가리키는 노드의 다음 노드를 새로운 노드로 연결합니다.
    4. tail을 새로운 노드의 위치로 옮깁니다.
    5. size에 1을 더합니다.

    그림으로 보면 다음과 같습니다.

이를 코드로 구현하면 다음과 같습니다.

void LPushBack(LinkedList * list, T data) {
    Node * newNode = (Node *)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;

    if (LIsEmpty(list) == true) {
        list->head = newNode;
    } else {
        list->tail->next = newNode;
    }

    list->tail = newNode;
    list->size += 1;
}

• 리스트 머리 삭제 함수 LPopFront

LPopFront는 매개 변수로 리스트 포인터를 받고, 자료형 T 의 데이터를 반환합니다. 머리 삭제할 때 우선적으로 고려해야 할 점은 리스트가 비어있는지 여부입니다. 만약 리스트가 비어있다면, 데이터 삭제를 막아야 합니다. 때문에, assert.h의 assert 함수를 사용합니다. assert 함수는 해당 조건이 참이 아니라면, 프로그램을 멈추는 기능이 있습니다. 따라서, 리스트가 비어 있지 않다는 조건문을 넣어주시면 됩니다. 그 후 머리 삭제 함수는 다음 흐름으로 진햅됩니다.

1. 먼저 head가 가리키는 새로운 노드 포인터를 생성합니다.
2. 해당 노드의 데이터를 가져옵니다.
3. head를 노드의 다음 노드로 위치를 옮깁니다.
4. 노드를 삭제합니다.
5. size를 1 줄입니다.
6. 만약 노드가 비었다면, 만일을 위해 head와 tail을 모두 NULL로 만들어줍니다.
7. 데이터를 반환합니다.

다음 그림은 머리 삭제 시 원소들이 존재할 때를 나타낸 것입니다.

이를 코드로 나타내면 다음과 같습니다.

T LPopFront(LinkedList * list) {
    assert(LIsEmpty(list) == false);

    Node * curr = list->head;
    T data = curr->data;
    list->head = curr->next;
    free(curr);
    list->size -= 1;

    if (LIsEmpty(list) == true) {
        list->head = NULL;  
        list->tail = NULL;
    }

    return data;
}

• 리스트 꼬리 삭제 함수 LPopBack

LPopBack은 매개 변수로 리스트 포인터를 받고, 자료형 T 의 데이터를 반환합니다.꼬리 삭제할 때 역시 우선적으로 고려해야 할 점은 리스트가 비어있는지 여부입니다. 만약 리스트가 비어있다면, 데이터 삭제를 막아야 합니다. 그 후 꼬리 삭제 함수는 다음 흐름으로 진햅됩니다.

1. 먼저 tail가 가리키는 새로운 노드 포인터를 생성합니다.
2. 해당 노드의 데이터를 가져옵니다.
3. tail의 위치를 head로 옮깁니다.
4. 현재 노드 이전까지 tail의 위치를 옮깁니다.
5. 노드를 삭제합니다.
6. size를 1 줄입니다.
7. 만약 노드가 비었다면, 만일을 위해 head와 tail을 모두 NULL로 만들어줍니다.
8. 데이터를 반환합니다.

다음 그림은 꼬리 삭제 시 원소들이 존재할 때를 나타낸 것입니다.

이를 코드로 나타내면 다음과 같습니다.

T LPopBack(LinkedList * list) {
    assert(LIsEmpty(list) == false);

    Node * curr = list->tail;
    T data = curr->data;
    list->tail = list->head;

    while (list->tail != curr && list->tail->next != curr) {
        list->tail = list->tail->next;
    }

    free(curr);
    list->size -= 1;

    if (LIsEmpty(list) == true) {
        list->head = NULL;
        list->tail = NULL;
    }

    return data;
}

• 리스트 인덱싱 함수 LGet

LGet은 매개변수로 리스트 포인터와, 인덱스를 받습니다. 추가/삭제까지 했다면, 인덱싱은 굉장히 쉽습니다. 먼저 주어진 인덱스가 사이즈 내의 인덱스인지 판별한 후, 머리부터 반복문을 돌리면 됩니다. C로 짠 코드는 다음과 같습니다.

T LGet(LinkedList * list, int index) {
    assert(LCount(list) > index);
    Node * curr = list->head;

    for (int i = 0; i < index; i++) {
        curr = curr->next;
    }

    return curr->data;
}

• 리스트 소멸 함수 LDestroy

LDestroy는 매개변수 리스트 포인터를 받습니다. 만약 리스트가 존재한다면, 리스트의 모든 요소에 대한 리소스를 해제합니다. 먼저 리스트의 존재한다는 것은 list가 NULL이 아닐 때입니다. 그 후, 리스트의 사이즈만큼 원소들을 삭제시킨 후에, list를 NULL로 만들어주면 됩니다. 따라서 코드는 다음과 같습니다.

void LDestroy(LinkedList * list) {
    if (list != NULL) {
        int size = list->size;

        for (int i = 0; i < size; i++) {
            LPopFront(list);
        }

        list = NULL;
    }
}

4. C++로 바꿔보기

이제 C++로 바꿔보겠습니다. ADT 설명 때, OOP와 유사하다고 말씀드렸습니다. 따라서 ADT만 있다면, 클래스로 변경하는 것은 일도 아닙니다. ㅎㅎ 바로 바꿔보도록 하죠. 먼저 LinkedList.hpp를 만들고 다음의 코드를 입력해주세요.

#pragma once

#include <cassert>

template<class T> class LinkedList {
private:
    struct Node{
        T data;
        Node * next;
    };

    Node * head;
    Node * tail;
    int size;
public:
    void LInit(LinkedList * list){ //C에서 구현한 코드 }
    void LDestroy(LinkedList * list){ //C에서 구현한 코드 }
    int LCount(LinkedList * list) { //C에서 구현한 코드 }
    bool LIsEmpty(LinkedList * list){ //C에서 구현한 코드 }
    void LPushFront(LinkedList * list, T data){ //C에서 구현한 코드 }
    void LPushBack(LinkedList * list, T data){ //C에서 구현한 코드 }
    T LPopFront(LinkedList * list){ //C에서 구현한 코드 }
    T LPopBack(LinkedList * list){ //C에서 구현한 코드 }
    T LGet(LinkedList * list, int index){ //C에서 구현한 코드 }
};

먼저 클래스를 템플릿 클래스로 선언합니다. 따라서, LinkedList 는 템플릿 인수를 사용할 수 있게 됩니다. 이렇게 말이죠.

LinkedList<int> list;

클래스는 내부 속성이 필드가 되고, 연산이 메소드가 됩니다. 단순히 이렇게 바꾸는 것 뿐 아니라, 객체 지향적으로 코드를 손 볼 필요가 있습니다. 클래스는 우선 생성자와 소멸자가 존재합니다. 각각의 하는 일은 LInit, LDestroy와 같습니다. 따라서, LInit과, LDestroy 부분을 다음과 같이 변경합니다.

template<class T> class LinkedList {
private:
    //이전 단계 동일
public:
    LinkedList() : head(nullptr), tail(nullptr), size(0) {}

    ~LinkedList() {
        int size = this->size;
        for (int i = 0; i < size; i++) {
            this->popBack();
        }
    }
    //이전 단계 동일
};

C++은 클래스 생성 시에 생성자(LinkedList())가 호출됩니다. 생성자는 LInit과 마찬가지로 클래스의 멤버 필드들을 초기화해줍니다. 또한 인라인으로 멤버 필드를 초기화해줄 수 있습니다. 따라서 본체 부분을 제거해줄 수 있지요. 만약 로직이 들어간다면, 본체에다 적어주시면 됩니다. 또한, 스택 메모리에서 제거될 때 모든 클래스는 소멸자(~LinkedList())가 호출됩니다. 따라서 위처럼, 동적으로 할당된 리소스가 있다면 여기서 제거해주면 됩니다. C에서 C++ 코드로 바꿀 때 뭐가 달라졌는지 혹시 눈치채셨나요? 바로 매개변수로 쓰이던 (LinkedList *) 가 제거되었습니다. 왜냐하면 클래스는 결국 해당 객체의 필드와 연산을 제공해주기 때문에 포인터를 매개 변수로 받을 필요가 없는것이지요. 어렵다면, 그냥 클래스가 내부에서 포인터 변수를 넣어준다고 생각하시면 됩니다. 이 파트는 C++ 언어를 설명하는 파트가 아니기 때문에, 이쯤하고 넘어가겠습니다. 이제 모든 메소드를 바꿔봅시다. 아래 코드는 변경된 사항입니다.

template<class T> class LinkedList {
private:
    //이전 단계 동일
public:
    //이전 단계 동일
    //LCount
    int getSize() {
        return this->size;
    }
    //LIsEmpty
    bool isEmpty() {
        return (this->size == 0);
    }
    //LPushFront
    void pushFront(T data) {
        Node * newNode = new Node{ data, nullptr };

        if (this->head == nullptr) {
            this->tail = newNode;
        }
        else {
            newNode->next = this->head;
        }

        this->head = newNode;
        this->size += 1;
    }
    //LPushBack
    void pushBack(T data) {
       Node * newNode = new Node{ data, nullptr };

       if (this->tail == nullptr) {
           this->head = newNode;
       }
       else {
           this->tail->next = newNode;
       }

       this->tail = newNode;
       this->size += 1;
    }
    //LPopFront
    T popFront() {
       assert(this->isEmpty() == false);

       Node * temp = this->head;
       T data = temp->data;
       this->head = this->head->next;
       delete temp;
       this->size -= 1;

       if (this->isEmpty() == true) {
           this->head = nullptr;
           this->tail = nullptr;
       }

       return data;
    }
    //LPopBack
    T popBack() {
       assert(this->isEmpty() == false);

       Node * temp = this->tail;
       T data = temp->data;
       this->tail = this->head;

       while (this->tail != temp && this->tail->next != temp) {
           this->tail = this->tail->next;
       }

       delete temp;
       this->size -= 1;

       if (this->isEmpty() == true) {
           this->head = nullptr;
           this->tail = nullptr;
       }

       return data;
    }
    //LGet
    T get(int index) {
       assert(this->getSize() > index);	//리스트 크기가 인덱스보다 작거나 같으면 프로그램 중단.
       Node * curr = this->head;

       for (int i = 0; i < index; i++) {
          curr = curr->next;
       }

       return curr->data;
    }
};

메소드로 변환되면서 list 가 제거하였고, this-> 를 써서 멤버 필드를 접근하게 코드로 바꾸었습니다. 대부분 로직은 동일하기 때문에, 이로써 CPP로 코드 바꾸기를 마치도록 하겠습니다.

5. 결론

연결 리스트 정리

이렇게 해서 연결 리스트의 배경, 개념, 동작 원리, 구현까지 알아 보았습니다. 앞서 배열의 한계를 극복하기 위해서, 배열 리스트와, 연결 리스트가 만들어졌다고 하였습니다. 그렇다면 어느 것이 더 좋을까요? 우리가 배운 연결 리스트가 좋을까요? ㅎㅎ 아쉽게도 이 둘은 상황에 따라서 각각의 장단점이 존재합니다. 다음 표를 보시고 각 상황에 맞게 잘 쓰시면 됩니다.

	배열 리스트	연결 리스트
저장	모든 원소들이 연속된 공간에 저장되어 있다.	모든 원소들이 흩어져서 저장된다.
인덱싱	O(1)	O(N)
머리 삽입	O(N)	O(1)
꼬리 삽입	O(1)	O(1 or N)
중간 삽입/삭제	O(N)	검색 시간 + O(1)
메모리 공간	O(N)	O(N)
STL	cpp(vector), java(ArrayList)	cpp(list), java(LinkedList)

일반적으로 인덱싱과, 꼬리 삽입이 많이 일어날 때라면, 배열 리스트가 맞고, 중간 삽입 혹은 삭제가 빈번히 일어난다면 연결 리스트가 성능의 우위를 가지고 있습니다. 이렇게 해서 연결 리스트의 설명을 마치도록 하겠습니다. 연결 리스트에 대해서 감이 좀 잡히시나요? ㅎㅎ 연결 리스트에 대해 잘 이해하셨다면은 다음에 나와 있는 연결 리스트의 응용을 공부하여 스스로 구현하는 것도 좋은 도전이 될 것 같습니다.

연결 리스트 응용

연결 리스트 개념을 응용해서 조금 더 다음의 리스트들을 구현할 수 있습니다.

1. 더미 연결 리스트

   더미 연결 리스트는 head에 쓰레기 노드를 추가하여, 추가할 때, 첫 원소를 고려하는 부분을 제거할 수 있습니다. 즉, 조금 더 편하게 연결 리스트를 관리할 수 있습니다.

2. 원형 연결 리스트

   연결 리스트의 순회 기능을 추가합니다. 일반적으로 마지막 노드에 다다르면, 연결 리스트는 다시 첫 노드 접근을 진행해야 합니다. 원형 연결 리스트는 이러한 불편한 점을 개선한 리스트입니다. 다만, 노드 간, 무한 반복이 일어날 수 있기 때문에 이를 잘 처리해주어야 합니다.

3. 이중 연결 리스트

   단일 연결 리스트의 가장 큰 문제는 그 이전 노드를 찾기 위해서는 현재 노드만큼 순회를 해야 한다는 것입니다. 이중 연결 리스트는 prev 라는 자기 참조 변수를 하나 더 두어서, 이전 노드를 가리키게 만듭니다. 따라서 단 한번으로 이전 노드를 호출할 수 있습니다. 다만 추가, 삭제 시 단일 연결 리스트보다는 구현이 어렵습니다.

다음 장에서는 이 중에서 가장 많이 쓰이는 이중 연결 리스트에 대해서 알아보도록 하겠습니다.