[자료구조] List - 배열로 구현하기

"리스트를 배열로 구현한다"는 무슨 말일까?

리스트는 ADT(Abstract Data Type)이다.
즉, 리스트 자체는 인터페이스와 같은 추상적인 것이고 제시된 명세서에 따라 내부 구현은 각각 다를 수 있다.
이때 구현 과정을 배열로 하느냐, 링크드 리스트로 하느냐에 따라 내부적으로 다르게 구현된다.

리스트에서 명시한(구현해야 하는) 기능들이 있는데, 그 기능을 배열로 어떻게 구현하는지 설명하겠다.

Add(index, data) 특정 구간에 삽입 - Big-O: O(N)

배열로 구현하였을 때, 특정 구간에 데이터를 삽입하는데 O(N)의 시간 복잡도를 가지게 된다.
특정 구간에 넣어줘야 할 때, 모든 요소를 한 칸씩 다 옮겨줘야 하는 경우가 최악의 경우 N이기 때문이다.

remove(index) 특정 인덱스 삭제 - Big-O: O(N)

특정 인덱스의 값을 삭제해줄 때는 O(N)의 시간 복잡도를 가진다.
add와 마찬가지로, 모든 인덱스를 한 칸씩 옮겨줘야 하는 경우가 최악의 경우이기 때문이다.

배열로 구현한 리스트의 시간 복잡도

삽입 -> O(N)
삭제 -> O(N)
특정 데이터 조회 -> O(N) -- 이 부분이 헷갈릴 수 있는데, 특정 데이터 값을 조회하려면 모든 인덱스를 탐색해야 하기 때문이다.
인덱스로 조회 -> O(1)

장점

1. 배열로 구현하기 때문에 특정 인덱스 조회가 매우 빠르다.
배열은 메모리에 연속적으로 위치해 있기 때문에, 인덱스 값에 따라 바로 접근할 수 있다. 시간 복잡도는 O(1)이다.

2. 캐시 친화적이다.
이유는 해당 포스팅에 설명되어 있다.
https://ttungbab.tistory.com/172

단점

1. 배열로 구현하니까, 처음에 데이터 공간을 미리 할당하고 동적으로 크기를 변경할 수 없다.
하지만 실제 구현할 때, 배열의 내부 크기를 조정하여 이 문제를 해결할 수 있다.