delete last node of a circular linked list

[vgoel38]

can i delete last node(that points to the first node) of the circular linked list in constant time?

[pogrady]

If you mean constant time as the time it takes to delete an element of a list independent of its size, then i think you can since you have a pointer to the last element, and no iteration is necessary.

[vgoel38]

If I follow your method, then how will I make the second-last node point to first node?

[HoneyBoy]

Lets call the target node to delete (the last one): discard

// Set pointers to the previous and next nodes of discard
NodePtr* prev = discard -> getPreviousLink( );
NodePtr* next = discard -> getNextLink( );

// Bypass discard, connect the two nodes (in this case the second-last and first)
prev -> setNextLink(next);
next -> setPreviousLink(prev);

delete discard;

This can be done in constant time since you can simply find the last node by getting the previous link of the first node.