[CS][CS50] 자료구조 - 연결 리스트 / 트리 / 해시 테이블

boostcource
모두를 위한 컴퓨터 과학 (CS50 2019) : David J. Malan
www.boostcourse.org/cs11
실습환경 : CS50 Sandbox & CS50 IDE

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

 

자료 구조

자료 구조(데이터 구조)는 컴퓨터 메모리를 더 효율적으로 관리하기 위해 새로 정의하는 구조체로

일종의 메모리 레이아웃 또는 지도로 생각하면 된다.

자료 구조 중에는 연결 리스트, 해시 테이블, 트라이, 스택, 큐, 딕셔너리 등이 존재한다.

 

 

 

---

연결 리스트

연결 리스트는 각 값이 메모리 상의 여러 군데에 나누어져 존재하지만

바로 다음 값의 메모리 주소를 기억하고 있어 배열과 비슷하게 값을 연이어 읽을 수 있는 자료 구조이다. 

 

 

• 배열: 각 값이 메모리 상에서 연이어 저장되어 있다. (인덱스가 연속적이다.)

[출처] 모두를 위한 컴퓨터 과학 (CS50  2019) 3-5

• 연결 리스트: 각 값이 메모리 상에서 따로 따로 저장되어 있다.

[출처] 모두를 위한 컴퓨터 과학 (CS50 2019) 6-3

연결 리스트의 가장 첫 번째 값인 1은 2의 메모리 주소(0x456)를 저장,

2는 3의 메모리 주소(0x789)를 저장,

3은 다음 값이 없기 때문에 NULL(\0)을 다음 값의 주소로 저장한다.

 

 

코드로 연결 리스트를 정의하면 아래와 같다. 

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

typedef strcut 를 이용해 구조체 node를 선언한다.

필드 number 는 int 자료형으로 받은 각 node가 가지는 값이고

필드 *next 는 다음 node를 가리키는 포인터다.

 

+) typedef struct { ... } 대신에 typedef struct node { ... } 라고 node를 명시해주는 이유는

구조체 내부에서 node를 사용하기 위함이다.

 

 

배열과 비교했을 때의 장단점

장점

• 연결 리스트는 다음 값이 저장된 메모리 주소만 알면 되기 때문에 같은 자료형을 연결할 필요가 없다.
  즉, 배열과 달리 여러 자료형의 값을 이용할 수 있다.
• 배열은 고정된 개수만 저장 가능하지만, 연결 리스트는 필요 시 데이터를 유동적으로 추가할 수 있다.
  새로운 항목을 만들고 포인터의 값만 변경하면 되기 때문에 삽입이 간단하다.

단점

• 위치를 나타낼 때 인덱스 사용이 불가능하기에 순차적으로 접근해야 한다.
  즉, 배열과 비교해 각 항목 접근하는 데 오랜 시간이 걸린다.
  • 연결 리스트의 크기가 n 일때 새로운 값을 추가하거나 검색하려면 실행 시간은 O(n)
  • 배열의 경우는 이진 검색을 이용해 실행 시간이 O(log n)
• 데이터와 다음 값의 메모리 주소를 함께 저장해야 하므로 메모리가 추가로 소비된다.

 

이처럼 여러 데이터 구조는 각자의 장단점이 존재하기 때문에

프로그래밍을 할 때는 목적에 부합하는 가장 효율적인 데이터 구조를 고민해 사용하는 것이 중요하다.

 

 

 

---

연결 리스트 구현하기

연결 리스트를 C언어를 이용해 구현해보자.

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

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

