[자료구조] Array, ArrayList

김희성 개발자 면접 CS강의/스터디

 

 

 

 

Array (배열) 

• 배열은 메모리 상에서 데이터가 연속적으로 연결되어 있는 선형 자료구조이다.
• 크기는 고정되어 변경될 수 없다. (데이터의 삽입/삭제 불가능. 배열의 사이즈 변경 안 됨)
• 시간 복잡도
  •  i번째 데이터에 접근/변경 O(1)(Random Access)
  •  x라는 데이터 탐색 O(N)

 

 

Dynamic Array(List, ArrayList, Vector) 

• Dynamic Array는 메모리상에서 데이터가 연속적으로 연결되어 있는 선형 자료구조.
• 크기가 동적으로 변경될 수 있으나 근본적으로 배열 기반으로 구현
• 여유공간 없으면 사이즈를 (2배 or 50%)씩 늘린다.
• 사이즈 늘리는 로직상 메모리 낭비 발생가능
  • 리사이징 발생할 때마다 새로운 메모리 영역을 할당하고 데이터를 복사함.
  • 리사이징은 자주 발생하지 않으므로 평균적으로 O(1)에 삽입/삭제 가능. 단 리스트 끝에서만.
  • 보통 실무에서도 리스트에 사이즈 안 주고 담기 시작함.
• 리스트 중간에 데이터가 삽입/삭제될 경우 O(N) 소요 
• list.remove()와 list.add()의 시간복잡도 O(N)
• 리사이징이 최대한 일어나지 않게 하는 게 좋은데 전략은 언어마다 다를 수 있다.

 

 

Linked List

• 메모리 상에서는 데이터가 불연속적으로 저장되어 있으나, 논리적(코드상)으로 연속성을 구현한 선형 자료구조. (몇 번째 데이터가 어디에 저장되어 있는지 찾을 때 오랜 시간 걸리는 자료구조)
• 노드(Node) : ( 값(value) , 다음값의 위치(메모리주소) ) 
• 시간 복잡도 
  • i 번째 데이터 접근/변경 O(N)
  • x라는 데이터 탐색 O(N)
  • 데이터 삽입/삭제 어느 위치에서나 O(1)
• 데이터 접근의 시간 복잡도는 O(N)
• 데이터 삽입/삭제는 어느 위치에서나 O(1)
• Double Linked List는 양방향 탐색이 가능하여 중간에 있는 데이터 찾을 때가 제일 오래 걸림.
• Java에서 Linked List는 Double Linked List로 구현되어 있음