A Journey 2 Eternity

When we want to remove all the elements from a linked list, the natural inclination is to use a single pointer to traverse the list, freeing elements as we go. A problem arises, however, when this is implemented. Do we advance the pointer or free the element first? If we advance the pointer first, then the freeing is impossible because we overwrote the pointer to the element to be freed. If we free the element first, advancing the pointer is impossible because it involves reading the next pointer in the element that was just freed. The solution is to use two pointers.

void DeleteAllElement( ListElement **head )
{
	ListElement *deleteMe = *head;
	while( deleteMe ) {
		ListElement *next = deleteMe->next;
		delete deleteMe;

		deleteMe = next;
	}

	*head = NULL;
}

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;
}

Operations on any but the first element of a linked list require traversal of some elements of the list, and you must always check for the end of the list.

ListElement Find( ListElement head, int data )
{
	while( head != NULL && head.data != data ) {
		head = head.next;
	}

	return head;
}

The head element of a singly-linked list must always be tracked; otherwise, the list will be lost in memory. This means that the pointer or reference to the head of the list must be updated when a new element is inserted ahead of the first element or when the existing first element is removed from the list. Tracking the head element becomes a problem when you alter the list inside a function or method, because the caller must be made aware of the new head element.

bool InsertInFront( ListElement **head, int data )
{
	ListElement *newElem = new ListElement;
	if( !newElem ) {
		return false;
	}

	newElen->data = data;
	*head = newElem;

	return true;
}