배열은 메모리의 연속된 위치에 각 원소들이 저장되어있고, 연결 리스트는 여기저기 흩어져있는 원소들의 특정 위치에서 삽입과 삭제를 상수 시간에 수행하기 위해 이전 원소에서 다음 원소를 가리키는 “포인터”로 구현한다.

struct ListNode {
	int element; 
	ListNode *prev, *next;
}

C++에서는 연결리스트를 list라는 STL을 사용해서 구현한다.

조세푸스 문제