[Data Structure] 연결 리스트(Linked List)

● 연결 리스트(Linked List)

연결 리스트는 선형 리스트처럼 리스트의 한 종류입니다. 연결 리스트는 전체적으로 보면 선형 리스트의 단점을 보완한다는 점이 있지만, 그만큼 구현이 복잡하기 때문에 서로가 장단점은 가진다고 볼 수 있습니다.

 

선형 리스트의 가장 큰 단점이라고 한다면 바로 리스트의 조작입니다. 선형 리스트는 배열을 기반으로 하기 때문에 정해진 크기 내에서만 활용이 가능하며, 그렇다고 배열의 최대 크기를 너무 크게 잡아버리면 낭비되는 메모리가 많아 결점이 많은 방법이었습니다. 

 

연결 리스트는 이러한 문제를 해결해 줍니다. 연결 리스트는 배열을 사용하지 않고, 데이터 하나하나를 node의 개념으로 접근합니다. 예를 들어 배열에 1과 2를 넣으면 1과 2는 서로 다른 인덱스에 들어있지만 결국은 배열에 묶여있기 때문에 1과 2를 조작하기 위해서는 배열 자체를 건드려야 합니다.

그러나 연결 리스트의 개념에서는 리스트가 존재하고 리스트 안에 node들이 독립적으로 존재합니다. 즉, 여러 개의 node들이 연결되어 리스트를 구성합니다. 이렇게 되면 배열과는 다르게 node들을 이어주는 연결 고리만 조작하면 자유롭게 삽입과 삭제가 가능합니다. 

 

---

연결 리스트의 처음은 head로 시작합니다. head는 node에 속하지 않으며 연결 리스트의 구조체에 들어가는 포인터 값입니다. head는 리스트의 시작인 만큼 첫 번째에 해당하는 값을 가리킵니다. 

node에는 두 가지 데이터 필드가 존재합니다. 하나는 내가 원하는 값을 담아줄 data와 위에서 말한 연결 고리에 해당하는 link입니다. 예를 들어 리스트의 구성을 2 다음에 5를 넣어주고 싶으면 전체 구성은 head->2->5가 될 것입니다. 여기서 2와 5는 node의 데이터 필드에 해당되고, 2를 데이터 필드로 가지는 node의 link는 그다음 node의 데이터인 5를 가리킬 것입니다. 그리고 5에 해당하는 node는 마지막이기 때문에 마지막 node의 link는 NULL을 가리킬 것입니다. 

 

※ node에 데이터를 담아서 사용할 경우에는 무조건 동적 메모리 할당을 한 상태에서 사용해야 합니다. 

---

연결 리스트에는 중심이 되는 3가지 기능이 있습니다.

바로 search, insert, delete입니다.

 

개요부터 말하자면, search는 내가 원하는 데이터 값을 전체 리스트에서 찾고 위치를 반환하는 것.

insert는 내가 원하는 데이터를 내가 원하는 위치에 삽입하는 것, delete는 내가 원하는 값을 삭제하는 것입니다.

 

search는 head가 가리키는 첫 번째 node부터 순서대로 데이터 필드를 훑으며 원하는 값을 찾는 과정입니다.

그래서 비교적 간단하게 구현할 수 있습니다.

 

● Insertion

 

insert부터는 몇 가지 경우의 수를 따져서 구현해야합니다. 

예를 들어 위와 같은 연결 리스트가 있다고 가정해봅시다. 당연히 연결 리스트를 구현하는데 구조체와 포인터가 이용되기 때문에 100, 200, 300은 node의 주소를 의미합니다. 

 

1. 중간에 값을 삽입하고 싶을 때

중간에 값을 삽입하는 경우에 중요한 것은 "링크를 찾아가는 것"입니다.

 

예를 들어 10과 40 사이에 30이라는 새로운 노드를 연결한다고 가정해 보겠습니다. 30의 주소를 150이라고 할 때, 이제 10의 link는 150을 가리키고 30의 link는 200을 가리켜야 합니다.  여기서 기존과 바뀌는 것은 10의 link입니다. 

그렇다면 해줘야 할 작업은 2개입니다. (10의 link를 150으로 바꾸는 것, 30의 link를 200으로 설정하는 것)

 

