부스트코딩 뉴비챌린지 스터디 6주차 : 연결리스트

3) 연결리스트 : 도입

 

배열은 메모리 상에서 덩어리로 붙어있지만 연결 리스트는 각 데이터가 메모리의 각기 다른 공간에 존재함. 대신 해당 메모리의 포인터가 다음 데이터를 가리키는 구조로써 연결되어 있음.

 

컴퓨터 공학에서 네모로 표현할 수 있는 메모리 덩어리를 node라고 한다.

위 자료구조에서 node는 정수와 포인터(주소값) 두 가지 데이터를 담고 있음.

 

📣 연결리스트를 구조체로 정의하는 법 

 

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

 

struct 다음에 node라고 쓴 것은 구조체 안에서 node를 쓰기 위한 문법이다.

 

4) 연결리스트 : 코딩

 

직접 만들어보자..

 

5) 연결리스트 : 시연

 

컴퓨터는 한 번에 하나의 메모리만 볼 수 있고 포인터를 따라 메모리를 확인해야 한다 

 

- 컴퓨터는 한 번에 하나의 메모리만 볼 수 있음. 즉, 연결 리스트의 숫자를 찾으려면 포인터를 따라 메모리를 하나씩 확인해봐야 함. 최대 시간이 걸릴 때는 모든 메모리를 확인해봐야함. 따라서 연결 리스트의 크기가 n일 때 실행시간은 O(n)이 됨.

 

- 연결 리스트의 장점은 배열처럼 숫자를 추가하기 위해서 크기를 조절하고 기존의 값을 모두 옮기지 않아도 된다는 것. 원래 있었던 것을 움직이지 않고도 리스트를 늘릴 수 있는 능력을 얻은 것.

 

- 단점은 임의 접근(random access)을 할 수 없다는 것. 중간 값을 바로 확인하는 게 불가능. 이진 탐색이 불가능해졌다. 

 

- 배열의 경우 임의 접근이 가능하기 때문에 이진 검색을 이용하면 실행 시간이 O(log n)으로 연결 리스트 보다 짧음 

 

- realloc에서 했던 것 처럼 메모리를 이동하지 않아도 되니 실행 시간이 덜 걸리지 않을까 싶지만 그런 것도 아니라는 것

 

6) 연결 리스트 : 트리

 

연결 리스트를 개념상 2차원으로 만든 것. 이진 탐색 트리.

 

typedef struct node
{
	int number;
    struct mode *left;
    struct node *right;
}
node;

 

노드 안에 left 와 right 라는 두 개의 포인터가 존재함

트리 가장 위에있는 노드는 '루트'라고 함. 루트의 주소를 알면 어디로든 갈 수 있음.

그리고 그 아래로 루트에서 시작되는 노드들을 '자식 노드'라고 함.

 

이진 탐색 트리의 장점

- 포인터를 이용했기 때문에 기존 연결 리스트의 역동성(dynamic)도 가지고 이진 탐색도 가능해졌음

- 이 트리의 높이는 로그를 따른다 O(n)보다 적게 걸림 

- 재귀에 가장 적합한 방법 

- 2차원 적이고 재귀적으로 정의되어있다 (어떤 노드에서라도 왼쪽이 더 작고 오른쪽이 더 크다는 것)

 

 

이진 탐색 트리의 구조를 이용하여 50을 찾는 방법. 재귀에 가장 적합한 방법이란 말이 이해가 가쥬?

 

bool search(node *tree)
{
	if (tree = NULL)
    {
    	return false;
    }
    else if (50 < tree->number)
    {
    	return search(tree->left);
    }
    else if (50 > tree->number)
    {
    	return search(tree->right);
    }
    else
    {
    	return true;
    }
}

 

이진 탐색 트리의 탐색 속도  : O(log n)

 

이로써 연결 리스트의 단점을 보완했다!

대신 저장해야 하는 포인터가 늘었으니 연결 리스트에 비해 필요한 메모리도 더 많아짐.

 

※ 이 글은 edwith의 [부스트코스] 모두를 위한 컴퓨터과학을 듣고 작성되었습니다.