Array vs List

• Array
  • 논리적 저장 순서와 물리적 저장 순서가 일치한다.
  • 따라서 인덱스로 해당 원소에 접근이 가능하다.
  • 그러므로 검색에는 원하는 원소의 인덱스를 알고있다면 O(1) 이다.
  • 삽입과 삭제에는 삭제 또는 삽입을 한 후에 Shift 비용이 발생하므로 O(n) 이다.
  • 정의와 동시에 길이를 지정하고, 바꿀 수 없다.(정적인 표현)
  • 컴파일 시 Stack 영역에 할당된다.
  • 장점
    • 검색
    • 연속적이므로 메모리 관리가 편함
  • 단점
    • 크기가 고정되어있기 때문에 삭제를 한 후에 shift를 하지않는다면 메모리 낭비가 생긴다.
    • 배열의 크기를 바꿀 수 없다
• List
  • 불연속적인 메모리 공간 할당
  • 동적인 표현
  • 인덱스를 사용하지 않고 포인터를 통해 접근한다.
  • 새로운 노드가 추가될 때 Heap 영역에 할당된다.
  • 장점
    • 삽입 삭제가 자유로움
  • 단점
    • 검색에 시간이 오래걸림 O(n)
    • 포인터를 사욜하므로 메모리 측면에서 비효율적