Array & List

Array

고정된 크기를 갖는 같은 자료형의 원소들을 연속적인 공간에 저장하는 자료구조
stack 영역에 메모리를 할당받은 뒤에 데이터 추가 → 정적 메모리 할당
장점
- index를 통해 랜덤 엑세스가 매우 빠르다 → O(1)
- 다중차원 배열(배열 안에 배열)을 사용할 수 있다
- spatial locality가 보장되어 cache hit rate이 높다
단점
- 삽입, 삭제 연산을 하면 원소를 shift 해주어야 한다 → 최악의 경우 O(N)
- 할당된 메모리보다 저장할 데이터가 많으면 resizing이 필요하다
배열을 사용하면 좋은 경우
- 순차적 데이터를 저장하는 경우
- 다차원 데이터를 다루는 경우
- 랜덤 엑세스가 잦고, 삽입이나 삭제 연산이 적은 경우

순서가 있는 데이터의 모임
언어별 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이 낮다