[CS 노트] : Linked List에 대해서..

Linked List는 tree, graph 등 다른 자료 구조를 구현할 때 사용되는 기본적인 자료구조로Node 구조체로 이루어져있으며 이 Node는 다음 Node의 주소 값을 가지고 있다. Linked List는 물리적인 메모리에서는 비연속적으로 저장되자만 Node의 특성(다음 Node의 주소를 가지고 있음)을 통해 논리적인 연속성을 가지게 된다.

 

Linked List는 데이터가 추가될 때 메모리를 할당한다. 즉, 메모리를 좀 더 효율적으로 사용할 수 있는 장점이 있다.

Node는 다음 주소 값을 가지고 있는데 첫 번째 노드는 head라는 포인터로 가리키고 있고 마지막 노드가 가리키는 주소는 NULL을 표시한다.

 

Array 처럼 메모리 연속성을 유지하지 않아도 되므로 메모리 사용이 자유로운데 다음 주소 값을 저장해야 하기 때문에 데이터 하나당 차지하는 메모리가 더 커진다.

 

데이터 삽입과 삭제는 O(1) 을 가지게 된다. 다음 주소 값만 변경하면 되기 때문이다. Linked List는 순차적으로 접근해야 하기 때문에 조회에 대한 시간 복잡도가 O(n)이 된다.

---

기출로 대비하는 개발자 전공면접 [CS 완전정복] 을 참고해서 공부하였습니다.