Array, Linked List ( 배열, 연결리스트 )

✔️Array ( 배열 )

◾ 논리적인 순서와 물리적인 순서가 같기 때문에 데이터에 엑세스 하기쉽다. (인덱스로 쉽게 탐색 가능)

◾ 삽입, 삭제 연산 후에 연속적인 물리적 순서를 유지하기 위해 나머지 원소들을 이동 시키는 오버헤드가 발생한다.

 

⏱️ 시간복잡도

◾ 탐색 : index를 통해 O(1)에 해당 원소로 접근 가능

◾ 삽입 : 원소를 삽입하려면 배열내의 원소를을 shift 해줘야한다.  O(n) 시간

◾ 삭제 : 삭제한 원소보다 큰 index를 갖는 배열내의 원소들을 shift 해줘야한다. O(n) 시간

 

💾 소스 코드

#include<stdio.h>

int main() {
	int arr[10] = { 0,1,2,3,4,5,6,7,8,9 };

	for (int i = 0; i < 10; i++) {
		printf("%d ", arr[i]);
	}

	return 0;
}

 

👀 시각화

array 시각화

 

---

✔️ Linked List ( 연결 리스트 )

◾ 원소의 논리적인 순서와 물리적인 순서가 일치하지 않아도 된다.

◾ 각 원소에 저장되어 있는 다음 원소의 주소에 의해 순서가 연결되는 방식이다.

◾ 삽입, 삭제 연산 시 물리적인 순서를 맞추기 위한 오버헤드가 발생하지 않는다.

◾ 탐색시 인덱스가 없기 때문에 첫 노드부터 원하는 노드까지 순차적으로 탐색해야한다.

 

⏱️ 시간복잡도

◾ 조회 : 원하는 원소를 찾으려면 첫 번째 원소부터 확인해야한다. O(N) (논리적 저장 순서와 물리적 저장 순서가 일치하지 않기 때문)

◾ 삽입 : 삽입을 위한 탐색 때문에 O(N)의 시간이 걸린다. 

◾ 삭제 : 삭제를 위한 탐색 때문에 O(N)의 시간이 걸린다.

 

💾 소스 코드

 

 

👀 시각화

linked list 시각화