Algorithm - Circular and Doubly Linked Lists

What is a circular list?

In the last node in the list, the link field contains null, a value that indicates the end. A circular list consists of pointing to the first node in the list. It is said to be open or linear succ(tail)=head.

Definition of the circular list by a pointer

pointer-driven circular list

1) Browse the list

Procedure path(L: ptr , p : ptr)
var pp:ptr
start
    pp := p
    repeat
         process (*pp.val)
         pp := *pp.link
    to (pp=p)
end

2) Insertion

Insert at the head

Insert in the lead

Integration outside the lead

Insert other than the top

See:
Inserting an item into a linked list.

3) Deletion

See: deleting an item from a linked list.

Pros and Cons

• The course has no special case.
• Three cases for insertion:
• At the top (empty list).
• At the top (non-empty list).
• Elsewhere than in the lead.
• Three cases for deletion;
• At the top (one-item list).
• At the top (list with more than one item).
• Elsewhere than in the lead

Definition of the circular list by a link

• The route is made from the current link that sentries it.
• Integration has no special case.
• We must make sure that the link to be eliminated is not the sentinel.