선형 자료 구조

일렬로 늘어선 자료를 저장하기 위한 자료구조.

 

 

종류

정적 배열

 

동적 배열 

 

연결 리스트

 

 

 

 

정적 배열

- 데이터가 메모리에 연속적으로 저장된다. 

 

- 크기가 고정이다.

 

- 시간 복잡도 

인덱스를 알면 O(1)로 접근 가능 ( Random Access )

 

 

 

 

동적 배열 

- 데이터가 메모리에 연속적으로 저장된다.

 

- 크기(capacity)가 동적으로 증가한다. 

자바에서 대표적으로 ArrrayList가 동적배열이다. 

 

- 시간 복잡도

인덱스 통한 접근 O(1) ( Random Access )

capacity 증가 시, 배열을 복사 후 더 큰 배열로 옮기기 때문에 O(N)

삽입/삭제 시, 기존 원소들의 shift 연산이 필요해서 최악으로 O(N)

 

ex) 첫 번째에 삽입/삭제는 기존의 모든 원소들을 밀어야 하기 때문에 O(N)

반면, 마지막 삽입/삭제는 마지막에만 붙이면 되므로 O(1) -> 코테에서 여러 번 사용했음 

( capacity가 꽉차자면 O(N)이지만.. 처음부터 capacity를 많이 늘려서 만들 수 있다 )

 

 

 

 

연결 리스트 

'배열과 다르게' 삽입 삭제 시 O(1) 시간 복잡도를 갖는 것이 핵심

하지만!!  삽입/삭제 할 위치를 찾아야 하므로 결국 O(N) 시간 복잡도를 갖는다. (random access불가)

 

Tree 구조에서 근간이 되는 자료구조다.