만약 10의 link를 먼저 바꾸고 30의 link를 설정하려고 한다면 오류가 발생할 것입니다. 왜냐하면 10의 link가 40에서 손을 떼는 순간부터 40이라는 node는 찾을 수 없게 됩니다. 원래는 10의 link를 통해 40을 찾을 수 있었지만 이 link가 끊어짐으로써 200이라는 주소를 찾아갈 방법이 없어진 것입니다.

그래서 무조건 삽입하는 node의 link를 뒤에 이어주고 나서 이전 node를 삽입한 노드의 주소로 이어줍니다.

2. 첫 번째 노드로 삽입하고 싶을 때

첫 번째 노드로 삽입하는 경우도 1번과 비슷하지만 이전과는 다르게 head 때문에 사뭇 달라집니다.

연결 리스트의 구조에서 알 수 있다시피 리스트의 시작은 head이고, 이 head가 리스트의 첫 번째 node를 가리킵니다.

 

맥락은 이전과 같고, 그 대신 삽입하는 node의 이전 노드가 head가 된다는 점이 다릅니다.

3. 마지막 노드로 삽입하고 싶을 때

마지막 노드로 삽입하는 경우에는 삽입하려는 노드가 다른 노드를 가리킬 필요가 없기 때문에 절차가 조금은 짧습니다.

리스트의 마지막 node는 가리키는 대상이 없기 때문에 link field가 NULL입니다. 

그래서 삽입하려는 노드의 링크를 NULL로 지정하는 것이 전부입니다.

그러나 문제는 어떻게 마지막 노드를 찾는지 입니다.

결론부터 말하자면 head가 가리키는 첫 번째 노드부터 끝까지 훑으면서 link가 NULL인 노드를 찾는 것입니다. 

그래서 반복문을 활용하기 때문에 앞선 과정들보다 구현하기 어렵습니다.

 

---

● Deletion

삭제 연산도 삽입과 마찬가지로 노드들의 link를 처리하는 것을 주의해야 합니다.

여기서도 문제는 어떻게 삭제하려는 노드의 앞 노드를 찾는지 인데, 이것도 위에서 한 것과 마찬가지로 반복문을 통해 찾아줍니다.

---

구현

1. list, node 구조체

typedef int element;

typedef struct ListNode {
    elenemt data;
    struct ListNode* link;
}listNode;

typedef struct LinkedList {
    listNode* head;
    int length;
}linkedList;

위에서부터 살펴보면 숫자 데이터를 리스트에 넣을 것이기 때문에 리스트의 요소로 넣을 것과 일반적인 정수 자료형을 구분하기 위해서 int를 element로 바꿔 보기 쉽게 변경합니다. 그렇다고 해서 int를 사용할 수 없는 게 아니고 정수형 자료형을 int와 element로 사용할 수 있다는 뜻이며 만약 모두 int로 처리하면 우리가 넣을 data와 다른 자료형들이 헷갈리기 때문에 이름을 바꿔주는 것입니다.

 

그다음은 node입니다. 

node에 들어가는 값은 우리가 삽입 혹은 삭제하고자 하는 데이터가 들어가야 합니다. 그리고 link field도 포함됩니다. 

 

마지막으로 linked list입니다.

head도 node형 데이터이지만 리스트에 귀속되는 자료이기 때문에 리스트에서 선언합니다. 그다음에 리스트를 삽입, 삭제하면 길이의 변화가 일어나기 때문에 length 또한 선언해 줍니다. 

 

2. list 생성, length 확인

linkedList* initlist() {
    linkedList* L;
    L = (linkedList*)malloc(sizeof(linkedList));
    L->head = NULL;
    L->length = 0;
    
    return L;
}

int getLength(linkedList* L) {
    return L->length;
}

첫 번째는 공백 리스트 생성입니다. 

먼저 함수 내부에 리스트를 하나 만들어주고 여기서 malloc를 사용하여 동적 메오리 할당을 해줍니다.

그다음 공백 리스트이기 때문에 head를 NULL을 가리키게 하고, length 또한 공백 리스트이기 때문에 0으로 해줍니다.

 

두 번째는 length 확인입니다.