int main(void){
    node *list = NULL; // 연결 리스트의 첫 번째 node 포인터 list. 현재 아무것도 가리키고 있지 않음

    node *n = malloc(sizeof(node)); // 새로운 node 포인터 n. 메모리 할당 완료
    if(n == NULL){
        return 1;
    }
    n -> number = 1; // node n 의 number 필드의 값으로 1 저장. (*n).number = 1; 과 동일
    n -> next = NULL; // node n의 next 값으로 NULL 저장
    list = n; // list 포인터를 n 포인터로 초기화
    

    n = malloc(sizeof(node)); // list에 다른 node를 더 연결하기 위해 n에 새로운 매모리 재할당
    if(n == NULL){
        return 1;
    }
    n -> number = 2; // node n의 number 값으로 2 저장
    n -> next = NULL; // node n의 next 값으로 NULL 저장
    list -> next = n; // node list의 next 값으로 n 저장. list의 다음 node로 n 포인터가 지정됨


    n = malloc(sizeof(node)); // list에 다른 node를 더 연결하기 위해 n에 새로운 매모리 재할당
    if(n == NULL){
        return 1;
    }
    n -> number = 3; // node n의 number 값으로 3 저장
    n -> next = NULL; // node n의 next 값으로 NULL 저장
    list -> next -> next = n; // node list의 다음 node의 다음 node로 n 포인터가 지정됨


    // list에 연결된 node들을 처음부터 방문하면서 각 number 출력
    // 마지막 node의 next에 NULL이 저장되어 있음을 루프의 종료 조건으로 활용
    for(node *tmp = list; tmp != NULL; tmp = tmp->next){
        printf("%i\n", tmp -> number);
    }
    // ? 1
    // ? 2
    // ? 3


    // list에 연결된 node들을 처음부터 방문하면서 메모리 해제
    while(list != NULL){
        node *tmp = list -> next;
        free(list);
        list = tmp;
    }
}

 

 

(응용) 중간에 새로운 노드 추가하기

두 번째 노드(number = 2)와 세 번째 노드(number = 3) 사이에

새로운 노드(number = 5) 를 추가해보자

n = malloc(sizeof(node)); // 새로운 node
if(n == NULL){
	return 1;
}
n -> number = 5; // 새로운 node의 number는 5
n -> next = NULL;
for(node *tmp = list; tmp != NULL; tmp = tmp -> next) {
	// number가 2인 두 번째 node와 number가 3인 세 번째 node 사이에 넣기 위한 조건문
	if(tmp -> number == 2) {
		n -> next = tmp -> next;
		tmp -> next = n;
		break;
	}
}

// 루프를 이용해 list에 연결된 node들 하나씩 출력해 확인
for(node *tmp = list; tmp != NULL; tmp = tmp->next){
	printf("%i\n", tmp -> number);
}
// ? 1
// ? 2
// ? 5
// ? 3

 

 

(응용) 중간에 노드 삭제하기

두 번째 노드(number = 2)를 삭제해보자

list -> next = list -> next -> next;

// 루프를 이용해 list에 연결된 node들 하나씩 출력해 확인
for(node *tmp = list; tmp != NULL; tmp = tmp->next){
	printf("%i\n", tmp -> number);
}
// ? 1
// ? 3

 

 

 

---

트리

연결 리스트에서는 각 요소가 다른 요소 하나씩만을 가리킨다.

연결 리스트를 활용한 데이터 구조인 트리는 각 요소가 여러개의 요소를 가리킨다.

 

[출처] https://www.geeksforgeeks.org/binary-tree-data-structure/

 

연결 리스트는 각 노드들의 연결이 1차원적 구성이라면, 트리는 2차원적 구성이다.

각 노드는 일정한 층에 속하고

다음 층의 노드들을 가리키는 포인터를 가진다.

 

가장 높은 층에서 트리가 시작되는 노드인 루트 노트(root node)가 존재하고

그 다음 층의 노드들을 자식 노드라고 칭한다.

 

 

이진 검색 트리

[출처] 모두를 위한 컴퓨터 과학 (CS50 2019) 6-6

위는 트리 중에서도 이진 검색 트리다.

 

하나의 노드가 두개의 자식 노드를 가지며

왼쪽 자식 노드는 자신보다 작은 값을, 오른쪽 자식 노드는 자신보다 큰 값을 가진다.

 

이진 검색 트리는 이름처럼 이진 검색을 수행하는데 유리하다.

 

 

이진 검색 트리의 노드 구제체는 아래와 같이 구현 가능하다.

// 이진 검색 트리의 노드 구조체
typedef struct node {
    int number;
    struct node *left; // 왼쪽 자식 노드
    struct node *right; // 오른쪽 자식 노드
}
node;

