[10] 연결 리스트(linked list)

배열의 큰 단점이 중간에 원소를 삽입하려면 cost가 매우 크다는 것이다.

중간에 자리를 만들기 위해서 나머지를 오른쪽으로 모두 옮겨야 한다.

같은 맥락으로 중간의 원소를 삭제할 때 

원소를 삭제한 후 나머지 원소들을 모두 왼쪽으로 옮겨야 해서 cost가 크다는 단점이 있다.

 

연결 리스트(linked list)를 사용하면 이러한 문제들을 어느정도 해결할 수 있다.

 

linked list는 다음과 같이 정의한다.

typedef struct _listNode {
    int data;
    // 여러 요소들
    struct _listNode* link;
}listNode;
typedef listNode *listPointer;

예시 프로그램을 만들어보자.

 

다음과 같이 연결하기 위해서는 다음과 같이 프로그램을 작성하면 된다.

int main() {
    listPointer A, B;
    A = (listPointer)malloc(sizeof(listNode));
    B = (listPointer)malloc(sizeof(listNode));
    
    A->data = 10;
    A->link = B;
 
    B->data = 20;
    B->link = NULL;
 
    return 0;
}

 

만약 A와 B 노드 사이에 C 노드를 삽입하고 싶으면 어떻게 하면 될까?

다음과 같이 A와 B의 연결을 끊고 A는 C를, C는 B를 가리키도록 해야한다. 

int main() {
    listPointer A, B;
    A = (listPointer)malloc(sizeof(listNode));
    B = (listPointer)malloc(sizeof(listNode));
    
    A->data = 10;
    A->link = B;
 
    B->data = 20;
    B->link = NULL;
 
    listPointer C;
    C = (listPointer)malloc(sizeof(listNode));
    C->data = 15;
    C->link = NULL;
 
    A->link = C;
    C->link = B;
 
    return 0;
}

그렇다면 이번엔 가운데 있는 노드 C를 삭제해보자.

A가 B를 가리키게 하면 된다.

int main() {
    listPointer A, B, C;
    A = (listPointer)malloc(sizeof(listNode));
    B = (listPointer)malloc(sizeof(listNode));
    C = (listPointer)malloc(sizeof(listNode));
 
    A->data = 10;
    B->data = 20;
    C->data = 15;
 
    A->link = C;
    C->link = B;    
    B->link = NULL;
 
    // A와 B 연결
    A->link = C->link;
 
    // C는 삭제하므로 꼭 free해준다.
    free(C);
 
    return 0;
}