연결리스트란?

연결리스트의 각 원소 혹은 데이터를 노드(Node)라고 한다. 연결리스트는 노드들의 연결로 이루어져 있으며 각 노드는 포인터를 가진다.

단일 혹은 단방향 연결 리스트(Singly Linked List)의 경우 노드들은 오로지 다음 노드의 주소를 가리키는 포인터 하나만을 가진다. 반면, 양방향 또는 이중 연결리스트(Doubly Linked List)의 경우는 노드들이 다음과 이전 노드의 메모리를 보관할 수 있도록 두 개의 포인터를 가진다.

노드 pseudocode:

Node {
	T data;
	Node *next;
	Node *prev;
}

연결리스트의 장점으로는 데이터의 빠른 삽입과 삭제가 있는 반면, 탐색 연산의 처리 속도는 O(N)으로 느린편에 속한다. 탐색 연산이 데이터의 삽입과 삭제보다 중요하다면, 배열이나 해시테이블을 사용하는 것이 효과적이다.