Linked List

- 메모리 공간 상에서 각 노드들이 연속적으로 이루어져 있지 않고 흩어져 있으며, 각각의 노드가 자신의 다음 위치를 알고 있는 형태

- 검색시 논리적 저장순서와 물리적 저장순서가 다르기 때문에 데이터 검색 시 첫 노드부터 찾아야한다.

 

 

검색

- 시간 복잡도: O(n)

삭제

- 시간 복잡도: O(n)

- 하지만 Array 보다 빠르다

삽입

- 시간 복잡도: O(n)

 

메모리 할당

- 동적 메모리 할당

- 새로운 node가 추가 될 때 runtime에 할당 된다.

 

tree 에서 사용해 보자