Array 특징

• 동일한 자료형의 데이터를 일렬로 나열한 선형 자료구조(sequence container)
• 연속된 메모리 공간에 순차적으로 저장.
• 배열의 크기는 고정. 선언할 떄에 배열의 크기를 정하고 변경할 수 없다.

시간복잡도

• 삽입/삭제
  • 배열의 맨 뒤에 삽입/삭제하는 경우 : O(1)
    • 끝 주소를 찾고 배열의 길이를 1 증가시킨 후 추가할 원소 데이터를 저장/삭제
  • 배열의 맨 앞에 삽입/삭제하는 경우 : O(n)
  • 배열의 중간에 삽입/삭제하는 경우제 : O(n)
    • 그 뒤에 존재하는 모든 원소들을 한칸씩 뒤로 밀어야함. 뒤로 미는 연산이 한번 일어날 때 O(1)이 걸린다. 만약 N개의 원소를 한 칸씩 밀어야 한다면 O(1XN) = O(N)이 걸리게 된다.
    • 추가하려는 위치가 배열의 끝과 가까울수록 연산의 수도 줄어들고, 배열의 처음과 가까울수록 연산의 수도 늘어난다. 하지만 평군은 O(N/2) = O(N)
• 탐색 : O(1)
  • 일렬로 나열되어 있으니 배열의 시작 주소에서 k칸 만큼 더하면 k번째 원소를 찾을 수 있다.

장점

• 인덱스를 가지고 있어 바로 접근 가능(시간복잡도 O(1))
  • 자료구조의 크기가 클수록 더 장점이 강력해짐
• 연속된 메모리 공간에 존재하기 때문에 관리하기가 편하다.
• 운영 체제의 캐시 지역성을 활용할 수 있다.
• 캐시지역성 : 운영체제는 물리적으로 근접한 위치의 데이터가 보통 자주 활용되기 때문에 미리 캐시에 넣어둠으로써 CPU의 성능을 향상시키는데, 배열은 물리적으로 연속된 곳에 데이터를 저장하기 때문에 이러한 기능을 보다 잘 활용할 수 있다.

단점

• 삽입과 삭제가 어렵고 오래 걸린다.
  • 원소를 삽입하거나 삭제할 경우, 해당 원소 이후의 모든 원소들을 한칸씩 밀거나 당겨야 한다.(연속된 메모리 공간에 저장되기 때문)
• 배열의 크기를 바꿀 수 없다.
  • 배열은 처음 생성할 때 크기를 설정함.
  • 크기를 변경하기 위해서는 원하는 크기의 새로운 배열을 선언한 뒤 값을 복사해야함.
  • 사용안한 만큼 베모리가 낭비될 수 있다.
• 배열요소를 삭제했더라도 변수의 선언이 해제되지 않는 이상 메모리를 점유하고 있다.

언제 사용할까?

• 데이터 개수가 확실하게 정해져 있을 때
• 데이터의 삭제와 삽입이 적을 때
• 검색을 해야할 때

배열 vs 링크드 리스트

배열과 링크드 리스트는 데이터를 나열한 다는 점에서 자주 비교된다.

1. 데이터 접근
   • 배열은 index만 알고 있다면 메모리의 바로 접근할 수 있기 때문에 O(1)의 시간 복잡도를 가지지만, 링크드 리스트는 연결되어 있는 노드를 탐색하여 접근해야 하기 때문에 O(n)의 시간복잡도를 가지며 배열에 비해 속도가 느리다.
2. 데이터 삽입, 제거
   • 배열은 데이터 삽입, 제거 시 기존의 데이터들의 위치를 이동시키는 경우가 많아 비효율적일 수 있지만, 리크드 리스트는 삽입 제거하려는 데이터의 이전, 이후 노드의 링크만 연결시키면 되기 때문에 효율적
   • 다만 LinkedList는 데이터 삽입/삭제마다 메모리 할당/해제가 일어나므로 시간복잡도는 빠를지라도 시스템콜에 있어서 Array보다 더 시간이 걸린다.
3. 메모리 공간 활용
   • 배열은 고정된 크기의 메모리를 할당받아 크기를 변결할 수 없지만 링크드 리스트는 연결되어 있는 노드에 따라 크기가 동적으로 변하므로 효율적으로 메모리를 사용할 수 있다.

즉, 데이터 삽입 제거가 빈번하게 발생한다면 링크드 리스트, 이미 만들엊 있는 데이터 구조에서 접근이 많이 발생한다면 배열이 유리하다.

Reference

https://choheeis.github.io/newblog//articles/2020-12/data-structure-array https://velog.io/@choiiis/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EB%B0%B0%EC%97%B4Array%EA%B3%BC-%EB%A6%AC%EC%8A%A4%ED%8A%B8List https://chanyeong.com/blog/post/49