🌿 정의
배열
배열은 동일한 데이터 타입을 가지는 요소들이 연속적으로 저장된 데이터 구조입니다.
배열이 할당되는 순간 크기가 고정됩니다.
메모리에서 실제로 연속된 공간을 차지하므로 index를 이용해 빠르게 접근할 수 있습니다.리스트
메모리에서 불연속적으로 저장되는 크기가 가변적인 데이터 구조입니다.
각 노드가 메모리에 불연속적으로 저장되어 있고, 각 노드는 다음 노드를 가리키는 포인터를 가지고 있습니다.
이를 통해 다음 노드를 찾고 전체 리스트를 순회할 수 있습니다.
리스트는 삽입, 삭제 연산을 효율적으로 수행할 수 있습니다.🏃 연산별 속도 비교
READ / UPDATE
(i번째 주소) = (시작 주소) + i * (자료형 크기)
위 연산을 수행하면 원하는 index에 O(1) 만에 접근하고 변경할 수 있습니다.
배열은 실제 주소가 나란히 배치되어 있기 때문에 원하는 index에 접근하는 것이 매우 빠릅니다.
하지만 리스트는 앞에서부터 값을 순회해서 찾아야 합니다.
따라서 원하는 index의 값을 찾고 변경하는데 O(N)의 시간이 걸립니다.
CREATE / DELETE
배열은 새로운 값을 중간에 추가하거나 삭제하려면 해당 index 뒤에 저장된 값을 모두 이동해야 합니다.
삭제 예시를 보면 삭제하고자 하는 index의 값을 지운 후, 뒤편에 저장된 값들을 한 칸씩 앞으로 이동시켜야 합니다.
따라서 배열 중간에 값을 추가하거나 삭제하는 작업의 시간복잡도는 O(N)이 됩니다.
리스트는 특정 index에 값을 추가하거나 삭제할 때, 해당 index 앞뒤 노드가 가리키고 있는 포인터를 신경써줘야 합니다.
삭제 예시를 보면 삭제하고자 하는 index의 노드를 삭제한 후, 2번 노드의 포인터를 4번 노드를 가리키도록 수정합니다.
그러면 전체 리스트가 잘 연결되어 있음을 볼 수 있습니다.
리스트의 추가, 삭제 작업은 해당 index를 찾아가는데 O(N)의 시간이 걸리고 추가, 삭제 작업을 하는데 O(1)의 시간이 소요됩니다.
데이터의 추가, 삭제 작업의 경우 동일하게 O(N)의 시간이 걸리지만, 구체적인 동작 방식 때문에 리스트가 배열보다 좀 더 빠르게 작업을 마무리할 수 있습니다.
🤔 적합한 선택 기준
배열은 다음의 경우에 적합합니다.
- 전체 길이가 자주 바뀌지 않는 경우
- 데이터의 추가, 삭제가 빈번하지 않은 경우
- 데이터를 읽는 횟수가 많은 경우
리스트는 다음의 경우에 적합합니다.
- 전체 길이를 예측할 수 없는 경우
- 데이터의 추가, 삭제가 빈번한 경우
- 데이터를 읽는 횟수가 적은 경우
