List와 Array 구분 (List형 컬렉션프레임워크와 배열의 구분)

내가 이해한 List와 Array의 차이에 대해 정리해보았다.

1. 간단 요약

배열 = 연속적이며 변수의 크기가 고정되어있는, 나열된 데이터 구조
리스트 = 데이터(노드) 꼬리물기 구조

---

 

2. 상세 버전

• 배열은 고정된 크기를 갖는 같은 자료형의 원소들이 연속적으로 저장된 구조로, 인덱스가 중요하며 cache hit가 가능함(미리 인덱스를 읽어 위치를 저장). 데이터가 삭제 되어도 인덱스를 유지해야 한다.(⇒ 메모리 낭비를 초래한다)
  
• 리스트는 빈틈없는 데이터 적재가 가능한 순서가 있는 데이터의 모임. 노드를 연결해 데이터를 저장한다. 노드는 기본적으로 헤드와 테일의 형태로 이루어져 있으며, 각 노드의 테일에는 다음 노드의 주소 정보를 저장하고 있어 꼬리에 꼬리를 무는 형태. 리스트에서는 인덱스가 배열에 비해 덜 중요하며, 순차성을 보장하지 못하므로 cache hit가 어렵다고 볼 수 있다.( = 색인(검색)이 어렵다.)

리스트 설명 이미지

 

---

3. 할당에 따라 구분

• 배열은 Compile time에 할당되는 정적 메모리 할당,
  리스트는 새로운 Node가 추가되는 runtime에 할당되는 동적 메모리 할당
  • 런타임 : 컴파일 과정을 마친 응용 프로그램이 사용자에 의해 실행될 때
  • 컴파일 타임 : 소스 코드가 컴파일을 통해 기계어 코드로 변환되어 실행 가능한 프로그램이 되는 편집 과정

 

---

4. 사용하는 의도와 목적에 따라 구분

• 저장할 데이터의 개수가 정해져 있고 / 삽입, 삭제 작업이 적고 / 특정 위치의 데이터를 조회하는 작업이 많다면 배열
• 저장할 데이터의 개수가 미정이고 / 삽입, 삭제 작업이 많고 / 특정 위치 데이터를 조회하는 경우가 별로 없다면 리스트