🚂 배열(Array) · 동적 배열(Dynamic Array) · 연결 리스트(Linked List) 비교 정리

가장 기본적이면서도 자주 등장하는 선형 자료구조 3가지 배열, 리스트, 링크드 리스트에 대해 알아보자.
 

1. 배열 (Array) 

배열이란 같은 타입의 데이터를 연속된 메모리 공간에 저장하는 자료구조이다. 
 

각 요소는 인덱스를 통해 접근할 수 있으며 인덱스는 0부터 시작한다.
 

특징 

• 고정된 크기

  배열은 생성 시 크기를 지정해야 하며 한 번 정해진 크기는 변경할 수 없다.

• 인덱스를 통한 빠른 접근

  배열은 인덱스를 사용하여 특정 위치의 값을 O(1) 시간에 바로 접근할 수 있다.

• 연속된 메모리 공간을 사용

  배열은 메모리상에 데이터가 연속적으로 배치되어 있어 캐시 적중률이 높고 퍼포먼스가 좋다.

• 삽입/삭제에 비효율적

  중간에 데이터를 삽입하거나 삭제하면 뒤의 요소들을 모두 이동시켜야 하므로 성능이 떨어질 수 있다.
   

  시간 복잡도

  

   

동적 배열(Dynamic Array)과 연결 리스트(Linked List)를 알아보기 전에 리스트가 무엇인지 알아보자.
 

리스트(List)란?

리스트는 순서가 있는 원소들의 모음이며 다음과 같은 연산을 지원하는 추상 자료형(ADT)이다.
 

• get(i) - i 번째 요소 조회
• insert(i, x) - i 번째 위치에 x 삽입
• delete(i) - i 번째 요소 삭제
• append(x) - 맨 뒤에 x 추가
• length() - 전체 길이 반환

즉 동적 배열과 링크드 리스트는 모두 이 리스트란 추상 개념을 서로 다른 방식으로 구현한 것이다.
 

2. 동적 배열 (Dynamic Array)

동적 배열은 크기가 고정된 배열의 한계를 극복하기 위해 만들어진 자료구조이다. 처음에는 일정한 크기로 시작하지만 저장 공간이 부족해지면 더 큰 배열을 새로 만들고 기존 데이터를 복사하여 자동으로 크기를 확장한다.

대표적인 동적 배열로는 Java의 ArrayList, Python의 list, JavaScript의 Array가 있다.

특징

• 배열과 유사

  기본적으로는 배열이기 때문에 인덱스를 통한 빠른 접근, 삽입/삭제에 비효율적이라는 부분은 동일하다.

• 동적인 크기 조절

  배열이 가득 차면 더 큰 배열을 새로 만들고 복사하여서 자동으로 크기를 확장한다.
   

  시간 복잡도

  

   

3. 연결 리스트 (Linked List)

연결 리스트는 데이터를 저장할 때 배열처럼 연속된 공간에 저장하지 않고 각 요소(노드)가 다음 요소를 포인터를 통해 가리키는 방식으로 연결된 선형 자료구조이다.

각 노드는 값과 다음 노드의 주소를 포함하며 구조에 따라 단일 연결 리스트(Singly Linked List), 이중 연결 리스트(Doubly Linked List), 원형 연결 리스트(Circular Linked List)로 나뉜다.
 

특징

• 비연속 메모리

  배열처럼 메모리 공간이 연속될 필요 없이 노드끼리 포인터로 연결된다.

• 삽입/삭제에 효율적

  중간 삽입/삭제 시 포인터만 조정하면 되므로 위치를 알고 있을 경우 비용이 낮다.

• 접근에 비효율적

  임의의 위치에 접근하려면 처음부터 순차 탐색해야 하기 때문에 비효율적이다.

• 메모리 오버헤드

  각 노드마다 데이터를 저장하는 공간 외에 포인터 공간이 추가로 필요하다.
   

시간 복잡도