배열 Array
int arr[3] = { 0, 1, 2 };같은 타입의 데이터 여러개를 하나의 이름으로 groupping하여 관리할 수 있게 하는 자료구조
장점
- 논리적 저장 순서 = 물리적 저장 순서
- 인덱스에 해당하는 원소에 O(1)만에 접근 가능
- 다른 말로, 'Random Access가 가능하다'고 표현
- 심플한 자료구조.
단점
- 삽입/삭제가 어렵다.
- O(N)만큼 소요된다.
- 중간에 원소를 빼거나 끼워넣으려면 한칸씩 밀고 당기는 걸 해주는데, 이 때 O(N)만큼 걸린다.
- 초기에 배열 크기를 지정해야한다.
- 추후에 동적할당으로 수정할 수 있긴 하다.
연결 리스트 Linked List
어떤 노드가 데이터와 다음 노드에 대한 주소 정보(포인터)를 갖고, 노드들끼리 순차적으로 연결되어 있는 방식의 자료구조
장점
- 삽입/삭제 자체는 O(1)만에 수행된다
- 다음 포인터에 대한 값만 변경해주면 되기 때문
- 필요할 때마다 크기를 늘이거나 줄일 수 있어 메모리의 낭비가 적다.
단점
- 탐색에 O(N)이 소요된다.
- Random Access가 불가능하다.
- 어떤 노드를 삭제하고 싶다면, O(N)의 시간동안 찾아서 O(1)의 시간동안 삭제해야하므로, 결국 삭제가 O(N)만에 이루어진다(...)
- 삽입에서도 마찬가지로 특정 위치에 삽입하고 싶다면 O(N)의 시간동안 해당 위치를 찾아서 O(1)의 시간동아 삭제하므로, 결국 O(N)이다(...)
- 하지만 삽입/삭제 시 메모리 관리는 용이하단 면에서 배열보다 낫다.
- 이는 Tree를 배열로 구현하고 리스트로도 구현해보면 느낄 수 있다.
- 배열보다 복잡하다. 구현이 어렵다.
- data뿐만 아니라 다음 노드를 가리키는 포인터까지 신경써야한다.
종류
단일 연결 리스트 Singly Linked List
이중 연결 리스트 Doubly Linked List
원형 연결 리스트 Circular Linked List
배열 Array VS 연결 리스트 Linked List
- 삽입/삭제가 잦다 → 연결 리스트
- 이미 만들어진 구조에서 접근만 필요하다 → 배열
- 단, 메모리의 할당과 해제는 표면적으로는 시간복잡도 안에 포함되지 않지만, 이러한 System call을 사용하는 경우에는 시간이 꽤나 소요된다는 것을 주의해야한다.
보너스 느낌으로 동적 배열에 대해서도 알아보자.
동적 배열 Dynamic Array
자료가 배열의 용량보다 많아져야하면 배열의 용량이 자동으로 늘어나는 자료구조
동작
용량이 가득 찼는데 새로운 원소가 추가되어야할 경우 용량이 2배로 늘어나며 계속해서 추가 할당을 할 수 있는 자료구조다.
2배로 늘리는 이유 : 2배로 늘려야만 평균적으로 확장에 O(1)만큼 걸리게 되기 때문
아래 더보기를 클릭하면 구체적이고 수학적인 증명 과정을 볼 수 있다.
더보기
- 마지막 n번째 원소를 삽입할 때 k번째 재할당(2배로 늘리기)을 했다면, n = 2^(k-1)+1 이며 배열의 전체 크기는 2^k
- 지금까지 총 복사한 원소의 개수
- 1 + 2^1 + 2^2 + ... + 2^(k-2) + 2^(k-1) = 2^k-1
- 등비수열의 합 공식 이용
- 따라서, n개의 원소를 저장하는데 필요했던 재할당 메소드의 총 수행시간은 2^k-1이므로 이는 2n으로 표현할 수 있다.
- 재할당 총 수행 시간 / 재할당 횟수 = 2n / n = 2
- 그러므로 재할당 메소드의 평균 수행시간은 O(1)이 된다.
이 재할당 과정을 수동으로 하긴 어렵기 때문에, 라이브러리에서 지원해준다 (ex : JAVA ArrayList)
References
- https://yoonpunk.tistory.com/8
- https://tenlie10.tistory.com/119
- https://makefortune2.tistory.com/191