[자료구조] 배열, 연결리스트 시간복잡도 비교

 

* 시간복잡도 비교 (worst case)

	배열	한방향 연결리스트	양방향 연결리스트
읽기/쓰기	O(1)
moveAfter/ Before	O(n)		O(1)
pushFront	(insert 라고 보면 될듯)  O(n)	O(1)	O(1)
pushBack	(append)  O(1)	O(n)	O(1)
popFront	(pop(0))   O(n)	O(1)	O(1)
popBack	(pop)  O(1)	O(n)	O(1)
Insert	(insert(3))  O(n)	O(n)	O(1)
Remove	(remove)  O(n)	O(n)	O(1)
Search	O(n)	O(n)	O(n)
Index/ Count	O(n)
	append, pop 연산이 평균 O(1)시간이다. resize가 일어나지 않는 한 O(1) 걸리고, append할 때마다 resize가 발생하지 않고, 가끔 발생하므로 그냥 O(1)이라고 생각한다	한방향에서는 next=None인 애가 tail이다.	search만 O(n) 걸리고, 나머지는 다 O(1) 걸린다. 링크가 다 연결되어 있으므로 각자의 링크만 변경시켜주면 되니까. search만 head에부터 시작해서 찾아야되니까 오래 걸린다.

 

배열은 읽기, 쓰기 할 때 값이 저장된 곳의 주소를 아니까, O(1)시간만 걸려 매우 빠르게 계산할 수 있다 

 

 

연결리스트는 head, tail이 있다.

한방향은 기본적으로 항상 head에서부터 시작해서, 쭉 next를 따라가면서 찾아야하므로, head의 위치를 아는 front연산 제외하고는 다 O(n) 시간 걸린다

 

 

 

반면, 양방향 연결리스트는 head, tail과 앞뒤 링크가 모두 있으므로