List vs Array

이 글은 책 알고리즘 도감에서 List, Array 부분을 정리한 글입니다.

 

List vs Array

List

데이터를 일직선으로 나열한 형태

추가/삭제는 쉽지만 원하는 데이터에 접근하려면 시간이 많이 걸림.

List Pointer

• 각 데이터에는 pointer가 존재, 다음 데이터의 메모리 위치
• 메모리 상의 연속된 위치에 저장하지 않아도 됨.
• Sequential Access(순차 접근) => 처음부터 순서대로 접근 => 탐색 시간이 오래 걸림.
• 추가/삭제 시 pointer만 변경
• 계산 시간
  • 검색 => 접근하고자 하는 데이터가 가장 뒤에 있는 경우, 선형 탐색 => O(n)
  • 추가 => 두 개의 pointer만 변경, n에 관계없음 => O(1)

원형 List

마지막 데이터의 pointer가 선두 데이터의 메모리 위치 가리킴

양방향 List

• 보통 pointer 하나만 가지고 있지만 데이터가 2개의 pointer를 사용해서 앞/뒤 데이터를 가리킴.
• 앞/뒤 데이터를 가리키니 추적이 쉬움.
• pointer 저장 영역이 커짐.
• 추가/삭제 시 변경해야할 pointer가 많아짐.

Array

데이터를 1열로 나열한 형태

데이터 접근은 쉽지만 추가/삭제는 시간이 많이 걸림.

• 연속된 메모리 영역에 순서대로 저장.
• Random Access(임의 접근) => 연속된 영역이라 메모리 주소 계산 가능 => 바로 접근 가능
• 추가 => 공간 확보 필요, 다른 데이터 이동 필요
• 계산 시간
  • 검색 => 임의 접근 => O(1)
  • 추가 => 선두에 데이터 추가 시 모든 데이터 이동 => O(n)

Name	Access	Add	Delete
List	느림	빠름	빠름
Array	빠름	느림	느림