연결 리스트 : 도입

들어가기 전에

우리는 여러 자료형의 데이터를 메모리 상에 저장하고 읽고 삭제하는 방법을 배웠습니다. 컴퓨터 프로그램은 이러한 데이터를 이용해서 다양한 작업을 수행할 수 있습니다. 하지만 좀 더 복잡한 프로그램을 구현하다 보면 기본적인 포인터 구조만 이용해서 메모리를 관리하기에는 다소 번거로울 때가 많습니다. 만약 메모리를 좀 더 효율적으로 관리하고 사용할 수 있다면 어떨까요? 이번 강의에서는 데이터 구조의 개념과 연결 리스트에 대해 알아보겠습니다.

 

학습 목표

연결 리스트의 정의를 설명할 수 있습니다.

 

핵심 단어

• 연결 리스트

 

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

일종의 메모리 레이아웃, 또는 지도라고 생각할 수 있습니다.

이번 강의에서는 데이터 구조중 하나인 연결 리스트에 대해 알아보겠습니다.

 

배열에서는 각 인덱스의 값이 메모리상에서 연이어 저장되어 있습니다.

하지만 꼭 그럴 필요가 있을까요? 각 값이 메모리상의 여러 군데 나뉘어져 있다고 하더라도 바로 다음 값의 메모리 주소만 기억하고 있다면 여전히 값을 연이어서 읽어들일 수 있습니다.

이를 ‘연결 리스트’라고 합니다. 아래 그림과 같이 크기가 3인 연결 리스트는 각 인덱스의 메모리 주소에서 자신의 값과 함께 바로 다음 값의 주소(포인터)를 저장합니다.

 

 

연결 리스트의 가장 첫 번째 값인 1은 2의 메모리 주소를, 2는 3의 메모리 주소를 함께 저장하고 있습니다.

3은 다음 값이 없기 때문에 NULL (\0, 즉 0으로 채워진 값을 의미합니다)을 다음 값의 주소로 저장합니다. 

 

연

결 리스트는 아래 코드와 같이 간단한 구조체로 정의할 수 있습니다. 

node 라는 이름의 구조체는 number 와 *next  두 개의 필드가 함께 정의되어 있습니다.

number는 각 node가 가지는 값, *next 는 다음 node를 가리키는 포인터가 됩니다.

여기서 typedef struct 대신에 typedef struct node 라고 ‘node’를 함께 명시해 주는 것은, 구조체 안에서 node를 사용하기 위함입니다.

 

 

생각해보기

연결 리스트를 배열과 비교했을 때 장단점은 무엇이 있을까요?

 

나의 생각  :  장점 - 저장되는 값들의 변화가 많을 때 배열은 메모리를 새로 할당해주고 복사를 해줘야하는데 연결리스트는 노드를 추가해주기만 하면돼서 배열보다 효과적이다.

                 단점 - 메모리를 더 많이 차지하고 찾는데 시간이 오래 걸릴 수 있다.

 

출처 : https://www.boostcourse.org/cs112/lecture/119038?isDesc=false 네이버커넥트재단