Linear Data Structures :: Deleting from a Linked List

Since the previous post discussed inserting a node into a linked list it is necessary to also discuss the deletion of a node from the list. There are multiple cases that need to be taken into consideration. Removing a node from the beginning, end, and inbetween. The steps of deleting form the list consist of first finding the node, next removing the node and finally repairing the link between the list by linking the node previous to the deleted node and the node immediatly following the deleted node.

The following is an example of a linked list. Each square is a node with a structure of a data field and a next. In order to delete the second node we would traverse through the list until the specific data is found. The links must be changed in order to maintain the proper structure as was mentioned before. The first and third square would then be linked.

BEFORE DELETION

AFTER DELETION

Deleting from the beginning or end is similar to what was previously shown. Deleting from the beginning is nothing more than setting the initial pointer to another location. Removal from the end of the list is similar in that we change only one pointer. The previous node must be set to be the end of the list by setting next to NULL.

Deleting and Inserting are not the only functions of linked lists. Searching and Sorting can also be used, often within deletion and insertion algorithims.