자료구조 - Linked list

Linked List 링크드 리스트 연결 리스트

데이터를 링크로 연결해서 관리하는 자료구조. 

노드라고 불리는 기본단위로 이루어져 있으며 노드는 데이터+포인터로 구성. (Pointer - 노드의 연결정보)

메모리상에서 연속성이 보장되지 않으므로 원하는 노드에 접근하기 위해서는 헤드(시작노드)부터 순차적으로 데이터에 접근해야한다. 

이러한 특성 때문에 모든 연산의 시간복잡도가 O(n)의 복잡도를 띄는 특징이 있다. 데이터를 추가 삭제하는 연산 자체는 고정된 프로세스를 거치므로 자료의 크기와 관계가 없지만 해당 연산을 하기위해 목표 노드에 접근하는 연산이 자료크기에 정비례하는 연산을 필요로 하기때문.