자료 구조 | 연결 리스트(2) 코딩 및 특징

학습 목표

1. 연결 리스트를 구현하고 사용할 수 있다.
2. 연결 리스트와 배열의 장단점을 설명할 수 있다.

 

연결 리스트 코딩

구조체를 이용하여 실제 연결 리스트를 구현해보자.

 

사진 출처 cs50

 

지난 포스팅에서 본 그림을 생각하며 코드를 살펴보자.

 

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

typedef struct node{
    int number;
    struct node *next;
} node;

int main(void)
{
    // list라는 이름의 node 포인터 정의
    // 아무 것도 가리키고 있지 않기 때문에 NULL로 초기화
    node *list = NULL;
    
    // 새로운 node를 위해 포인터를 정의하고 메모리 할당
    node *n = malloc(sizeof(node));
    if(n == NULL){
        return 1;
    }
    
    // n의 number 필드에 1의 값 저장
    // n->number은 (*n).number과 동일한 의미
    // 즉, n이 가리키는 node의 number 필드를 의미
    n->number = 1;
    
    // n 다음에 정의된 node가 없기 때문에 NULL로 초기화
    n->next = NULL;
    
    // 첫 번째 node를 정의했기 때문에 list 포인터를 n 포인터로 변경
    list = n;
    
    // 더 많은 node 연결을 위해 n에 새로운 메모리 할당
    n = malloc(sizeof(node));
    if(n == NULL){
        return 1;
    }
    
    n->number = 2;
    n->next = NULL;
    
    // list가 가리키는 것은 첫 번째 node
    // 이 node의 다음 node를 n포인터로 지정
    list->next = n;
    
    // 다시 새로운 메모리 할당
    n = malloc(sizeof(node));
    if(n == NULL){
        return 1;
    }
    
    n->number = 3;
    n->next = NULL;
    
    list->next->next = n;
    
    // 연결 리스트을 처음부터 방문해 각 number값 출력
    for(node *tmp = list; tmp != NULL; tmp = tmp->next){
        printf("%i\n", tmp->number);
    }
    
    // 메모리 해제
    while(list != NULL){
        node *tmp = list->next;
        free(list);
        list = tmp;
    }
}

 

프로그램을 실행하면 결과는 다음과 같다.

 

 

연결 리스트의 특징

• 연결 리스트는 새로운 값을 추가할 때 다시 메모리를 할당하지 않아도 된다는 장점이 있다. 하지만 유동적인 만큼 구조가 정적인 배열에서처럼 임의 접근이 불가능하다.
• 연결 리스트에서 값을 추가하거나 검색할 경우 해당 위치까지 각 node를 따라 이동해야한다. 따라서 연결 리스트의 크기가 n일 때 그 실행 시간은 O(n)이다.
• 정렬된 배열에서 이진 검색시 O(log n)의 실행시간이 소요되는 것에 비해 불리하다. 

 

 

생각해보기

연결 리스트의 중간에 node를 추가하거나 삭제하는 코드는 어떻게 작성할 수 있을까.

연결 리스트가 끊어지는 일이 없도록 주의하며 코딩해야한다.

 

1) node를 추가하는 경우

예) 1->3 사이에 2를 추가해보자

• 2의 값을 가지는 node를 생성한다.
• 이 node의 포인터가 3을 가리키게 한다.
• 1의 값을 가진 node의 포인터가 2를 가리키게 한다.

 

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

typedef struct node{
    int number;
    struct node *next;
} node;

int main(void)
{
    node *list = NULL;
    
    node *n = malloc(sizeof(node));
    if(n == NULL){
        return 1;
    }
    
    n->number = 1;
    n->next = NULL;
    
    list = n;
    
    n = malloc(sizeof(node));
    if(n == NULL){
        return 1;
    }
    
    n->number = 3;
    n->next = NULL;
    
    list->next = n;
    
    
    // 중간에 2의 값을 가지는 새로운 node 추가
    n = malloc(sizeof(node));
    if(n == NULL){
        return 1;
    }
    
    n->number = 2;
    n->next = list->next;
    list->next = n;
    
    // 메모리 해제
    while(list != NULL){
        node *tmp = list->next;
        free(list);
        list = tmp;
    }
}

 

2) node를 삭제하는 경우

예) 1->2->3 에서 2를 삭제해보자

• 2를 가리키던 포인터가 3을 가리키게한다.
• 2의 값을 가지는 node를 삭제한다.

 

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

typedef struct node{
    int number;
    struct node *next;
} node;

int main(void)
{
    node *list = NULL;
        
    node *n = malloc(sizeof(node));
    if(n == NULL){
        return 1;
    }
    
    n->number = 1;
    n->next = NULL;

    list = n;
    
    n = malloc(sizeof(node));
    if(n == NULL){
        return 1;
    }
    
    n->number = 2;
    n->next = NULL;
    
    list->next = n;
    
    n = malloc(sizeof(node));
    if(n == NULL){
        return 1;
    }
    
    n->number = 3;
    n->next = NULL;

    list->next->next = n;
    
    // 2의 값을 가지는 node 삭제
    node *rmNode = list->next->next;
    free(list->next);
    list->next = rmNode;
        
    for(node *tmp = list; tmp != NULL; tmp = tmp->next){
        printf("%i\n", tmp->number);
    }
    
     while(list != NULL){
        node *tmp = list->next;
        free(list);
        list = tmp;
    }
}

 

---

이 글은 네이버 부스트 코스 David J. Malan(데이비드 J. 말란) 교수님의 모두를 위한 컴퓨터 과학(CS50 2019) 강의를 수강하고 작성한 글입니다. 본 강좌 내 실습에서는 CS50 Sandbox를 사용합니다.

 

모두를 위한 컴퓨터 과학 (CS50 2019)