배열과 리스트

배열

 

동일한 자료형 원소들을 연속적인 메모리 공간에 저장.
크기는 고정, 선언 시 크기를 지정 해야 함,
삽입삭제 시간이 느림.

배열 탐색

 

인덱스 값이 있기 때문에 배열의 크기와 상관없이 바로 찾아갈 수 있다.

시간 복잡도는 O(1) 이다.

배열 원소 삽입

 

배열 a가 있고 1,2,3,4,5 총 5개의 원소를 가지고 있고 사이즈가 5일 때

6이라는 원소를 추가하려면 배열 a를 6개 사이즈의 배열로 재정의 해줘야한다.

 

 

배열 원소 삭제

 

a = {1,2,3,4,5} 

배열이 있고 a[2] = 3을 삭제하고 싶으면

 

1. a[2] 삭제

2. a[3],a[4]값을 앞으로 땡김

 

따라서 최종 배열의 모습은 a = [1,2,4,5] 이다.

 

원소 삽입, 삭제에 대한 시간복잡도는 O(N)이다.

 

리스트

 

원소들을 비연속적인 메모리 공간에 할당,
원소의 갯수가 가변적이며 삽입과 삭제가 자유로움,
삽입삭제 시간이 빠름.

리스트 탐색

 

리스트는 선형 탐색이기 때문에 원소 갯수만큼의 시간이 소요되므로

시간 복잡도는 O(N)이다.

 

예) head노트 부터 n번째 노드까지 순차적으로 순회해야 함

리스트 삽입, 삭제

 

삽입은 그냥 몇 번째 인덱스에 어느 값을 삽입해줄지 정하면 되고,

삭제는 배열과 같다.(삭제 후 뒤에 있는 원소 땡겨오기)

 

시간복잡도는 삽입, 삭제 둘다 O(N).

 

 

배열과 리스트의 차이

 

배열은 데이터 탐색 속도가 리스트보다 빠르며,

리스트는 데이터 삽입, 삭제가 특정 위치에서 O(1)로 빠르다.

 

ㄴ 리스트 특정 위치에서 데이터 삽입, 삭제 시간 복잡도가 O(1)인 경우

1. 리스트 끝에서 삽입, 삭제

2. 리스트 특정 위치에서 삽입, 삭제