A Journey 2 Eternity

Delete an item from a Singly Linked List

Posted on: August 29, 2008

Because elements in a singly-linked list are maintained exclusively with links to the next element, any insertion or deletion of elements in the middle of a list requires modification of the previous element’s link. This may require a traversal of the list, because there’s no other way to find a preceding element. Special care must be taken when dealing with the head of the list.

bool DeleteElement( ListElement **head, ListElement *deleteMe )
{
	ListElement *elem = *head;

	// special case for head
	if( deleteMe == *head ) {
		*head = elem->next;
		delete deleteMe;

		return true;
	}

	while( elem ) {
		if( elem->next == deleteMe ) {
			// elem is element preceding deleteMe
			elem->next = deleteMe->next;
			delete deleteMe;

			return true;
		}
		elem = elem->next;
	}

	// not found
	return false;
}
Advertisements

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

Pages

Categories

August 2008
M T W T F S S
« Apr   Sep »
 123
45678910
11121314151617
18192021222324
25262728293031

Blog Stats

  • 26,968 hits
%d bloggers like this: