연결 리스트(이중연결, 단방향, 순환)의 헤드 포인터와 헤더 노드

단방향 연결 리스트와 순환 연결 리스트는 보통 헤드 포인터를 사용한다.

헤드 포인터는 연결리스트의 맨 처음 노드인 시작 노드를 가리킨다.

이중 연결 리스트는 양방향으로 연결되어 있는 리스트이므로 2가지 포인터를 사용한다.

다음 노드는 물론 이전 노드까지 접근 가능한 리스트이다.

이중 연결 리스트는 헤더 노드를 사용하는데 노드 자체를 사용하여 추가와 삭제를 용이하게 한다.

헤더 노드는 리스트의 첫번째 노드와 마지막 노드를 가리키는 포인터 값을 가진다.

왜 이중 연결 리스트는 헤더 노드를 사용해야 할까?

이중 연결 리스트는 pNode==pNode->pLLink->pRLink==pNode->pRLink->pLLink를 만족해야 한다.

만약 헤드 포인터를 사용하게 되면 pNode가 첫번째 노드일 경우에 pNode->pLLink는 노드가 아닌 단순한 헤드 포인터이므로(노드만 가리키는 포인터이므로) pNode->pLLink->pRLink가 성립될 수 없다. 노드의 추가와 삭제시에 고려해야 할 점이 늘어나므로 헤드 포인터가 아닌 헤더 노드로 구현하는 것

생각해봤는데 헤드 포인터를 사용하면 그 노드를 가리키기만 할 뿐 RLink는 존재하지 않기 때문에

헤드 포인터는 RLink를 가지고 있지 않으므로 성립이 안되는 듯함!

헤드 포인터에는 양방향 포인터인 LLink와 RLink가 존재하지 않는다고 생각한다.

그 노드를 가리키는 포인터이므로 LLink와 RLink는 가리키는 노드가 갖고 있는 것이지 포인터 자체가 갖고 있는것이 아니기 때문?

사실 pNode->LLink도 포인터라는게 이해가 잘 안간다. 머릿속에서 꼬이는 거 같다.

++

이거 보니까 좀 더 이해 되는데 자칫하면 무한루프 돌 수 있어서 인 듯

처음과 끝을 알 수가 없어짐

헤더 노드를 이용하면 이렇게 됨

무한루프에서 벗어날 수 있음

pNode->pLLink라는 것이 그냥 전 노드 혹은 전 포인터를 말하는 거 같음

http://web.skhu.ac.kr/~mckim1/Lecture/DS/dna/class04/class04_05.html