어레이와 링크드리스트

배열 Array

크기가 정해진 데이터의 공간. 한번 정해지면 바꿀 수 없음

배열은 각 원소에 즉시 접근이 가능하다(Index로 접근이 가능)

원소를 중간에 삽입, 삭제 하려면 모든 원소를 다 옮겨야 하기때문에하기때문에

 최악의 경우, 배열의 길이 N만큼을 옮겨야하므로 O(N)의 시간복잡도를 가진다.

⇒ 원소를 새로 추가하려면 새로운공간을 할당해야하므로 비효율적인 자료구조이다.

링크드리스트

리스트는 크기가 정해지지않은 공간.

연결고리를 통해 이어주기만 하면 자유자재로 생성이된다.

리스트의 경우, 특정원소에 접근을 하려면 연결고리를 따라서 탐색을 해야한다

⇒ 최악의 경우 모든 화물칸을 탐색해야하기때문에 O(N)의 시간복잡도를 가짐

 

**연결고리: 포인터 / 기차의 화물칸: 노드

 

원소를 중간에 삽입/삭제 하기위해서는 단순히 포인터만 변경하면된다.

⇒ 원소의 삽입/삭제 O(1)의 시간복잡도

 

 

즉각적인 데이터 조회 : Array

삽입&삭제 : Linked List