[CS50] 연결리스트 : 도입

지금까지 여러 자료형의 데이터를 메모리에 저장하고, 읽고, 삭제하는 방법에 대해 공부했었습니다. 그런데 만약 프로그램이 복잡해지거나 양이 방대해진다면 기본적인 포인터 구조만으로는 메모리를 관리하기에 다소 번거로울 겁니다. 그래서 오늘은 메모리를 더 효율적으로 관리하고 사용하기 위한 데이터의 개념과 연결 리스트에 대해 공부해보도록 하겠습니다.

 

데이터 구조란

우리가 컴퓨터 메모리를 효율적으로 관리하기 위해 새로 정의하는 구조체입니다.

이 데이터 구조중 하나인 연결 리스트는 배열과 다르게 각 값이 메모리에 여러군데 나누어져 있더라도 다음 값의 메모리 주소만 기억한다면 배열처럼 값을 연이어서 읽어 들일 수 있게 해 주는 것을 말합니다.

이렇게 각각의 번호가 떨어져 있더라도

포인터를 이용해서 자신의 값과함께 바로 다음 값의 주소를 저장하기 때문에 가능합니다.

여기서 잠깐 눈여겨 볼만한건 1과 2는 각각 2의 주소 3의 주소를 함께 저장하고 있지만 3의 경우는 어떻게 할까요?

3의 경우에는 다음값이 없기 때문에 NULL을 다음 값의 주소로 저장하면 됩니다.

 

 

연결 리스트를 간단한 코드로 정리해보면

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

형태로 정의할 수 있습니다.

node라는 이름의 구조체는 number와 *next 두 개의 필드가 함께 정의되어있고, number는 각 node가 가지는 값, *next는 다음 node를 가리키는 포인터가 됩니다. 첫 줄에 typeof struct가 아닌 typeof struct node라고 'node'를 함께 명시해주는건 구조체 안에서 node를 사용하기 위해서입니다.

 

 

*** node가 많아 조금 헷갈리시다면 node를 x나 y등 다른 문자로 바꿔보세요 ㅎㅎ

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

위와 같은 의미를 가집니다.

 

---

출처

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

 

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