[자료구조] Linked List

Linked List

데이터 요소들이 노드(Node)로 연결되어 있는 선형 데이터 구조

특징

논리적 저장 순서와 물리적 저장 순서가 다르다.
노드 내부에는 앞, 뒤 노드의 주소 가지고 있다.
이를 통해서 선형 접근을 지원한다.

접근 시 O(n) 시간이 소요된다.
이는 접근 방식이 Sequential Access(순차접근)이기 때문이다.

삽입/삭제 시 O(1) 시간이 소요된다.
하지만 삽입/삭제할 데이터에 접근할 시간도 필요하기 때문에
전체적으로 보면 O(n) 시간이 소요된다.

Array와 달리 동적으로 메모리를 할당한다.
이러한 이유로 데이터가 자주 변경되는 구조에 유용하다.