Array vs LinkedList 특징 & 성능 비교

Array (배열)

특징

- 같은 타입의 여러 변수를 하나의 묶음으로 다루는 자료구조

- 물리적으로 연속적인 메모리 공간에 저장되며 크기가 고정되어 있다.

 

시간 복잡도

접근(Access)

- 배열은 무작위 접근(random access)이 가능하다.

- 인덱스를 알고 있는 경우 O(1)

 

검색(Search): 순차 접근이라고도 함

- 선형 검색(Linear Search): 정렬되어 있지 않은 배열에서 특정 값을 찾는 경우로 O(n)

- 이진 검색(Binary Search): 정렬된 배열에서 특정 값을 찾는 경우로 O(log n)

 

삽입(Insertion)

- 배열의 시작에 원소를 삽입하는 경우, 이후 요소들을 모두 한 칸씩 뒤로 이동시켜야 하므로 O(n)

배열 시작에 원소를 삽입하는 경우

- 배열의 중간에 원소를 삽입하는 경우, 이후 요소들을 모두 한 칸씩 뒤로 이동시켜야 하므로 O(n)

- 배열의 끝에 원소를 삽입하는 경우, 추가적인 요소 이동을 필요로 하지 않기 때문에 O(1)

    - 동적 배열의 경우, 배열이 가득찬 상태에서 요소가 추가될 경우 배열의 크기를 두 배로 늘리고 기존 요소들을 복사해야 하므로 O(n)

 

삭제(Deletion)

- 배열의 시작 원소를 삭제하는 경우, 이후 요소들을 모두 한 칸씩 앞으로 이동시켜야 하므로 O(n)

- 배열의 중간 원소를 삭제하는 경우, 이후 요소들을 모두 한 칸씩 앞으로 이동시켜야 하므로 O(n)

- 배열의 끝 원소를 삭제하는 경우, 추가적인 요소 이동을 필요로 하지 않기 때문에 O(1)

 

LinkedList (연결리스트)

특징

- Array와 비교했을 때 삽입/삭제 연산에 효율적인 자료구조

- Array가 물리적으로 연속적인 공간에 데이터를 저장한다면, LinkedList는 비연속적인 공간에 데이터를 저장하고 그 주소를 가리키는 포인터로 연결해서 관리한다.

- 새로운 원소가 추가될 때마다 동적으로 공간을 할당받아 비연속적인 메모리 공간에 추가한다.

- 데이터의 저장 단위인 노드로 구성되어 있고 각각의 노드는 "값"과 "포인터"(다음 노드를 가리키는 주소)를 가지고 있다.

    - "값"은 정수/실수와 같은 기초 타입이나 클래스의 객체가 될 수 있다.

 

시간 복잡도

접근(Access)

- 특정 인덱스에 위치한 원소에 접근하는 경우, 처음부터 순회하여 해당 위치를 찾아야 하므로 O(n)

2번째 인덱스에 위치한 요소에 접근하는 경우

 

검색(Search)

- 특정 값의 노드를 찾는 경우, 처음부터 순회하여 특정 값을 갖는 노드를 찾아야 하므로 O(n)

특정 값의 노드를 찾는 경우

 

삽입(Insertion)

- 연결리스트의 시작에 원소를 삽입하는 경우, head 노드의 포인터만 변경하면 되므로 O(1)

연결리스트의 시작에 원소를 삽입하는 경우

- 연결리스트의 중간에 원소를 삽입하는 경우, 처음부터 순회하여 삽입할 위치의 이전 노드를 찾아야 하므로 O(n)

    - 단, 삽입 작업 자체는 해당 노드의 포인터만 변경하면 되므로 O(1)

중간에 원소를 삽입하는 경우

- 연결리스트의 끝에 원소를 삽입하는 경우, 처음부터 순회하여 마지막 노드를 찾아야 하므로 O(n)

    - 이 때, 시간복잡도를 O(n) -> O(1)으로 개선하는 방법? tail 포인터를 두어 마지막 노드의 주소를 기억한다.

마지막에 원소를 삽입하는 경우

 

삭제(Deletion)

- 연결리스트의 시작 원소를 삭제하는 경우, head 노드의 포인터만 변경하면 되므로 O(1)

시작 원소를 삭제하는 경우

- 연결리스트의 중간 원소를 삭제하는 경우, 처음부터 순회하여 삭제할 위치의 이전 노드를 찾아야 하므로 O(n)

    - 단, 삭제 작업 자체는 해당 노드의 포인터만 변경하면 되므로 O(1)

- 연결리스트의 끝 원소를 삭제하는 경우, 처음부터 순회하여 마지막 노드를 찾아야 하므로 O(n)

    - 단, 삭제 작업 자체는 해당 노드의 포인터만 변경하면 되므로 O(1)

끝 원소를 삭제하는 경우

 

Array vs LinkedList

Array

- 빠른 접근: 무작위 접근(random access)이 가능하기 때문에 인덱스를 사용하여 O(1)의 시간복잡도로 원소에 직접 접근할 수 있다.

- 느린 삽입 및 삭제: 삽입/삭제 시 데이터를 한 칸씩 뒤/앞으로 이동해야 하기 때문에 비효울적이다.

- 크기 고정: 배열 생성 시에 크기가 결정되며 변경하기 어렵다. 크기를 변경하려면 새 배열을 할당하고 기존 데이터를 복사해야 한다.

- 연속적인 메모리 공간 필요: 물리적으로 연속된 메모리 공간이 필요하기 때문에 공간의 제약이 존재한다.

- 메모리 공간 효율성: 각 요소는 동일한 크기를 가지고 있으며 추가 메모리 오버헤드가 없다.

 

Linked List

- 빠른 삽입 및 삭제: 삽입/삭제할 노드를 찾는 데는 O(n)이 걸릴 수 있지만, 삽입/삭제 작업 자체는 해당 노드의 포인터만 변경하면 되므로 O(1)이다.

- 느린 접근: 순차 접근(sequential access)만 가능하기 때문에 O(n)의 시간복잡도를 가진다.

- 동적 크기: 크기를 동적으로 조절 가능하므로 메모리 사용이 효율적이다. (불필요한 메모리 공간을 낭비하지 않는다.)

- 연속적인 메모리 공간 불필요: 물리적으로 연속된 메모리 공간이 필요하지 않기 때문에 공간의 제약이 없다.

- 메모리 공간 비효율성: 각 노드는 다음 노드를 가리키는 포인터를 저장해야 하므로 추가적인 메모리가 필요하다.