| 연결 리스트의 종류 |
: 연결 리스트에는 단일 연결 리스트(singly-linked list), 이중 연결 리스트(doubly-linked list), 원형 연결 리스트(circularly-linked list) 이렇게 세가지 기본 유형이 있다.
| 단일 연결 리스트 |
: 단일 연결 리스트는 각각 다음 원소를 가리키는 next 포인터 또는 레퍼런스(연결 링크)가 들어있는 데이터 원소들로 구성된다. 리스트의 마지막 원소에는 빈 링크 또는 널 링크가 들어간다. 아래와 같이 구현 될 수 있겠다
next 포인터를 구조체나 클래스의 맨 앞 쪽에 넣어두면 그 원소에 어떤 데이터가 들어가든 제대로동작하는 포괄적인 리스트 처리 루틴을 더 쉽게 만들 수 있따는 장점이 있다. 연결 리스트를 구현할 때 몇 가지 주의해야 할 특별 케이스 및 함정이 있는데, 단일 연결 리스트의 연결 링크는 다음 원소를 가리키는 포인터(or 레퍼런스)만으로 구성되기 때문에 리스트를 한 방향으로만 종주할 수 있다. 따라서 리스트를 완전히 종주하려면 반드시 첫 번째 원소부터 시작해야 한다. 바꿔 말하면 리스트에 있는 모든 원소들을 찾아내기 위해서는 반드시 첫 번째 원소에 대한 포인터 또는 레퍼런스가 있어야만 한다. 그래서 연결리스트라는 용어를 어떤 연결 리스트의 첫 번째 원소라는 뜻으로 쓰는 경우도 종종있다. 단인 연결 리스트의 첫 번째 원소는 리스트의 헤드라고 부르며 마지막 원소는 테일(tail)이라고 부른다.
| 이중 연결 리스트 |
| 원형 연결 리스트 |
: 원형 연결 리스트에는 헤드나 테일이 없다. 원형 연결 리스트의 종주 문제를 따질 때는 무한루프가 생기지 않도록 주의해야 한다. 시작점을 제대로 파악해놓지 않으면 리스트를 끝임없이 종주해야 하는 상황이 일어난다.