이는 현재 리스트의 길이를 확인하기 위해 임시로 만들어주는 함수입니다.

 

3. search

search는 말 그대로 내가 원하는 값이 리스트 내에 존재하는지 확인하기 위한 함수입니다.

listNode* search(linkedList* L, element x) {
    listNode* temp = L->head;
    
    while(temp != NULL) {
    	if(temp->data == x)
            return temp;
        else 
            temp = temp->link;
    }
    return temp; 
}

개요는 특정 리스트 안에 원하는 값이 있는지를 알고 싶은 것이기 때문에 매개 변수는 리스트와 element로 설정합니다.

그다음에 메모리 할당이 필요 없는 temp라는 node형 변수를 생성하여 이를 head값으로 설정합니다. 이 의미는 리스트의 첫 노드를 가리키게 한다는 것입니다.

temp가 리스트의 첫 노드를 가리키고 있기 때문에 while문의 의미는 리스트의 처음부터 끝까지 모든 노드를 훑는다는 말이 됩니다. 그 안에는 조건문이 들어가는데 만약 temp의 data가 x와 같다면 바로 temp 반환, 아니면 temp가 다음 링크로 가게 하여 계속 search 하게 합니다.

 

temp에 메모리 할당을 하지 않아도 temp->data가 가능한 이유는 바로 temp는 L의 head를 가리키는 포인터로 실제로 data를 저장하는 것이 아닌 본인이 가리키는 곳의 값을 보여주기만 하는 기능을 가지기 때문입니다. 즉, link에 해당하는 주소값만을 저장하는 변수이기 때문이라는 것입니다. malloc을 통해 메모리를 할당해도 오류가 발생하지 않지만, 적지 않아도 메모리를 사용하지 않기 때문에 지장이 없는 것입니다.

 

4. insert

insert와 delete는 구현하는 방법이 두 가지입니다.

첫 번째는 매개변수로 element를 넣어서 값을 적어서 삽입, 삭제를 하는 것

두 번째는 매개변수로 삽입, 삭제하고자 하는 node를 넣는 것

 

먼저 첫 번째입니다.

void insert(linkedList* L, listNode* pre, element x) {
    listNode* newNode;
    newNode = (linkedList*)malloc(sizeof(linkedList));
    newNode->data = x;
    
    if(L->head == NULL) {
        newNode->link = NULL;
        L->head = newNode;
    }
    else if(pre == NULL) {
        newNode->link = L->head;
        L->head = newNode;
    }
    else {
        newNode->link = pre->link;
        pre->link = newNode;
    }
    L->length++;
}

매개변수부터 살펴보면 pre는 삽입 위치 이전의 노드를 의미합니다. 

함수 내부에는 data를 받아줄 노드를 생성하고 데이터를 저장해야 하기 때문에 메모리 할당을 시켜줍니다. 

 

먼저, if문이 의미하는 바는 리스트가 공백 리스트인 경우입니다. 공백 리스트인 경우에는 head를 조정해야 합니다.

 

else if문이 의미하는 바는 pre가 없는 상태, 즉 삽입하려는 위치가 리스트의 맨 처음인 경우입니다. 맨 처음에 넣어주는 것도 마찬가지로 head를 조정해야 합니다.

 

마지막 else문이 의미하는 바는 리스트 중간에 삽입하는 것입니다. 여기서부터는 명확하게 pre가 존재하기 때문에 pre의 link를 조정하는 것이 관건입니다.

 

위 모든 과정에서 중요한 것은 앞서 insert의 주의사항에서 말한 대로 삽입하려는 노드의 link를 먼저 연결시키고 나서 이전 노드의 link를 삽입한 노드로 바꿔주는 것입니다.

 

그리고 이 모든 과정이 끝난 후 리스트의 길이를 1 늘려줍니다.

 

만약 위를 두 번째 경우로 작성한다면 다음과 같습니다.

void insert(linkedList* L, listNode* pre, listNode* newNode) {
    if(L->head == NULL) {
        newNode->link = NULL;
        L->head = newNode;
    }
    else if(pre == NULL) {
        newNode->link = L->head;
        L->head = newNode;
    }
    else {
        newNode->link = pre->link;
        pre->link = newNode;
    }
    L->length++;
}

