[자료구조] 배열 기반 리스트 vs 포인터 기반 리스트

 

 자료구조에서 리스트는 데이터를 순차적으로 저장하는 기본 구조입니다. 리스트는 구현 방식에 따라 배열 기반 리스트(선형리스트)와 포인터 기반 리스트(연결리스트)로 나뉘며, 각 방식은 메모리 구성, 접근 속도, 삽입 및 삭제 성능에 차이를 보입니다.

 

 본 글에서는 이 두 리스트 구조의 차이점과 각각의 장단점, 그리고 실제 애플리케이션에서 어떻게 선택되고 활용되는지를 비교 분석해 보겠습니다.

배열 기반 리스트의 구조와 특징

 배열 기반 리스트는 가장 단순하고 직관적인 리스트 구조로, 데이터를 연속된 메모리 공간에 저장합니다.

 

 자바의 ArrayList, C언어의 배열, 파이썬의 리스트 등 대부분의 고수준 언어에서 기본 자료구조로 제공되며, 데이터에 인덱스로 직접 접근할 수 있어 빠른 읽기 성능을 자랑합니다.

int[] numbers = new int[5];
numbers[0] = 10;
numbers[1] = 20;

 

 이처럼 배열은 메모리에 연속적으로 저장되기 때문에, 특정 인덱스에 접근하는 데 시간 복잡도는 O(1)입니다. 그러나 새로운 요소를 중간이나 앞에 삽입하거나 삭제할 경우, 나머지 요소들을 모두 이동시켜야 하므로 시간 복잡도는 O(n)으로 증가합니다.

포인터 기반 리스트의 유연성과 성능

 포인터 기반 리스트, 즉 연결리스트는 각 데이터 노드가 자기 자신과 다음 노드를 연결하는 방식으로 구성됩니다. 이는 메모리에 데이터를 불연속적으로 저장하고, 노드 간을 포인터로 연결하는 구조입니다.

class Node {
    int data;
    Node next;
}

 

 이러한 구조는 메모리 사용에 매우 유연하며, 리스트의 크기를 동적으로 조절할 수 있는 장점이 있습니다.

 

 새로운 데이터를 리스트 중간에 삽입하거나 삭제할 경우, 단순히 포인터만 수정하면 되기 때문에 시간 복잡도는 O(1)로 빠른 성능을 유지할 수 있습니다.

 

 하지만 특정 인덱스에 있는 값을 찾으려면 앞에서부터 순회해야 하며, 이는 시간 복잡도 O(n)을 의미합니다. 또한 각 노드에 포인터가 추가로 필요하므로 메모리 오버헤드가 증가하고, 잘못된 포인터 참조로 인한 오류 발생 가능성도 존재합니다.

 

리스트 구조 선택 기준과 실무 예시

 실제 개발 환경에서는 리스트 구조를 선택할 때 데이터의 접근 방식과 연산 빈도를 기준으로 삼습니다.

항목	배열 기반 리스트	포인터 기반 리스트
메모리 구조	연속적	불연속적
접근 속도	빠름 (O(1))	느림 (O(n))
삽입/삭제 성능	느림 (O(n))	빠름 (O(1) ~ O(n))
메모리 낭비	있음 (남는 공간)	없음 (필요시 동적 생성)
구현 난이도	쉬움	비교적 어려움
예시	ArrayList, 정적 배열	LinkedList, 큐, 스택 등

 

 실제 예를 들어보면, 쇼핑몰의 상품 리스트 페이지는 배열 기반 리스트로 구현되어야 빠른 상품 조회가 가능하고, 채팅 앱의 메시지 큐는 연결리스트 기반으로 구성되어야 실시간 추가/삭제가 원활합니다.

 

 배열 기반 리스트와 포인터 기반 리스트는 각각 고유한 구조적 특징과 사용처를 가지고 있습니다.

 

 배열은 빠른 인덱스 접근과 단순한 구조로 읽기 중심 시스템에 적합하며, 포인터 기반 리스트는 유연성과 빠른 삽입/삭제를 통해 동적인 시스템에 적합합니다.

 

 코딩테스트는 물론 실무 개발에서도 어떤 리스트를 선택하느냐에 따라 성능과 유지보수성이 크게 달라질 수 있습니다.

 여러분도 프로젝트 요구사항에 맞는 리스트 구조를 선택하여 효율적인 자료구조 활용을 경험해 보시기 바랍니다.