2-2. 연결리스트 - 메모리 해제 함수 / 전체 출력 함수 / 구현 시 주의할 점 / 연결 리스트의 특징

저번 연결리스트 포스팅의 예제들에서, 모든 노드값을 출력하는 부분이 상당히 긴것을 볼 수 있는데, 이것을 다음과 같이 모든 노드값을 출력하는 함수 showAll()을 만들어 출력하도록 하면 훨씬 효율적이다.

void showAll(Node *root){
    Node *curr = head->next;
    while (curr != NULL){
        printf("%d ", curr->data);
        curr = curr->next;
    }
    printf("\n");
}

연결 리스트의 전체 원소 메모리를 할당 해제하는 함수는 다음과 같다.

void freeAll(Node *root){
    Node *cur = head->next;
    while(cur != NULL){
        Node *next = cur->next;
        free(cur);
        cur = next;
    }
}

전체원소를 할당 해제할 때, 'head'는 할당 해제하지 않는다.

위에서 정의한 함수를 이용해 단일 연결 리스트를 만들어 보면 다음과 같다.

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

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

Node *head;

void addNode (Node *root, int data){
    Node (*newnode) = (int*)malloc(sizeof(Node));
    newnode->data = data;
    newnode->next = root->next;
    root->next = newnode;
}

void removeFront(Node *root){
    Node *front = root->next;
    root->next = front->next;
    free(front);
}

void freeAll(Node *root){
    Node *cur = head->next;
    while(cur != NULL){
        Node *next = cur->next;
        free(cur);
        cur = next;
    }
}

void showAll(Node *root){
    Node *cur = head->next;
    while (cur != NULL){
        printf("%d ", cur->data);
        cur = cur->next;
    }
    printf("\n");
}

int main(void){
    head = (Node*)malloc(sizeof(Node));
    head->next = NULL;
    addNode(head,5);
    addNode(head,4);
    addNode(head,3);
    addNode(head,2);
    addNode(head,1); 
    showAll(head);
    freeAll(head);
    system("pause");
    return 0;
}

1 2 3 4 5

+ 위의 코드에서, main함수에서 freeAll을 호출한 다음, showAll을 호출하면, 5개의 쓰레기 값을 볼 수 있다.

연결 리스트를 구현 할 때 주의할 점

위 소스코드에 덧붙여서, 삽입 및 삭제 기능에서 예외 사항을 처리할 필요가 있다. 삭제할 원소가 없는데 삭제하는 경우, 머리(Head)노드 자체를 잘못 넣은 경우 등을 체크해서 예외 처리 해야한다.

 

연결 리스트의 특징

1. 삽입과 삭제가 배열에 비해서 간단하다는 장점이 있다.
2. 배열과 다르게, 특정 인덱스로 즉시 접근하지 못하며, 원소를 차례대로 검색해야 한다. 이런 점에서 상대적으로 배열에 비해 처리 속도가 느릴 수 있다.(물론, 삽입과 삭제는 연결리스트의 처리 속도가 훨씬 빠르다.)
3. 추가적인 포인터 변수가 사용되므로 메모리 공간이 낭비 된다.

요약

• 연결리스트는 데이터를 선형적으로 저장하고 처리하는 한 방법이다.
• 기존에 배열을 이용했을 때보다 삽입과 삭제가 많은 경우에 효율적이다.
• 다만 특정한 인덱스에 바로 참조해야 할 때가 많다면 배열을 이용하는 것이 효율적이다.