[자료구조] 연결리스트

배열과 연결리스트의 차이?

연결리스트는 일반적으로 사용하는 배열과 달리 동적으로 각 칸들이 앞뒤로 사슬처럼 연결되어 있는 자료구조이다.

아래 사진은 1차원 배열과 연결리스트의 구조도이다. 

 

배열은 연속된 메모리 구조를 가졌고, 연결 리스트는 흩어진 공간들을 포인터로 연결한 구조이다. 

인덱스로 접근하면 되는 배열을 놔두고 왜 처음부터 차근차근 따라가야 하는 연결리스트를 사용할까?

 

데이터를 새로 삽입하거나 삭제할 때 연결리스트는 매우 유용하기 때문이다. 

값을 빼면 빈 자리(0)로 남겨지는 배열과는 달리,

연결리스트에선 이전 칸 포인터를 바꿔주고 해당 칸을 free() 해주면 된다.

 

각 칸들이 동적으로 구현이 되기 때문에 크기도 자유롭게 확장/축소가 가능하다. 

---

연결리스트 종류

1. 단일 연결 리스트

한 방향으로만 이동이 가능해서 처음부터 접근하려는 위치까지 찾아가야 한다. 

각 노드는 data와 next (다음 노드 주소) 를 가진다.

 

2. 이중 연결 리스트

각 노드가 이전 노드(Prev)와 다음 노드(Next) 주소를 가진다.

양방향으로 이동이 가능해서 앞/뒤 모두 탐색이 가능하다. 삽입과 삭제가 비교적 유연하겠다.

하지만 포인터가 2개이므로 메모리를 더 사용한다는 단점이 있다.

 

3. 원형 연결 리스트

마지막 노드의 Next가 다시 첫 노드를 가리킨다. 

---

단일 연결 리스트 구현 코드

구조체 Node 

typedef struct NODE {
    int data;
    struct NODE* nextNode;
}Node;

 

저장할 값을 나타내는 data와 다음 노드를 가리키는 포인터인 nextNode로 이루어진 구조체이다.

---

insertNode()

void insertNode(Node* head, int data, int idx) {
    Node* preNode = head;
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;

    for (int i = 0; i < idx; i++) {
        if (preNode->nextNode == NULL) {
            free(newNode);
            return; // error
        }
        preNode = preNode->nextNode;
    }
    newNode->nextNode = preNode->nextNode;
    preNode->nextNode = newNode;
}

 

특정 인덱스(idx) 위치에 새로운 노드를 삽입하는 함수이다.

만약 idx == 3이면 3번째 노드 뒤에 삽입한다.

 

preNode는 이전 노드를 가리키는 포인터다. 왜 정의하느냐?

 

우리가 노드를 삽입 또는 삭제할 때, 어느 위치에 삽입/삭제할지를 결정해야 한다. 

그러기 위해서는 현재 위치 뿐만 아니라 그 앞의 노드도 알아야 한다. 

그래서 preNode를 이용하여 리스트를 하나하나 순회하며 원하는 위치를 찾아가는 것이다.

 

Node* preNode = head 코드의 의미는

"preNode가 head부터 따라가면서 위치를 찾을 것이다." 라는 뜻이다.

 

따라서 head부터 시작해서 idx번 반복하며 preNode 위치까지 이동한다.

그리고 새로운 노드를 동적 생성 후, 데이터도 저장한다.

새로운 노드의 nextNode를 preNode의 nextNode로 설정한 뒤 preNode의 nextNode를 newNode로 바꾼다.

 

즉 기존에는 'preNode > 다음 노드' 였다면 이젠 'preNode > newNode > 다음 노드' 인 것이다.

---

appendNode()

void appendNode(Node* head, int data) {
    while (head->nextNode != NULL) {
        head = head->nextNode;
    }
    Node* newNode = (Node*)malloc(sizeof(Node));
    head->nextNode = newNode;
    newNode->data = data;
    newNode->nextNode = NULL;
}

 

연결 리스트 맨 끝에 새로운 노드를 추가하는 함수이다.

 

head 부터 시작해서 nextNode가 NULL일 때 까지 추적한다. (끝을 찾는 과정)
새 노드를 동적 할당한 뒤 마지막 노드의 nextNode를 새 노드로 연결한다. 

그리고 새 노드의 nextNode는 NULL로 설정하면 끝.

---

deleteNode()

void deleteNode(Node* head, int idx) {
    Node* temp = head;
    Node* target = NULL;
    for(int i = 0; i < idx; i++) {
        temp = temp->nextNode;
    }
    target = temp->nextNode;
    temp->nextNode = target->nextNode;
    free(target);
}

 

