자료구조에서의 시간복잡도( 연결리스트, 배열 )

자료구조	접근	탐색	삽입	삭제
배열	O(1)	O(n)	O(n)	O(n)
이중 연결 리스트	O(n)	O(n)	O(1)	O(1)
스택	이중 연결리스트와 동일 ( 연결리스트로 구현 가능 )
큐

연결 리스트 - 삽입, 삭제 : O(1)

클래스LinkedList 는

head(맨 앞에 있는 노드)를 필드로 갖는다.

 

head를 이용하면 삽입,삭제가 원소 수와 상관없이 이루어진다.

삭제

head = head.next;

삽입

newHead.next = head;
head = newHead;

 

연결 리스트 - 접근 : O(n)

클래스LinkedList는 head(맨 앞에 있는 노드)만을 필드로 갖고

, 각 노드는 data와 다음노드를 가르키는 포인터(next) 만을 필드로 갖는다.

 

head부터 시작해서 next값을 통해, 해당 index까지 이동해야함

Node01 current = head;
		
for (int i =0; i < index; i++) { // index에 해당하는 노드까지 이동
	current = current.next;
}

 

배열  - 삽입, 삭제 : O(n)

배열은 생성될때 크기(셀의 개수) 가 고정되어서, 크기가 변하기 위해선 다시 배열을 생성해야함

배열  - 접근 : O(1)

배열은 index로 해당 셀에 바로 접근 가능하다

 

탐색

탐색은 접근을 기반으로 한다. (연결리스트) < (배열)

 

데이터 추가및 삭제는 연결리스트
탐색은 배열