[자료구조] 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로 구현되어 있음