idx번째 노드를 삭제하는 함수이다.

 

temp 포인터를 하나 만들어 준다. 그리고 이 포인터로 head부터 idx만큼 이동한다. (타겟 찾는 중)

target은 삭제할 대상 포인터이므로 temp->nextNode 로 초기화해준다. (타겟 찾음)

 

temp->nextNode = target->nextNode 는 target을 건너 뛰는 코드이다. 

즉 temp > target > 다음노드 에서 temp > 다음노드 가 된 것이다.

 

노드가 삭제되었으니 free()로 target 메모리를 해제해준다.

---

printList()

void printList(Node* head) {
    int idx = 0;
    Node* node;
    node = head->nextNode;
    while (node != NULL) {
        printf("%d %d\n", idx, node->data);
        node = node->nextNode;
        idx++;
    }
    printf("\n");
}

 

head->nextNode 부터 끝까지 각 노드의 인덱스와 값을 출력하는 함수이다.

 

while(node != NULL) 조건이 '끝까지' 와 같다. 

---

main()

int main() {
    Node* head = (Node*)malloc(sizeof(Node));
    head->data = 0;
    head->nextNode = NULL;
    appendNode(head, 11);
    appendNode(head, 22);
    appendNode(head, 33);
    appendNode(head, 44);
    appendNode(head, 55);
    printList(head);

    insertNode(head, 66, 2);
    printList(head);

    deleteNode(head, 4);
    printList(head);
    
    return 0;
}

//출력
0 11
1 22
2 33
3 44
4 55

0 11
1 22
2 66 
3 33
4 44
5 55

0 11
1 22
2 66
3 33
4 55

---

단일 리스트 코드를 이중/원형 연결 리스트 코드로 바꿔보자

이중 연결 리스트

typedef struct NODE {
    int data;
    struct NODE* prev;     
    struct NODE* next;
} Node;

 

단일 연결 리스트는 nextNode 포인터만 정의한 것과 달리 prev와 next 포인터 2개로 양방향 연결이 가능하게 되었다.

이하의 모든 함수에서 prev 관련 코드가 추가되겠다.

 void appendNode(Node* head, int data) {
     while (head->next != NULL) {
         head = head->next;
     }
     Node* newNode = (Node*)malloc(sizeof(Node));
     newNode->data = data;
     newNode->next = NULL;
     //head->next = newNode; 이 줄은 빠진다.
     newNode->prev = head;  // 여기부터 추가된 부분
     head->next = newNode;
 }

 

새 노드가 앞 노드를 기억하는 코드가 추가되었다.

 void deleteNode(Node* head, int idx) {
     Node* temp = head;
     for (int i = 0; i < idx; i++) {
         temp = temp->next;
     }
     Node* target = temp->next;
     //temp->next = target->next; 
     temp->next = target->next;
     if (target->next != NULL) {
         target->next->prev = temp;   
     }
     free(target);
 }

 

다음 노드가 이전 노드를 다시 연결하도록 수정되는 코드가 추가되었다. ( target->next->prev = temp )

---

원형 연결 리스트

구조체는 단일 연결 리스트와 동일해도 무관하다.

하지만 마지막 노드의 next를 첫 노드로 연결시켜야 하고,

무한 루프 또한 방지해야 하므로 시작 노드도 체크해야 한다.

 

 void appendNode(Node* head, int data) {
     Node* newNode = (Node*)malloc(sizeof(Node));
     newNode->data = data;

     //newNode->next = NULL;
     //head->next = newNode;
     if (head->next == NULL) {
         head->next = newNode;
         newNode->next = newNode;    // 자기 자신을 가리킴 (첫 노드)
     } else {
         Node* temp = head->next;
         while (temp->next != head->next) {
             temp = temp->next;
         }
         temp->next = newNode;
         newNode->next = head->next;  // 마지막이 다시 처음을 가리킴
     }
 }

 void printList(Node* head) {
     int idx = 0;
     //Node* node = head->next;
     //while (node != NULL) {
     Node* node = head->next;
     if (node == NULL) return;
     Node* start = node;
     do {
         printf("%d %d\n", idx, node->data);
         node = node->next;
         idx++;
     } while (node != start);  // 처음 노드로 다시 돌아오면 종료 = 무한루프 방지
 }

---

이렇게 단일 연결 리스트 코드를 분석하고, 이를 이용하여 이중/원형 연결 리스트도 코드로 구현해보았다.

원형 연결 리스트 코드는 아직 이해가 완벽히 되진 않았지만.. 차차 구현해보며 익숙해져 보려고 한다.