이번 포스팅 또한 마찬가지로 코딩테스트를 하면서 언제가 한 번 공부해야지 하며 미뤄뒀던 주제다. 모든지 기본에 충실하는 말을 코테를 할 때마다 느낀다.

Array

Array(배열)은 초기화할 때 크기를 지정해야한다. -> 메모리가 고정되어 있다.(정적 할당)
배열은 메모리 공간에 연속적으로 저장되어 있는 자료구조이다. 이러한 특징때문에 인덱스를 통한 접근이 용이하다.
arrayOf() or intArrayOf() or Array(){}로 배열을 초기화 한다.

시간복잡도

  • access(접근)
    시간복잡도: O(1)
    인덱스 x에 곧바로 접근할 수 있다.

  • find(탐색)
    시간 복잡도: O(n)
    0번째 인덱스부터 마지막 인덱스까지 접근하면서 원하는 데이터를 찾는다.
    배열안에 찾으려는 데이터가 앞에 있다면 빠른 시간안에 찾을 수 있지만, 배열 안에 찾는 데이터가 없거나 또는 찾으려는 데이터가 마지막에 있는 경우 n개의 데이터를 살펴봐야 한다.

  • Insertion/Deletion(삽입/삭제)
    시간 복잡도: O(n)
    특정 인덱스에 데이터를 삽입, 삭제하기 위해 기존의 데이터를 옮기는 작업이 필요하다.
    최악의 경우 -> 0번째 인덱스에 데이터를 삽입하기 위해서는 현재 배열의 0번째 인덱스부터 마지막 인덱스까지의 데이터들을 모두 한 인덱스 뒤로 옮겨야한다.
    하지만 배열의 마지막에 데이터를 삽입하거나 삭제하는 경우에는 O(1)의 시간 복잡도를 가진다.

List

Kotlin에서 리스트는 연결리스트(Linked List)라고 생각하면 된다.
필요할 때마다 노드를 생성하여 연결하면 되기 때문에 메모리를 효율적으로 사용할 수 있다.(동적 할당)

  • access(접근)
    시간복잡도: O(n)
    인덱스 x에 있는 노드에 접근하려면 Head에서 다음 노드로 x번 가면 된다.

  • find(탐색)
    시간 복잡도: O(n)
    배열을 탐색할 때와 같은 방법으로 구한다. 0번째 인덱스부터 마지막 인덱스까지 접근하면서 원하는 데이터를 찾는다.
    가장 앞의 노드부터 다음 노드순서로 원하는 데이터를 찾는다. -> 선형탐색
    최악의 경우 -> 링크드 리스트안에 찾는 데이터가 없거나 또는 찾으려는 데이터가 마지막 노드에 있는 경우 n개의 노드를 다 봐야한다.

  • Insertion/Deletion(삽입/삭제)
    시간 복잡도: O(1)
    삽입, 삭제할 노드의 주변 노드들의 Link만 수정하면 된다. 따라서 삽입, 삭제가 실행되는 시간은 특정 값에 비례하지 않고 항상 일정하다.
    ⚠️ 현실적으로 삽입, 삭제를 위해서는 노드를 탐색하는 과정이 필요하다. 최악의 경우 시간복잡도 O(n)이 걸린다. 그러나 연결리스트의 맨 앞 or 맨 뒤의 노드에 삽입, 삭제를 하는 경우 이미 Head를 알고 있기 떄문에 시간복잡도 O(1)을 가진다.

Map

Map은 <key,value>로 객체를 관리하는 컬렉션이다. 특징으로는 순서가 없이 저장되지만 삽입/삭제/조회가 빠르다.

  • access(접근)
    시간 복잡도: O(1)

  • find(탐색)
    시간 복잡도: O(1)
    key로 데이터를 검색했을 때 시간복잡도가 O(1)이지만, value로 데이터를 검색했을 경우 시간복잡도가 O(n)이다.

  • Insertion/Deletion(삽입/삭제)
    시간 복잡도: O(1)

Reference

Array와 List의 차이(시간복잡도 포함)
List, ArrayList, Set, Map, Stack, Queue 자료구조 시간복잡도
TreeMap, LinkedHashMap, HashMap

참고