차이를 보시면 아시겠지만, 함수 내에서 newNode를 선언하냐 마냐의 차이입니다. newNode를 선언하지 않고 길이를 짧게 하는 대신 main 함수에서 따로 newNode를 만들고, 메모리 할당까지 하여 매개변수로 처리해야 할 것입니다.

그래서 결국은 newNode에 해당하는 3줄을 insert 내에서 하냐, main함수에서 하냐의 차이입니다.

 

앞선 설명에서 insert의 3가지 경우를 알아봤습니다. 위 코드는 물론 맨 처음에 넣는 조건문이 있지만 전체적으로 봤을 땐  중간에 삽입하는 경우입니다.

 

그럼 나머지 두 가지 경우를 살펴보겠습니다.

void insertFirst(linkedList* L, element x) {
    listNode* newNode;
    newNode = (listNode*)malloc(sizeof(listNode));
    newNode->data = x;
    
    newNode->link = L->head;
    L->head = newNode;
    L->length++;
}

void insertLast(linkedList* L, element x) {
    listNode* newNode;
    newNode = (listNode*)malloc(sizeof(listNode));
    newNode->data = x; 
    newNode->link = Null;
    
    listNode* temp;
    
    if(L->head == NULL)
        L->head = newNode;
    else {
        temp = L->head;
        while(temp->link != NULL) {
            temp = temp->link;
        }
        temp->link = newNode;
    }
    L->length++;
}

insertFirst는 위의 insert 함수와 비슷한 점이 많아 생략하고 insertLast만 다루도록 하겠습니다. 

일단 insertLast에서는 삽입하고자 하는 node가 마지막에 들어가는 것이 확실하기 때문에 노드를 초기화하면서 link로 같이 NULL로 초기화시킵니다. 그다음에 temp는 search에서 본 것과 비슷하게 이전 노드를 찾아주는 역할입니다.

 

temp를 첫 노드를 가리키게 설정하고 while문으로 반복시켜 temp가 가리키는 곳을 계속 뒤로 옮겨줍니다. 그 다음 while문을 탈출하는 조건이 처음으로 temp->link가 NULL이 되는 순간, 즉 newNode가 들어갈 자리에 도착한 순간 break 합니다.

그러면 자연스럽게 temp는 temp의 link가 NULL을 가리키는 노드, 즉 newNode바로 이전의 노드가 됩니다.

---

5. delete

delete 같은 경우에는 삭제 연산이기 때문에 free()를 사용하여 메모리를 없애줍니다.

#define True 1
#define False 0

int delete(linkedList* L, listNode* p) {
    listNode* pre;
    
    if(L->head == NULL) return False;
    if(p == NULL) return False;
    
    pre = L->head;
    while(pre->link != p) {
        pre = pre->link;
        if(pre == NULL) return False;
    }
    pre->link = p->link;
    free(p);
    
    L->length--;
    return True;
}

delete의 경우에는 성공적인 삭제가 이루어졌는지의 여부를 따지기 위해 int로 함수를 생성하여 0과 1의 반환값을 받아줍니다. 이 0과 1이라는 반환값을 좀 더 직관적으로 보여주기 위해서 이를 define 해줬습니다. 

그다음에 마찬가지로 삭제할 노드의 이전 노드인 pre를 생성합니다. pre는 데이터를 담는 노드가 아닌 포인터 역할이기 때문에 link만 가질 뿐 data가 필요 없어 malloc을 해줄 필요가 없습니다.

 

1. 첫 번째 if문은 공백 리스트에서 삭제를 하려는 경우입니다.

2. 두 번째 if문은 삭제하려는 값이 존재하지 않을 때입니다. 이는 리스트에 값이 존재하지 않는 게 아니라 진짜 p라는 노드에 data field에 값이 존재하지 않는 경우를 말합니다. 그리고, 이는 첫 번째 if문과는 별개의 내용이기 때문에 else if로 처리하면 안 됩니다.

 

3. 위 두 가지 경우가 아닌 정상적인 경우입니다. pre를 찾아주기 위해서는 먼저 pre를 첫 번째 노드를 가리키는 부분으로 두어 p에 해당하는 값이 나올 때까지 반복을 해야 합니다.