그리고 "50"을 재귀적으로 검색하는 이진 검색 함수는 아래와 같이 구현할 수 있다.

// 이진 검색 함수
// (*tree는 이진 검색 트리를 가리키는 포인터)
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) 이다.

때문에 기본 연결 리스트(O(n))보다 값을 검색할 때 실행 시간이 적게 소모된다는 장점이 있다.

다만, 포인터를 2개 가지기 때문에 기본 연결 리스트에 비해 메모리를 더 많이 차지한다.

 

 

 

---

해시 테이블

해시 테이블은 연결 리스트의 배열이다.

 

여러 값들을 몇 개의 바구니에 나눠 담는 상황을 상상해보자.

각 값들은 해시 함수라는 맞춤형 함수를 통해서 어떤 바구니에 담기는 지가 결정된다.

그리고 각 바구니에 담기는 값들을 그 바구니에서 새롭게 정의되는 연결 리스트로 연결된다.

즉, 연결 리스트가 담긴 여러개의 바구니가 해시 테이블이다.

 

 

더 구체적인 예시로 살펴보자.

다음은 사람들의 이름들을 이름의 가장 첫 글자를 기준으로 나누고

같은 첫 글자를 가진 이름들끼리는 연결 리스트를 구성한 예시이다.

[출처] 모두를 위한 컴퓨터 과학 (CS50 2019) 6-7

이 때 이름의 가장 첫 글자가 해시 함수이며 알파벳 개수에 해당하는 26개의 포인터들이 존재하는 셈이다.

각 포인터는 그 알파벳으로 시작하는 이름들을 저장하는 연결 리스트를 가리킨다..

 

 

 

해시 함수를 정의하는 대표적인 것들에는 자릿 수 선택(digit selection), 자릿수 접기(digit folding), 모듈로 연산(modulo function), 분할 방법(division method) 등이 존재한다

 

만일 해시 함수가 이상적이라면, 각 바구니에는 단 하나의 값들만 담길 것이기 때문에 검색 시간은 O(1)이 된다.

하지만 하나의 바구니에 모든 값들이 담기는 최악의 경우가 존재하기에 O(n)이 될 수도 있다.

일반적으로는 최대한 많은 바구니를 만들 수 있도록 해시 함수를 사용하기에 O(1)에 가깝다고 볼 수 있다.

 

 

 

---

복습 퀴즈

Q1. 같은 크기를 가지는 배열과 리스트가 있다. 첫번째 값이 아닌 위치의 값에 접근하려고 할 때 소용되는 시간에 대한 설명으로 옳은 것은?

① 배열과 리스트 모두 동일하다.

② 배열이 리스트보다 더 빠르다.

③ 알 수 없다.

④ 리스트가 배열보다 더 빠르다.

답: ② 배열이 리스트보다 더 빠르다.

리스트는 처음부터 순차적으로 접근해야 하기 때문에 실행 시간이 O(n)이다.

배열은 정렬이 가능하기 때문에 이진 검색을 이용해 실행 시간이 O(log n)으로 리스트보다 빠르다.

 

 

Q2. node라는 구조체 안에 number 멤버가 정의되어 있다. node *n; 변수가 선언되어 있을 때 (*n).number 와 동일한 의미의 코드는?

답: n -> number

(*n).number = 1 은 n -> number = 1 과 같다.

 

 

Q3. 아래와 같이 영문자를 인덱스로 변환해 해시 테이블을 작성하려고 한다. 어떤 문자가 어떤 값이 될지 매핑하는 함수를 무엇이라고 하나요?

답: 해시 함수

해시 테이블은 해시 함수라는 맞춤형 함수를 가지며, 이는 각 연결 리스트를 가리키는 포인터가 된다.

 

 

Q4. 연결 리스트를 구현하기 위해 노드를 구조체로 정의하려고 한다. 노드에 입력될 숫자 number와 다음 노드를 가리키는 포인터 next를 정의하기 위해 괄호 안에 들어갈 코드는?

typedef struct node {
	int number;
	struct node ( /* 코드 */ );
}
node;

답: *next

다음 노드를 가리키는 포인터 next를 정의해야 하기 때문에 *을 붙인 *next 를 괄호 안에 작성해야 한다.