20230219 [Java] 배열(Array)과 리스트(List)

배열(Array)

• 데이터가 많아지고 그룹 관리의 필요에 따라 배열을 사용한다.
• 고정된 크기를 갖는 같은 자료형의 원소들이 연속적인(논리적 저장 순서와 물리적 저장 순서가 일치) 형태로 구성된 자료구조
  • 인덱스에 따라 값을 유지하므로 원소가 삭제되어도 빈자리가 남게되어 메모리가 낭비된다.
  • 처음 크기를 10으로 지정한다면 5개의 데이터만 저장하더라도 실제 배열의 크기는 10이다.
• 인덱스 (index) : 각원소의 번호로 0번부터 시작하며, 해당 원소에 접근한다.
• 데이터 갯수가 확실하게 정해져 있고, 접근이 빈번한 경우 배열이 효율적이다.
• cache hit 가능성이 커져 성능에 도움이 된다.
  ( * cache hit : CPU가 참조하고자 하는 메모리가 캐시에 존재하고 있는 경우)
• 고정적이고 연속적인 만큼 인덱스로 random access가 가능하다.
• Compile time에 할당되는 정적 메모리 할당
  ( * Compile time : 소스 코드가 컴파일을 통해 기계어 코드로 변환되어 실행 가능한 프로그램이 되는 편집 과정)

리스트(List)

• 배열의 문제점을 해결하기 위한 자료구조
• 빈틈없는 데이터의 적재라는 장점을 가진다.
  원소를 삭제했을 때 삭제된 데이터 뒤 원소로 빈틈없이 연속적으로 위치시킨다.
• 리스트의 핵심은 원소들 간의 순서이다. 순서가 있는 데이터의 모임이 리스트이며 리스트를 다른 이름으로 시퀀스(sequence)라고도 부른다.
• 배열에서 인덱스는 유일무이한 식별자이지만 리스트에서는 몇 번째 데이터인지 정도의 의미를 가진다.
• 빈 엘리먼트는 허용하지 않는다.
• 순차성을 보장하지 못하기 때문에 special locality 보장이 되지 않아 cash hit가 어렵다.
  ( * special locality : 프로그램 실행 시 접근하는 메모리 영역은 이미 접근이 이루어진 영역의 근처일 확률이 높다는 프로그램 성격 표현)
• 새로운 Node가 추가되는 runtime에 할당되는 동적 메모리 할당
  ( * runtime : 컴파일 과정을 마친 응용 프로그램이 사용자에 의해 실행될 때)

ArrayList

• 배열을 이용해 리스트를 구현한 것
• 접근이 빠름(순차 x) 하지만 데이터 추가와 삭제가 느림
• 동적으로 사용하기 힘들다. Java의 경우 자동으로 사이즈를 키워서 관리한다. -> Dynamic Array