Array와 List 차이

Array와 List 차이

---

Array와 List의 차이를 알아보겠습니다.

 

각 자료구조의 자세한 설명은 https://kdgdev.tistory.com/8에 있습니다.

 

자 그런데 List에는 Linked List도 있고 Array List도 있죠? 전부 한번 알아볼게요

 

Array와 LinkedList 차이

둘의 대표적인 차이로는 시간복잡도, 할당되는 메모리의 차이가 있습니다.

 

• 시간복잡도
  • 검색
    • Array
      • O(1)
      • 요소들을 index를 통해 곧바로 접근할 수 있는 랜덤 액세스 방식
    • LinkedList
      • O(n)
      • 어떤 요소를 접근할 때 순차적으로 검색하며 찾아야 하는 시퀀셜 액세스 방식
  • 삽입/삭제
    • Array
      • O(n) / 맨뒤에 데이터 O(1)
      • 맨 뒤가 아닌 위치에 데이터의 삽입과 삭제가 일어날 때는 뒤에 데이터들이 앞으로 당겨지거나 뒤로 밀어야하기 때문에 O(n)의 시간이 걸립니다.
    • LinkedList
      • O(1) / 원하는 위치를 모를 때는 O(n)
      • 포인터의 방향만 바꾸어 주면 되기 때문에 삽입/삭제 자체로는 O(1)의 시간이 걸리나 원하는 위치에 넣을 때는 결국 순차적으로 확인해야 하기 때문에 전체적으로는 최대 O(n)의 시간까지 걸릴 수 있습니다.
• 메모리 할당
  • Array
    • 컴파일 타임에 정적으로 할당됩니다.
    • Stack 섹션에 할당됩니다.
  • LinkedList
    • 새로운 요소가 추가될 때 런타임에 동적으로 할당됩니다.
    • Heap 섹션에 할당됩니다.

 

Array와 ArrayList 차이

 

ArrayList는 List이긴 하나 Index로 요소에 접근하기 때문에 시간복잡도가 같습니다.

 

하지만 List의 특징을 가지고 있기 때문에 그로 인한 차이점을 살펴보겠습니다.

 

• 차이점
  • Array는 정적으로 할당되기 때문에 길이가 변하지 않습니다. 하지만 ArrayList는 가변길이입니다.
  • Array는 다차원이 가능하고 ArrayList는 불가능합니다.
  •  ArrayList에서 새로운 요소를 추가할 때, 여유공간이 없는 경우 맨뒤여도 O(n)의 시간이 걸립니다.
    • ArrayList의 크기가 변할 때는 메모리에 크기가 더 큰 새로운 배열에 재할당을 받는 방식입니다. 그래서 그곳으로 요소들을 옮기는 시간인 O(n)의 시간이 걸립니다.

※ 잘못된 정보, 혹은 다른 의견이 있다면 댓글로 말해주세요. 감사합니다.