반복문 안에서도 주의할 사항은 if문으로 처리하였는데, 이 if문이 의미하는 바는 아무리 리스트를 뒤져도 p가 보이지 않는 경우를 의미합니다. 왜 if문의 조건이 이를 의미하냐면, 바로 위에서 pre = pre->link라고 하였는데 리스트의 마지막에 도달하면 pre의 link는 NULL이 될 것입니다. 그리고 이 값은 곧 pre가 됩니다. 그래서 처음으로 pre가 NULL이 되는 순간이 리스트의 탐색이 종료되는 순간이라는 것입니다.

 

4. pre를 찾는 과정이 종료되고 나면 먼저 pre의 link를 p가 현재 가리키고 있는 것으로 옮긴 다음 p를 삭제합니다.

당연히 리스트의 길이도 1 줄입니다. 그리고 이렇게 삭제가 완성되면 성공이기 때문에 return 1도 해줍니다.

 

그런데 만약 delete의 매개변수를 linkedList와 element로 주면 어떻게 될까요?

그러면 동적 메모리가 할당된 current 노드를 만들어서 반복문을 변형할 것입니다. 

void delete(linkedList* L, element x) {
    listNode* pre, cur;
    cur = search(L, x);
    
    if(L->head == NULL) return False;
    if(cur == NULL) return False;
    
    pre = L->head;
    
    if(pre->data == x) {
        L->head = pre->link;
        free(pre);
        L->length--;
        return True;
    }
    
    while(pre->link->data != x) {
        pre = pre->link;
        if(pre == NULL) return False;
    }
    pre->link = cur->link;
    free(cur);
    L->length--;
    return True;
}

매개변수로 data값만 주어졌기 때문에 해당 data가 어떤 노드에 있는지를 알아야 합니다. 그래서 현재 데이터가 있는 노드를 cur라고 두고 이를 search 연산을 통해 반환된 값을 적용합니다. 그러면 자연스럽게 cur은 x가 담긴 노드를 의미하게 됩니다. 

그다음은 반복문의 변화인데 pre->link->data라고 적어주는 것이 중요합니다. 결국은 우리가 삭제하려는 노드 이전의 노드의 링크와 그다음을 이어줘야 하기 때문에 pre의 값이 계속 변화해주어야 합니다.

그러면 또 다른 문제점이 생깁니다. pre는 L->head부터 시작하는데 정작 while문이 시작하는 pre->link는 두 번째 노드이기 때문입니다. 만약 내가 첫 번째 노드를 삭제하려고 할 때는 쓸 수가 없게 됩니다. 

그래서 첫 번째 노드를 삭제하려는 경우를 만들어줘야 합니다. 이는 if문으로 해결가능합니다. pre는 첫 번째 노드를 가리키는 것부터 시작하기 때문에 아무것도 하지 않은 상태에서의 pre->data는 첫 번째 노드의 값이 됩니다. 그래서 이를 활용하여 free(cur) 대신 free(pre)를 함으로써 첫 번째 노드도 삭제할 수 있습니다.

---

6. display

display는 현재 연결 리스트 내의 노드들을 출력하는 함수입니다.

void display(linkedList* L) {
    listNode* p;
    p = L->head;
    printf("L=(");
    
    while(p != NULL) {
        printf("%d", p->data);
        p = p->link;
        if(p != NULL) printf(", ");
    }
    printf(")\n");
}

연결 리스트는 하나의 배열이 아니라 여러 개의 독립적인 노드가 연결되어 있는 구조이기 때문에 단순한 반복문으로 모두 출력하는 것이 불가능합니다. 그래서 위의 함수들에서 사용한 원리와 마찬가지로 포인터 노드를 하나 생성하여 이를 첫 번째 노드를 가리키게 둔 후 반복문을 돌려 p가 가리키는 곳의 data를 출력하고 link를 옮기며 이후의 값들도 출력합니다.

printf 속 문장들은 깔끔하게 L=(a, b, c, d)처럼 보이게 조작한 것입니다.

---

이렇게 연결 리스트의 개념과 이들을 구현하는 방법에 대해 알아봤습니다.