배열(Array)과 연결 리스트(Linked List)는 선형 자료구조를 대표하는 가장 기본적인 두 가지 구조다. 두 자료구조는 모두 데이터를 순차적으로 저장한다는 공통점을 가지지만, 내부 구조와 동작 방식, 성능 특성은 크게 다르다. 이 차이로 인해 같은 문제라도 어떤 자료구조를 선택하느냐에 따라 실행 속도와 메모리 효율이 크게 달라질 수 있다. 특히 2026년 기준으로 코딩 테스트, 자료구조 학습, 실무 개발 환경에서 배열과 연결 리스트의 차이를 명확히 이해하는 것은 필수 역량으로 여겨진다. 이 글에서는 배열과 연결 리스트의 개념부터 구조적 특징, 장단점, 활용 기준까지 체계적으로 비교 설명한다.
배열(Array)의 구조와 특징
배열은 동일한 타입의 데이터를 연속된 메모리 공간에 저장하는 선형 자료구조다. 각 데이터는 인덱스(index)를 통해 관리되며, 이 인덱스를 이용해 특정 위치의 데이터에 즉시 접근할 수 있다. 이러한 구조 덕분에 배열은 접근 속도가 매우 빠르다는 큰 장점을 가진다.
배열의 가장 핵심적인 특징은 임의 접근(Random Access)이 가능하다는 점이다. 예를 들어 n번째 요소에 접근할 때 반복적인 탐색 없이 단 한 번의 연산으로 해당 데이터에 접근할 수 있다. 이로 인해 탐색과 조회가 빈번한 상황에서 매우 효율적으로 동작한다.
하지만 배열에는 명확한 단점도 존재한다. 대부분의 배열은 크기가 고정되어 있어, 처음 선언한 크기보다 많은 데이터를 저장하기 어렵다. 또한 배열의 중간에 데이터를 삽입하거나 삭제할 경우, 뒤에 있는 모든 요소를 한 칸씩 이동시켜야 하므로 시간 복잡도가 크게 증가한다. 이러한 특성 때문에 배열은 데이터의 개수가 자주 변하지 않는 상황에 적합하다.
연결 리스트(Linked List)의 구조와 특징
연결 리스트는 각 데이터 요소가 노드(Node) 단위로 구성되며, 각 노드는 데이터와 다음 노드를 가리키는 포인터를 함께 저장한다. 이로 인해 데이터가 메모리 상에서 반드시 연속적으로 저장될 필요가 없다. 노드들은 포인터를 통해 논리적으로 연결된다.
연결 리스트의 가장 큰 장점은 삽입과 삭제가 매우 유연하다는 점이다. 특정 위치에 새로운 데이터를 추가하거나 기존 데이터를 제거할 때, 포인터 연결만 변경하면 되기 때문에 배열처럼 대규모 데이터 이동이 발생하지 않는다. 이로 인해 데이터의 추가와 삭제가 빈번한 상황에서 매우 효율적인 구조다.
반면 연결 리스트는 배열과 달리 임의 접근이 불가능하다. 특정 위치의 데이터를 찾기 위해서는 첫 번째 노드부터 차례대로 탐색해야 하므로 접근 속도가 느리다. 또한 각 노드가 포인터 정보를 추가로 저장해야 하기 때문에 배열보다 메모리 사용량이 더 많다는 단점도 존재한다.
배열(Array)과 연결 리스트(Linked List)의 성능 비교
배열과 연결 리스트의 차이는 시간 복잡도와 공간 복잡도 측면에서 명확하게 드러난다. 배열은 인덱스를 이용한 접근이 가능하므로 조회 연산에서 매우 빠른 성능을 보인다. 반면 연결 리스트는 순차 탐색이 필요해 조회 성능은 상대적으로 떨어진다.
삽입과 삭제 연산에서는 상황이 반대가 된다. 배열은 중간 삽입이나 삭제 시 많은 데이터 이동이 필요해 비효율적이지만, 연결 리스트는 포인터만 수정하면 되므로 훨씬 효율적이다. 이러한 차이로 인해 두 자료구조는 사용 목적에 따라 명확히 구분되어야 한다.
메모리 측면에서도 차이가 존재한다. 배열은 데이터만 저장하므로 메모리 구조가 단순하지만, 연결 리스트는 포인터 정보를 추가로 저장해야 하므로 메모리 사용량이 상대적으로 크다. 따라서 메모리 제약이 있는 환경에서는 배열이 더 적합할 수 있다.
어떤 상황에서 어떤 자료구조를 선택해야 할까?
배열은 데이터의 개수가 고정되어 있거나 변경이 거의 없고, 조회와 탐색이 빈번한 상황에 적합하다. 예를 들어 점수 목록, 좌표 데이터, 정적 테이블과 같은 구조에서는 배열이 매우 효율적이다.
반면 연결 리스트는 데이터의 추가와 삭제가 자주 발생하고, 데이터의 크기를 미리 예측하기 어려운 상황에 적합하다. 큐, 스택, 실시간 데이터 처리 구조 등에서는 연결 리스트가 더 유연한 선택이 된다.
코딩 테스트와 알고리즘 문제에서는 배열이 기본 선택인 경우가 많지만, 문제 조건에 따라 연결 리스트의 특성을 요구하는 경우도 있다. 따라서 두 구조의 차이를 단순 암기가 아닌 활용 관점에서 이해하는 것이 중요하다.
결론
배열과 연결 리스트는 모두 선형 자료구조이지만, 내부 구조와 성능 특성은 매우 다르다. 배열은 빠른 접근 속도를 제공하는 대신 유연성이 떨어지고, 연결 리스트는 유연한 삽입과 삭제가 가능한 대신 접근 속도가 느리다. 문제 상황과 요구 사항에 따라 적절한 자료구조를 선택하는 능력은 자료구조 학습의 핵심이다. 이 두 구조를 정확히 이해하면 이후 스택, 큐, 트리와 같은 자료구조 학습도 훨씬 수월해진다.