[ 자료구조 ] 배열(Array) vs 리스트(List) - 특징, 차이

배열(Array)

---

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

 

리스트(List)

---

• 배열의 문제점을 해결하기 위한 자료구조
• 빈틈없는 데이터의 적재라는 장점을 가진다.
  • 원소를 삭제했을 때 삭제된 데이터 뒤 원소로 빈틈없이 연속적으로 위치시킨다.
• 리스트의 핵심은 원소들 간의 순서로 순서가 있는 데이터의 모임이 리스트이며 리스트를 다른 이름으로 시퀀스(sequence)라고도 부른다.
• 배열에서 인덱스는 유일무이한 식별자이지만 리스트에서는 몇 번째 데이터인지 정도의 의미를 가진다.
• 빈 엘리먼트는 허용하지 않는다.
• 순차성을 보장하지 못하기 때문에 spacial locality 보장이 되지 않아 cash hit가 어렵다.
• spacial locality : 프로그램 실행 시 접근하는 메모리 영역은 이미 접근이 이루어진 영역의 근처일 확률이 높다는 프로그램 성격 표현
• 언어별로 list를 지원하는 것이 다르다
  • 최근 언어들은 리스트를 기본으로 제공
  • C : 리스트 지원 X
  • JavaScript : 배열에 리스트 기능 포함
  • Python : 기본 리스트, 배열 지원 X
  • Java : 배열과 리스트 모두 지원, ArrayList와 LinkedList로 나뉨
• ArrayList와 LinkedList는 구현 방법에 따라 나뉜다.
  • ArrayList
    • 배열을 이용해 리스트를 구현한 것
    • 접근이 빠름(순차 x) 하지만 데이터 추가와 삭제가 느림
    • 동적으로 사용하기 힘듬(자바의 경우 자동으로 사이즈를 키워서 관리한다. → Dynamic Array)
  • LinkedList
    • 연결로 구현한 리스트
    • 한 원소에서 값과 다음 원소의 주소를 알고 연결하는 방식
    • 순차적으로 접근함 W(n)
    • 삽입, 삭제는 O(1)이지만 해당 지점까지 접근해야하므로 W(n)일 수 있음
    • → 배열과 다르게 논리적 저장 순서와 물리적 저장 순서가 일치하지 않는다!
• 배열은 Compile time에 할당되는 정적 메모리 할당, 리스트는 새로운 Node가 추가되는 runtime에 할당되는 동적 메모리 할당
  • 런타임 : 컴파일 과정을 마친 응용 프로그램이 사용자에 의해 실행될 때
  • 컴파일 타임 : 소스 코드가 컴파일을 통해 기계어 코드로 변환되어 실행 가능한 프로그램이 되는 편집 과정