6: 자료구조-4(연결 리스트: 코딩과 시연)

연결리스트의 코드를 나눠서 보기

 

1. 연결 리스트의 기본 단위가 되는 node 구조체를 정의

 

typedef struct node
{   
    //node 안에서 정수형 값이 저장되는 변수를 number로 지정
    int number;  
    //다음 node의 주소를 가리키는 포인터를 *next로 지정
    struct node *next;
}
node;

 

2.  list라는 변수 생성하고 그곳에 node의 주소(포인터)가 들어감

 

int main(void)
{
    // List of size 0 -> 연결리스트를 아무것도 없는 상태로 초기화(NULL)
    // 연결 리스트의 첫 번째 node 가리킴
    // list라는 빈박스를 NULL로 표현(아무것도 들어가 있지 않아서)
    node *list = NULL;
 }

 

3.  새로운 node를 위한 메모리를 할당하고 이 주소를 n이라는 변수에 저장

 

    node *n = malloc(sizeof(node));
    
    // if문은 안정성을 위해서! 무언가 잘못되면 1을 리턴해서 프로그램 멈춤 
    if (n == NULL)
    {
        return 1;
    }

 

4. 1과 NULL을 새로만든 node 구조체에 저장

 

    n->number = 1;
    n->next = NULL;

 

n의 number 필드에 1의 값을 저장함 n->number는 (*n). number와 동일함

node의 number 필드의 주소에 가서 1을 저장해라!

n 다음의 정의된 node가 없으므로 NULL로 초기화

 

5.  첫번째 node를 정의했기 때문에 list포인터를 n 포인터로 바꿔줌

 

 list = n;

 

비어있던 list 박스의 화살표가 새로운 node인 n을 가리키게 됨

 

6. 리스트에 입력한 값을 출력하기

 

    //마지막 node의 next에는 NULL이 저장되어 있어서 그건 for루프의 종료 조건이 됨
    for (node * tmp = list; tmp != NULL; tmp = tmp->next)
    {
        print("%i\n", tmp->number);
    }

 

list에 연결된 node를 처음부터 방문하며 각 number값을 출력함

for (초기화; 조건(NULL이 되면 반복 끝!); 업데이트하는 방법;)

for 루프의 종료 조건은 마지막 node의 next이 NULL인 것

 

7. 메모리 누수를 방지하기 위해 list를 free 해주기

메모리를 해제해주기 위해 list에 연결된 node들을 처음부터 방문하면서 free 해줌

 

    while (list != NULL)
    {
        node *tmp = list->next;
        free(list);
        list = tmp;
    }

 

8. 연결 리스트 코드

 

#include <stdio.h> // for printf
#include <stdlib.h> // for malloc, free

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

int main(void)
{
    node *list = NULL;

    // Add number to list
    node *n = malloc(sizeof(node));
    if (n == NULL)
    {
        return 1;
    }
    
    n->number = 1;
    n->next = NULL;

    // list가 새로운 node를 가리키게 됨
    list = n;

    // Add number to list
    // list에 다른 node를 더 연결하기 위해 n에 새로운 메모리를 다시 할당
    n = malloc(sizeof(node));
    if (n == NULL)
    {
        return 1;
    }
    
    // n의 number와 next의 값을 각각 저장
    n->number = 2;
    n->next = NULL;
    
    // list가 가리키는 것은 첫 번째 node의 next 포인터
    // list의 화살표를 따라서 다음 node를 n 포인터로 지정
    list->next = n;

    // Add number to list
    // 다시 한 번 n 포인터에 새로운 메모리를 할당하고 number와 next의 값을 저장
    n = malloc(sizeof(node));
    
    if (n == NULL)
    {
        return 1;
    }
    
    // n의 number와 next의 값을 각각 저장
    n->number = 3;
    n->next = NULL;
    
    // 현재 list는 첫 번째 node를 가리키고, 두 번째 node와 연결되어 있음
    // 따라서 세 번째 node를 연결 첫 번째 node(list)의 다음 node(list->next)의 다음 node(list->next->next)를 n 포인터로 지정
    // list에서 시작 1의 포인터 -> 2의 포인터  -> 3의 주소
    list->next->next = n;

    // Print list
    for (node * tmp = list; tmp != NULL; tmp = tmp->next)
    {
        print("%i\n", tmp->number);
    }
    
    // Free list
    while (list != NULL)
    {
        node *tmp = list->next;
        free(list);
        list = tmp;
    }
}

 

 

연결 리스트의 장점

- 배열과 비교해서 새로운 값을 추가하기 위해서 크기를 조절하고 기존의 값을 옮겨가면서 다시 메모리를 할당하지 않아도 됨

연결 리스트의 단점 

- 배열과 달리 임의 접근이 불가능함 (특정한 임의 값으로 바로 갈 수 었음 반드시 처음부터 -> -> ->)

 

---

연결 리스트에 값을 추가하거나 검색하는 경우 -> 해당하는 위치까지 연결 리스트의  node들을 따라 이동함

따라서 연결 리스트의 크기가 n일 때 실행 시간 -> O(n)

배열의 경우 임의 접근이 가능해서(정렬되어있을 때) 이진 검색을 이용하면 O(log n)의 실행시간이 소요됨(이럴 땐 연결 리스트에 비해 배열이 유리함!)

-> 임의접근을 할 수 있으면 binary search(이진 탐색)에 유용함

이렇게 여러 데이터 구조는 각각 장단점이 존재!

 

 

 

 

2021.12.11 - [소소한 CS 지식/CS50] - 6: 자료구조-3(연결 리스트: 도입)

6: 자료구조-3(연결 리스트: 도입)

 

https://www.boostcourse.org/cs112/joinLectures/41307

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