들어가기 전에
우리는 여러 자료형의 데이터를 메모리 상에 저장하고 읽고 삭제하는 방법을 배웠습니다. 컴퓨터 프로그램은 이러한 데이터를 이용해서 다양한 작업을 수행할 수 있습니다. 하지만 좀 더 복잡한 프로그램을 구현하다 보면 기본적인 포인터 구조만 이용해서 메모리를 관리하기에는 다소 번거로울 때가 많습니다. 만약 메모리를 좀 더 효율적으로 관리하고 사용할 수 있다면 어떨까요? 이번 강의에서는 데이터 구조의 개념과 연결 리스트에 대해 알아보겠습니다.
학습 목표
연결 리스트의 정의를 설명할 수 있습니다.
핵심 단어
강의 듣기
데이터 구조는 우리가 컴퓨터 메모리를 더 효율적으로 관리하기 위해 새로 정의하는 구조체입니다.
일종의 메모리 레이아웃, 또는 지도라고 생각할 수 있습니다.
이번 강의에서는 데이터 구조중 하나인 연결 리스트에 대해 알아보겠습니다.
배열에서는 각 인덱스의 값이 메모리상에서 연이어 저장되어 있습니다.
하지만 꼭 그럴 필요가 있을까요? 각 값이 메모리상의 여러 군데 나뉘어져 있다고 하더라도 바로 다음 값의 메모리 주소만 기억하고 있다면 여전히 값을 연이어서 읽어들일 수 있습니다.
이를 ‘연결 리스트’라고 합니다. 아래 그림과 같이 크기가 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를 사용하기 위함입니다.
생각해보기
연결 리스트를 배열과 비교했을 때 장단점은 무엇이 있을까요?
comment
배열은 한 번 선언하면 길이가 고정되지만 연결 리스트는 노드의 추가와 삭제가 가능하기 때문에 길이 가변이 가능하다.
연결 리스트는 배열에 비해 다음 값의 주소를 담는 공간이 더 필요하기 때문에
같은 크기의 데이터를 사용할 경우의 배열보다 더 많은 메모리 공간을 필요로 하는 것이 단점이다.
메모리의 효율적 사용은 가능하나, 시간이 오래 걸리고 메모리를 더 사용하게 되는 단점이 있음.
장점: 작성자가 자신의 의도대로 메모리 사용이 가능하다.
단점: 메모리 주소상 값이 연속되어 있지 않기 때문에 접근속도가 느려질 수 있다.
연결 리스트의 경우 리스트의 추가, 삭제가 배열에 비해 용이하다. 그러나 인덱스를 이용한 데이터 접근이 어려워 원하는 노드에 접근하기 위해 더 많은 시간이 소요된다.
배열은 원하는 데이터를 찾기 위해 인덱스를 이용하여 O(1)의 시간으로 접근할 수 있지만, 연결 리스트는 노드에 접근하기 위해 그 전 노드, 그 전 노드, 모두 거쳐가야 하기 때문에 최악의 경우 O(N)의 시간이 소요된다.
장: 메모리의 효율적 사용
단: 접근시간 증가
연결 리스트
장점
- 리스트의 크기를 동적으로 변경이 가능하다.
- 요소 추가, 삭제가 자유롭다.
- 어느 자료형이라도 넣을수 있다.
단점
- 연속된 메모리에 저장되지 않으므로 랜덤 접근이 불가능하고 순차적 접근만 가능하다
배열
장점
- 연속된 메모리 공간이기 때문에 랜덤 접근이 가능해서 탐색 속도가 매우 빠르다
- 연결리스트에 비해 차지하는 메모리 공간이 적다
단점
- 요소들이 모두 같은 자료형이여야한다.
- 요소의 추가/삭제할때 새로운 배열을 선언해서 데이터를 옮겨야한다.
- 배열에 할당된 메모리를 모두 사용하지 않는 경우 메모리 낭비가 될수 있다.
연결 리스트
- 장점
1. 동적 크기 조절: 동적으로 크기를 조절할 수 있어 메모리를 효율적으로 사용할 수 있음
2. 중간 삽입 및 삭제 효율적: 중간에 요소를 추가하거나 삭제할 때 다른 요소들을 옮길 필요가 없어 효율적
- 단점
1. 접근 시간 오버헤드: 특정 인덱스에 접근하려면 처음부터 순차적으로 접근해야 함.
2. 메모리 오버헤드: 각 요소는 다음 요소를 가리키는 포인터를 가지고 있어 메모리 오버헤드가 발생할 수 있음.
3. 캐시 지역성 부족: 연결 리스트는 각 노드가 불연속적인 메모리에 할당되므로 캐시 지역성이 떨어져 성능 저하가 발생할 수 있음.
배열
- 장점
1. 빠른 접근: 인덱스를 사용하여 원하는 원소에 빠르게 접근할 수 있음
2. 메모리 효율: 연속된 메모리 공간에 요소들이 저장되기 때문에 캐시 지역성이 좋아져 성능이 향상될 수 있음
- 단점
1. 크기 고정: 배열은 생성 시 크기가 고정되므로 동적인 크기 조절이 어려울 수 있음
2. 메모리 낭비: 배열은 크기를 지정하면서 더 큰 공간을 할당하므로, 모든 공간을 사용하지 않을 수 있음
3. 삽입 및 삭제 오버헤드: 중간에 요소를 삽입하거나 삭제할 경우, 이후의 모든 요소를 이동시켜야 함.
따라서 연결 리스트와 배열은 각각의 상황에 따라 적절하게 선택되어야 함. 배열은 빠른 접근이 중요한 경우 유용하며, 연결 리스트는 동적 크기 조절이나 중간 삽입/삭제가 빈번한 경우에 효과적임.
배열은 인덱스로 메모리 주소에 직접 접근이 가능하므로, 조회에 장점이 있습니다.
연결리스트는 배열의 단점인 할당 크기가 고정됐다는 단점을 극복하여, 새로운 공간에 메모리를 추가함으로써 동적으로 메모리 재할당에 용이합니다. 그러나, 주소값을 저장하기 위해 각 노드 당 1byte를 추가로 사용해야 합니다.
배열의 경우 연속적인 메모리를 사용해야 사용이 가능한데, 연결 리스트의 경우 메모리의 next 주소 값을 참조하기 때문에 메모리를 추가 삭제 하기에 유연하고 필요한 데이터의 숫자가 정확하지 않은 상황에서 늘리기 쉬울 거 같습니다.
단점으로는, 배열 처럼 [index]로 접근이 되지 않아 접근 할때 next 주소 값을 체크해야 되는 번거로움이 있을 수 있을거 같습니다.
장점: 유연한 확장
단점: 인덱스에 접근하는데 걸리는 시간
장점은 메모리를 연속적으로 쓰지 않아도 되서 남는 메모리 공간을 사용하여 동적으로 크기를 조절할 수 있다는 것이다.
단점은 배열과 달리 node구조체를 따로 정의해야하고, 배열의 요소에 해당하는 값과 다음 node를 가르키는 포인터도 같이 저장해야하기 때문에 메모리를 더 사용하게 된다.
장점: 메모리 공간이 부족할 때 여기 저기 비어 있는 공간을 사용한 다음 하나로 관리할 수 있음.
단점: 다음 배열을 가리키는 주소까지 같이 저장해야 하기 때문에 용량이 커짐.
malloc을 통해 힙 영역에서 가변 크기의 데이터 저장 공간을 확보할 수 있으므로,
배열과 달리 상황에 따라 필요한 만큼의 데이터만 사용하는 용량 효율적인 프로그래밍이 가능합니다. 확장성도 용이합니다.
연결 리스트를 배열과 비교했을 때 장점은 새로운 데이터를 추가 및 기존 데이터의 삭제가 용이하다는 것입니다.
단점은 어떤 데이터를 찾기 위해 순차적으로 탐색해야 해서 속도가 느리고 메모리 용량이 더 필요하다는 것입니다.
배열은 검색 (인덱싱) 부분에서 빠르다는 장점이 있고, 연결 리스트는 삽입과 삭제 부분에서 빠르다는 장점이 있습니다. 단점은 서로의 장점의 반대 입니다.
연결 리스트의 장점
1. 연결리스트는 동적으로 크기를 조정할 수 있으며, 새로운 요소를 삽입하거나 삭제하는 데 유연성을 제공한다. 배열은 크기가 고정되어 있기 때문에 크기를 동적으로 변경할 수 없다.
2. 연결 리스트는 특정 위치에 노드를 삽입하거나 삭제하는 작업이 배열보다 효율적이다. 반면 배열은 삽입 및 삭제 시 데이터의 이동이 필요하므로 비용이 크다.
3. 연결 리스트는 메모리를 동적으로 할당하고 해제하기 때문에 메모리 단편화 문제가 발생하지 않는다.
연결 리스트의 단점
1. 연결 리스트 각 노드에는 추가적인 링크 정보가 필요하므로 메모리 오버헤드가 발생할 수 있다 반면에 배열은 데이터만 저장하므로 메모리 사용량이 더 적다.
2. 연결 리스트는 특정 위치에 있는 요소에 접근하기 위해 순차적으로 탐색해야 한다. 반면에 배열은 인덱스를 사용하여 상수 시간에 랜덤 액세스가 가능하다.
추가 및 삭제 연산이 더 유리하다는 장점이 있지만 랜덤 접근을 못한다는 단점이 있습니다.
떨어져있는 메모리공간을 효율적으로 사용할 수 있게 해준다.
연결리스트는 배열보다 삭제와 삽입이 용이하다
하지만 각 요소에 접근하는 것은 배열보다 까다롭다