[CS50] 연결리스트 : 시연

이번 포스팅에선 저번 포스팅의 내용을 실제 강의에서 어떤 방식으로 학생들이 시연하는지를 보고 이해하는 것이 편할 것 같아 링크를 남깁니다.

https://www.boostcourse.org/cs112/lecture/119040?isDesc=false 

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

 

이 영상을 보고 지난 시간에 코딩했던 코드를 보면 이해가 빠를겁니다.

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

//지난 시간에 포스팅한 node 구조체 정의
typedef struct node
{
	int number;
    struct node *next;
}
node;


int main(void)
{
//list라는 이름의 node 포인터를 정의함과 동시에 NULL로 초기화 시켜줌
	node *list = NULL;
    
    //node에 메모리를 할당하고 포인터 *n으로 가리킴
    node *n = malloc(sizeof(node));
    if(n == NULL)
    {
    	return 1;
    }
    
    //(*n).number = 1;와 동일한 의미
    //node의 number 필드를 의미함
    n->number = 1;
    n->next = NULL;
    
    //첫번째 node를 정의했으므로 16줄의 *list를 *n으로 바꿔줌
    list = n;
    
    //list에 다른 node를 더 연결하기 위해 n에 새로운 메모리 할당
    n = malloc(sizeof(node));
    if(n == NULL)
    {
    	return 1;
    }
    
    n->number = 2;
    n->next = NULL;
    
    //list가 가리키는 첫번째 node의 다음 node를 n으로 지정
    list->next = n;
    
     n = malloc(sizeof(node));
    if(n == NULL)
    {
    	return 1;
    }
    
    n->number = 3;
    n->next = NULL;
    
    //list가 두번째 node와 연결된 첫번째 node를 가리키고
    //세번째 node를 연결하기 위해 두번째 node의 next를 n으로 지정
    list->next->next = n;
    
    for(node *tmp = list; tmp != NULL; tmp = tmp->next)
    {
    	printf("%i\n", tmp->number);
    }
    
    //마지막으로 메모리 해제를 위해 list에 연결된 node를 처음부터 free해줌
    while(list != NULL)
    {
    	node *tmp = list->next;
        free(list);
        list = tmp;
    }
}

 

다시 한번 정리해보자면 배열과 달리 연결 리스트는 새로운 값을 추가할때 다시 메모리를 할당하지 않아도 된다는 장점을 가지고 있지만 단점으로는 연결리스트에서는 임의 접근이 불가능하다는 것입니다.

 

연결리스트에 값을 추가하거나 검색하는 경우 연결리스트는 각 node들을 따라 이동해야 하므로 연결 리스트의 크기가 n일 때 O(n)의 실행시간을 갖지만 

배열의 경우 임의 접근이 가능하기 때문에(즉 정렬이 되어있는 경우) 이진 검색을 활용한다면 O(log n)의 실행시간을 가지게 되므로 연결 리스트가 배열보다 효율이 떨어지게 될 수 있습니다.

---

출처

본 내용은 CS50의 2019년 강의를 듣고 작성했습니다. (개념이 어느 정도 정리되면 최신강의도 다시 듣고 수정할 내용 있으면 수정하겠습니다.)

 

강의 자료는 EdX에서 무료로 사용할 수 있고 boostcourse에서 한글 강의로도 들을 수 있습니다.