Linked List (링크드 리스트, 연결 리스트)

개념 및 용어
링크드 리스트의 개별 데이터들을 원소(element) 또는 노드(node)라고 함.
각 노드는 다음 노드의 주소를 가지고 있는데 이 걸 다음링크(next link) 또는 다음 포인터(next pointer)라고 함.
그외 data, information, value, cargo, payload등의 필드를 가지고 있음.
리스트의 첫번째 노드를 헤드(head)라고 함.

종류
싱글 링크드 리스트(Singly linked list)
노드가 데이터 필드와 다음 노드를 가르키는 필드로 구성됨.

더블 링크드 리스트(Doubly linked list)
각 노드들이 양옆의 노드에 대한 링크를 가지고 있음.

다중 링크드 리스트(Multiply linked list)
각 노드들이 링크에 대한 필드를 2개 이상가지고 있음.

원형 리스트(Circular list)
리스트의 마지막 원소가 링크 필드에 null이 아니라 첫번째 원소를 가리키도록 함.

다른 자료구조와의 처리시간 비교

	링크드리스트	배열	동적배열	균형트리
인덱싱(Indexing)	Θ(n)	Θ(1)	Θ(1)	Θ(log n)	Θ(log n)
시작부분에 삽입/삭제	Θ(1)	N/A	Θ(n)	Θ(log n)	Θ(1)
마지막에 삽입/삭제	Θ(n)	N/A	Θ(1) amortized	Θ(log n)	Θ(log n) updating
가운데 삽입/삭제	search time + Θ(1)	N/A	Θ(n)	Θ(log n)	Θ(log n) updating
소모되는 공간 (평균)	Θ(n)	0	Θ(n)	Θ(n)	Θ(n)

참조
1. https://en.wikipedia.org/wiki/Linked_list
2. http://mirror.enha.kr/wiki/%EC%97%B0%EA%B2%B0%20%EB%A6%AC%EC%8A%A4%ED%8A%B8#s-3.3