[자료구조] Linked List

Linked List란? (tree와 graph를 구현할때 자주 사용)

Linked List는 Node라는 구조체로 이루어져 있고 Node는 데이터 값과 다음 Node의 주소값으로 이루어져 있다.

물리적인 메모리상으로는 비연속적으로 저장되지만 각각의 Node가 다음 Node를 가르키기 때문에 논리적으로는 연속성을 가진 자료구조다.

 

시간복잡도

데이터 삽입: O(1) -> Node의 다음 주소값만 바꿔주면 되기 때문에

데이터 삭제: O(1) -> Node의 다음 주소값만 바꿔주면 되기 때문에

데이터 조회: O(n) -> 첫번째 노드부터 순차적으로 검색

데이터 검색: O(n)