Write algorithm to delete last node in circular linked list?

Answer 1

This depends on whether the list is singly or doubly(or multiply) linked, and on the actual implementation of the list. For example, you can write a CDLL(circular doubly linked list) without maintaining your beginning or ending nodes, using only a current pointer, thus this question doesn't really apply as there would be no "last" node and thus it would be like deleting any node.

A typical implementation of a circular singly-linked list (CSLL) list actually maintains the pointer to the last element (hence it's FIFO nature) and thus there are both last and first nodes.

This deletion is a little tricky. Consider that you have situations where the next pointer will point to the current element. On the other hand, you also have a situation where there are n-values that you have to iterate over to find the next-to-last value. Typically you would delete the first node in these lists, again dictated by the FIFO nature of these lists, but deletion of the last node is also not impossible.

set struct node *last to list->end

if (list->end->next == list->end){

set list->end to null (leaving an empty list)

} else {

while(true){

if(last->next == list->end){

break

}

set last to last->next

}

set link->last to list->end->next (this temporarily sets list's end node to current first node)

free last->next (frees the last node)

set last->next to list->end (set the new last node next pointer to the first node)

set list->end to last (set the list's end node to the new last node)

}