[자료구조] Array, ArrayList, Linked-List

안녕하세요 개발콩 입니다😆

오늘은 자료구조 Array, ArrayList, Linked-List에 대해서 알아보도록 하겠습니다.

 

우리가 개발을 하며 사용하는 Array, List와 같은 것은 순서를 가지로 일렬로 나열한 원소들의 모임입니다.

이러한 것을 구현하는 방법에는 3가지가 있습니다.

 

 

 

Array(배열)

연속된 메모리 공간에 순차적으로 저장되는 자료구조입니다.

즉, 인덱스와 인덱스에 대응하는 데이터들로 이루어진 선형 자료구조입니다.

 

아래는 C++코드입니다. (C언어로 표현하고 싶었지만 티스토리에는 C언어를 제공하지 않습니다.)

int arr[5] = {0};

 

우리는 배열을 선언하는 최초 시점에 배열의 크기가 고정됩니다.

 

우리는 인덱스를 활용하여 임의의 원소의 접근, 수정에 관하여 O(1)의 시간으로 접근할 수 있습니다.

하지만, 임의의 원소를 추가, 삭제하는데에는 기존의 원소들을 이동시켜야 하기 때문에 O(n)의 시간이 발생하게 됩니다.

 

배열의 시간 복잡도 특성

임의의 원소 접근 / 수정	O(1)
임의의 원소 추가 / 삭제	O(n)
마지막 원소 추가	O(1)
마지막 원소 삭제	O(1)

 

 

 

배열을 선언하는 최초 시점에 배열의 크기가 고정되기 때문에 우리는 무한정 요소들을 추가할 수 없습니다.

따라서 이러한 문제를 해결하기 위해 ArrayList(동적배열)이 등장합니다.

 

 

 

ArrayList(동적배열)

Array의 최초 선언 시점에 배열의 크기가 고정되는 문제를 해결하기 위해 등장했습니다.

최초 선언된 크기보다 더 많은 원소가 추가되는 경우 기존 크기보다 더 큰 공간을 새롭게 할당하고 기존의 배열 값을 복사하는 방식으로 구현되었습니다.

 

 

모든 동작은 배열과 동일하게 수행됩니다.

하지만, 배열을 추가하는 과정에서 O(1)의 시간복잡도가 발생할수도, 혹은 O(n) + O(1)의 시간복잡도가 발생할 수도 있습니다.

 

이것은, 배열의 선언된 크기보다 아직 공간에 여유가 있을 경우 O(1)의 시간복잡도가 발생하지만,

공간이 가득 차 있을 경우 더 큰 공간을 할당하고 기존의 배열 값을 복사하기 때문에 O(n)의 시간이 추가로 발생하기 때문입니다.

 

동적배열의 시간 복잡도 특성

임의의 원소 접근 / 수정	O(1)
임의의 원소 추가 / 삭제	O(n)
마지막 원소 추가	O(1) or O(n)
마지막 원소 삭제	O(1)

 

 

 

앞서 나온 배열과 동적배열의 단점이 존재합니다.

바로 메모리 공간을 할당하는 과정에서 더 큰 메모리 공간을 사용하기 때문에 메모리 낭비에 대한 문제가 발생합니다.

이것을 해결하기 위해 Linked-List라는 개념이 등장합니다.

 

 

 

Linked-List(연결리스트)

연속되지 않은 메모리 공간에 연결되어 저장되는 자료구조입니다.

데이터와 포인터로 구성된 노드를 통해 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료구조입니다.

 

 

기존 배열과 동적배열과의 차이점은 연속되지 않은 메모리 공간에 할당된다는 것입니다.

따라서, 시작 주소값을 기준으로 특정 인덱스에 바로 접근할 수 없습니다.

 

연결리스트의 시간 복잡도 특성 (시작, 마지막 주소값을 알고 있다는 가정)

 

임의의 원소 접근 / 수정	O(n)
임의의 원소 추가 / 삭제	O(n)
마지막 원소 추가	O(1)
마지막 원소 삭제	O(1)

 

 

연결리스트는 결국 메모리 공간의 이점만 가질 수 있는 것은 아닙니다.

위의 작성된 기준은 임의의 원소 추가, 삭제에 관하여 복잡도가 O(n)으로 표현되었습니다.

즉, 연속되지 않은 메모리 공간에 연결되어있기 때문에 특정 위치에 추가, 삭제의 노드를 찾는 시간인 O(n)이 포함되어 있기 때문입니다.

 

하지만 우리가 특정 위치에 관한 위치를 알고 있다면 해당 노드를 찾는 시간인 O(n)의 복잡도가 없어지기 때문에 O(1)의 시간복잡도로 요소를 추가하고 삭제할 수 있게됩니다.

 

즉, 이러한 모든 장점이 있는 대표적인 예시인 Text Editor를 보면 이러한 연결리스트의 장점을 잘 활용한 것이라고 볼 수 있습니다.