알고리즘 - 순환 및 이중 연결 목록
순환 목록이란 무엇입니까?
목록의 마지막 노드에서 링크 필드에는 끝을 나타내는 값인 null이 포함되어 있습니다. 순환 목록은 목록의 첫 번째 노드를 가리키는 것으로 구성됩니다. 개방 또는 선형 succ(tail)=head라고 합니다.
포인터에 의한 순환 목록의 정의
|
| 포인터 기반 순환 목록 |
1) 목록 찾아보기
|
|
|
var pp:ptr
start
pp := p
반복
프로세스(*pp.val)
pp := *pp.link
to (pp=p)
end
2) 삽입
머리에 삽입
|
| 리드 에 삽입 |
선두 주(lead) 외부의 통합
|
| 상단 이외의 삽입 |
참조:
연결된 목록에 항목 삽입
3) 삭제
|
참조: 연결된 목록에서 항목 삭제.
장점과 단점
- 이 코스에는 특별한 경우가 없습니다.
- 삽입을 위한 세 가지 경우:
- 맨 위(빈 목록).
- 맨 위 (비어 있지 않은 목록).
- 선두가 아닌 다른 곳에서.
- 삭제에 대한 세 가지 경우;
- 맨 위(단일 항목 목록)에 있습니다.
- 맨 위(둘 이상의 항목이 있는 목록)
- 선두가 아닌 다른 곳에서
링크에 의한 순환 목록의 정의
- 경로는 해당 경로를 전송하는 현재 링크에서 만들어집니다.
- 통합에는 특별한 경우가 없습니다.
- 제거할 링크가 센티넬이 아닌지 확인해야 합니다.