[자료구조] 리스트(List) 이해하기

리스트는 가장 빈번하게 사용되는 자료구조 중 하나입니다.

다량의 데이터를 다루는데 가장 단순한 방법이기 때문인데요.

 

기본적인 자료구조이다 보니 프로그래밍 언어들에 내장되어 있는 경우가 많습니다.

자주 사용하는 만큼 이론적인 부분도 중요하기 때문에 리스트(List)에 대해 정리해 보았습니다.

 

---

자료구조의 두 가지 구현 방법

자료구조는 구현 방법에 따라 크게 두 갈래로 분류할 수 있습니다.

바로 순차(Sequential) 자료구조와 연결(Linked) 자료구조입니다.

 

순차 자료구조는 구현할 자료들을 논리적인 순서대로 메모리에 연속하여 저장하는 자료구조입니다.

 

데이터가 컴퓨터 메모리에 저장될 때, 저장 시작 위치부터 빈자리 없이 순서대로 저장된다는 뜻인데요.

 

자료의 논리적인 순서와 물리적인 순서가 일치하는 구현 방식이라고 할 수 있습니다.

데이터가 연속된 메모리 공간 안에 존재. (int 타입이 4byte이므로 메모리 주소 4씩 증가)

 

반면 연결 자료구조는 메모리에 저장된 물리적 위치나 순서와 상관없이, 링크에 의해 논리적인 순서를 표현하는 자료구조입니다.

 

연속적인 메모리에 저장되는 방식이 아니라 노드라는 각각의 독립된 공간을 사용해 데이터를 담습니다.

 

노드는 실제 데이터가 저장되는 공간인 데이터 필드와 다음 노드의 주소 값을 가진 링크 필드로 이루어져 있습니다.

데이터가 메모리 상에서 연속적인 공간에 존재하지 않음.

 

리스트 역시 위의 두 가지 방법으로 구현할 수 있습니다.

순차 방식으로 구현한 리스트는 순차 리스트, 연결 방식으로 구현한 리스트는 연결 리스트라고 합니다.

 

사실 위의 그림은 순차 리스트와 연결 리스트의 그림입니다.

 

순차 리스트 vs 연결 리스트

그럼 리스트는 왜 두 가지로 구분되어 있을까요? 각 리스트의 차이점을 살펴보면 그 이유를 알 수 있습니다.

두 리스트는 데이터를 삽입·삭제 그리고 탐색하는 과정에서 뚜렷한 차이를 보입니다.

 

순차 리스트는 데이터를 삽입하거나 삭제하고 나면, 연속적인 물리적 위치를 유지하기 위해 원소를 옮기는 추가 작업을 해야 합니다.

 

따라서 삽입이나 삭제 연산이 많다면 그만큼 시간이 듭니다.

순차 리스트 삭제 과정

 

연결 리스트는 특정 노드를 삽입하거나 삭제할 때 노드의 링크 필드(다음 노드 주소)만 수정하면 되므로 순차 리스트에 비해 연산 속도가 빠른 것입니다.

연결 리스트의 삭제 과정

 

두 그림을 비교해 보면 순차 리스트는 데이터의 삭제 작업이 이루어진 뒤 원래 데이터가 담겨있던 주소에 변화가 생겼지만, 연결 리스트는 주소가 변경된 노드가 없습니다.

 

연결 리스트가 추가·삭제에서 더 효율적이었다면, 탐색은 순차 리스트가 더 효율적입니다.

 

순차 리스트는 배열로 구현하기 때문에 인덱스를 통해 원소를 탐색할 수 있지만, 연결 리스트는 이전 노드를 통해서만 다음 노드를 참조할 수 있다는 특성 때문에 리스트의 처음부터 다음 노드들을 탐색해야 하기 때문입니다.

 

결과적으로 추가·삭제에서는 연결 리스트가, 탐색에서는 순차 리스트가 더 효율적인 자료구조라고 할 수 있겠습니다.