More on linked lists in C++

Question. You are given a singly linked list, and are supposed to delete the m^{th} from last node.

Solution.

Firstly, we observe that this task would be much simpler and straightforward if we had a doubly linked list. We could start at the end of the list, and traverse through m nodes before reaching our desired node, after which we could delete it.

In a singly linked list, we do not have that ability to traverse in the backward direction and hence must think of an alternate strategy.

To make the notation clear, m=1 denotes that we wish to delete the last node of the linked list. m=2, 3 and so on follow naturally from that.

One method could be the following:-Traverse the linked list from the start of the list. Thus we can compute its length. Then traverse again from the beginning to the desired node (we can now do so since we know the length of the list) and delete it.

A more elegant technique and one which we would employ would use 2 pointers. The idea is the following:

Say we want the 4th from last node of the linked list. Make one pointer point to the 4th node of the list, and another to the start of the list. Then, move each pointer forward through the list in tandem until the one in front reaches the last node of the list. At that point, the one at the back points to the node which we wish to delete.

A small note on the above idea would be in place: When we want to delete a node, we need to be able to identify it when we are at the node before it. Only then will we be able to manipulate the “next” pointer of the node before the one which we wish to delete. With this in mind, we would need to slightly modify the idea mentioned above.

—-

The code can be written as follows:

// the function returns true if deletion was successful, and false otherwise.

// deletion can fail if the list is of size < m.

// Node ** head is a pointer to the head pointer of the list.

// void ** myData will point to the data contained in the deleted node pointer once the function call is        //  completed.

bool myDelete (Node **head, void **myData, int m)

{

if ( ! (*head) )

//empty list.

return false;

Node *front, *back; // front will be m nodes ahead of back.

back = front = *head;

for (int i = 1; i < m; i++)

{

if (! front)

// checking if the length of the list is < m.

return false;

front = front -> next;

}

 

// special case if list is of length 1 (note that in this case m is necessarily = 1.

*myData = (*head) -> data;

delete *head;

*head = 0;

 

//special case if we have to delete the first node.

// in this case, front would currently point to the last node.

Node *temp;

if ( ! (front -> next) )

{

temp = (*head) -> next;

*myData = (*head)-> data;

delete *head;

*head = temp;

}


// now that front is m nodes ahead of back, we move both forward until front reaches

// the end of the list.

// Since we need to know the node which precedes the node to be deleted, we will

// move the pointers forward until front->next -> next becomes null.

while ( ! (front -> next -> next ) )

{

front = front -> next;

back = back -> next;

}

// Now we need to delete back -> next.

// We do that using a temporary node pointer.

temp = back -> next;

*myData = temp -> data;

back -> next = temp -> next;

delete temp;

return true;

}

——

We need to make sure that boundary case are handled properly:

1. What if the list is empty?  — We have a separate test for that.

2. What if the list is of size < m? — We test that within the code.

3. What if the list is of length 1, and m=1? — We handle this case separately.

4. What if the list is of length 2, and m = 1 ?  —- the code handles it properly.

5. What if m equals the length of the list i.e. we need to delete the first node?  —- That case is handled separately in the code.

6. What if m =1 ? — The code handles it properly.

——

A good code should in general check for extreme cases where there is the possibility that the code might fail.

——-

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: