[CS50] 자료구조: 연결 리스트 - 도입
❄️ David Malan 교수의 모두를 위한 컴퓨터 과학(CS50 2019)을 바탕으로 정리한 내용입니다.
데이터 구조는 우리가 컴퓨터 메모리를 더 효율적으로 관리하기 위해 새로 정의하는 구조체입니다.
일종의 메모리 레이아웃, 또는 지도라고 생각할 수 있습니다.
이번 강의에서는 데이터 구조중 하나인 연결 리스트에 대해 알아보겠습니다.
배열에서는 각 인덱스의 값이 메모리상에서 연이어 저장되어 있습니다.
하지만 꼭 그럴 필요가 있을까요?
각 값이 메모리상의 여러 군데 나뉘어져 있다고 하더라도 바로 다음 값의 메모리 주소만 기억하고 있다면 여전히 값을 연이어서 읽어들일 수 있습니다.
이를 ‘연결 리스트’라고 합니다.
아래 그림과 같이 크기가 3인 연결 리스트는 각 인덱스의 메모리 주소에서 자신의 값과 함께 바로 다음 값의 주소(포인터)를 저장합니다.
연결 리스트의 가장 첫 번째 값인 1은 2의 메모리 주소를, 2는 3의 메모리 주소를 함께 저장하고 있습니다.
3은 다음 값이 없기 때문에 NULL (\0, 즉 0으로 채워진 값을 의미합니다)을 다음 값의 주소로 저장합니다.
연결 리스트는 아래 코드와 같이 간단한 구조체로 정의할 수 있습니다.
typedef struct node
{
int number;
struct node *next;
}
node;
node 라는 이름의 구조체는 number 와 *next 두 개의 필드가 함께 정의되어 있습니다.
number는 각 node가 가지는 “값”, *next 는 다음 node를 가리키는 “포인터”(주소)가 됩니다.
여기서 typedef struct 대신에 typedef struct node 라고 “node”를 함께 명시해 주는 것은, 구조체 안에서 node를 사용하기 위함입니다.
생각해보기
연결 리스트를 배열과 비교했을 때 장단점은 무엇이 있을까요?
장점
물리적 공간에 구애받지 않기 때문에 컴퓨터 내의 공간을 더 유동적으로 사용할 수 있습니다.
요소의 추가/삽입에 용이합니다.
단점
다음 node를 가르키는 포인터도 같이 저장해야하기 때문에 메모리를 더 사용하게 됩니다.
인덱스로 메모리 주소에 접근할 수 없기 때문에 조회하는데 많은 시간이 걸립니다.
💛 개인 공부 기록용 블로그입니다. 👻