선형구조 - 순차 리스트

Sequential List

: 데이터들을 논리적인 순서대로 메모리에 연속해 저장하는 구조이다.

 

종류

1. Array

2. ArrayList

 

 

Array

: 크기가 고정되어있는 고정 길이 배열 구조이다.

 

특징

- 고정된 크기를 가진다.

- 메모리 구조 단순하다.

- 인덱스를 통해 검색한다: O(1)

- 삽입, 삭제 시 추가작업 필요하다(원소 이동 비용 발생): O(n)     // 삽입, 삭제 연산 늘어날수록 연산 시간 증가

 

삽입

: 삽입할 자리를 만들고 삽입한다.

- 원소 옮기는 추가작업 필요

 

삭제

: 원소 삭제 후 삭제한 원소 뒤의 요소들을 앞으로 옮긴다.

- 원소 옮기는 추가작업 필요

 

검색

: 인덱스를 통해 원소를 탐색한다.

- 추가 작업이 불필요

 

ArrayList

: 크기를 자동으로 늘릴 수 있는 동적 배열 구조이다.

 

특징

- 인덱스를 통해 검색한다: O(1)

- 크기를 자동으로 조정할 수 있다(복사 비용 발생): O(n)

- 삭제 시 추가작업 필요하다(원소 이동 비용 발생): O(n)     // 삽입, 삭제 연산 늘어날수록 연산 시간 증가

- 중간 삽입 시 추가작업 필요하다(원소 이동 비용 발생): O(n) 

- 끝에 삽입 시 공간 여유가 있으면 O(1), 없으면 resize로 인해 복사 비용(O(n)) 발생한다.

 

더블링

:내부적으로 배열이 다 차게 되면 배열의 크기를 두 배로 늘리고 기존 데이터를 복사한다.

 

 

시간 복잡도 비교

// n = 데이터 개수

	Array	ArrayList
검색	O(1)	O(1)
중간 삽입	O(n)	O(n)
끝 삽입		O(1) // 더블링 발생 시: O(n)
삭제	O(n)	O(n)
복사	O(n)	O(n)