Array & List

Array

• 고정된 크기를 갖는 같은 자료형의 원소들을 연속적인 공간에 저장하는 자료구조

• stack 영역에 메모리를 할당받은 뒤에 데이터 추가 → 정적 메모리 할당

• 장점

  • index를 통해 랜덤 엑세스가 매우 빠르다 → O(1)

  • 다중차원 배열(배열 안에 배열)을 사용할 수 있다

  • spatial locality가 보장되어 cache hit rate이 높다

• 단점

  • 삽입, 삭제 연산을 하면 원소를 shift 해주어야 한다 → 최악의 경우 O(N)

  • 할당된 메모리보다 저장할 데이터가 많으면 resizing이 필요하다

• 배열을 사용하면 좋은 경우

  • 순차적 데이터를 저장하는 경우

  • 다차원 데이터를 다루는 경우

  • 랜덤 엑세스가 잦고, 삽입이나 삭제 연산이 적은 경우

List

• 순서가 있는 데이터의 모임

• 언어별 List 지원

  • C : 배열만 지원할 뿐 List를 지원하지 않음 (라이브러리를 사용하거나 직접 구현해야함)

  • Javascript : 배열에 List 기능이 포함됨

  • Python : 기본적으로 List를 제공, 배열은 제공하지 않음 (C보다 메모리를 더 많이 필요로함)

  • Java : 배열과 List를 모두 지원 (두 가지가 완전히 분리됨), 크게 ArrayList, LinkedList 형태로 지원함

• Java의 ArrayList

  • 내부적으로 배열로 구현됨

  • 장점 : 인덱스를 통해 랜덤 엑세스가 가능 → O(1)

  • 단점 : 삽입, 삭제 연산속도가 느림 → O(N)

• Java의 LinkedList

  • 새로운 데이터 추가시 heap 영역에 런타임시 메모리를 할당 → 동적 메모리 할당

  • 장점 : 삽입, 삭제 연산속도가 빠름 → O(1)

  • 단점 : 인덱스 개념이 없기 때문에 랜덤 엑세스 불가능 → O(N)

• 장점

  • 삽입, 삭제 연산속도가 빠르다 → O(1)

  • 새로운 데이터 추가시 동적으로 메모리를 할당하기 때문에 resizing할 필요 없음

• 단점

  • index 개념이 없어 랜덤 엑세스가 불가능하다. 처음부터 탐색해야하기 때문에 → O(N)

  • spatial locality가 보장되지 않아 cache hit rate이 낮다