The middle of a list is one record with equal number of records to the left and right (assuming the list has odd number of elements). If this number is even, the middle consists of two records. Write a pseudo-code procedure to delete the middle (one or two) record(s) of a doubly linked list without counting first or knowing the total number of elements in the list.
At first you might think to yourself, “Wait, how would I delete the middle element(s) of a doubly linked list without counting or knowing the number of elements in the list?” There is actually an easy solution to this: Use the head and tail pointers and move inward until they’ve met (i.e. they are equal). This works well if the number of elements is odd. If the number of elements is even, we’ll have to delete two “middle” nodes.
Note: We are using a Doubly Linked List ADT in this example and assuming that the following methods exist:
- first() – returns the head
- last() – returns the tail
- remove( node ) – removes a specified node from the list
- after( node ) – returns the node after a specified node in the list
- before( node ) – returns the node before a specified node in the list
Pseudo-code
// Procedure DeleteMiddle( LinkedList list ):
// Input: LinkedList list
// Output: LinkedList list such that the middle (one or two) elements of the list have been deleted.
currentLeft = list.first(); // Head
currentRight = list.last(); // Tail
while ( currentLeft != null && currentRight != null ) {
// List is odd, delete one node
if ( currentLeft == currentRight ) {
list.remove( currentLeft );
}
// List is even, delete two nodes
else if ( list.after( currentLeft ) == list.before( currentRight ) ) {
list.remove( currentLeft );
list.remove( currentRight );
}
currentLeft = list.after( currentLeft );
currentRight = list.before( currentRight );
}
return list;