# Deletion in a Linked List

Deletion in a linear linked list, like insertion, can be done in these ways-

• Deletion at the beginning
• Deletion at the end
• Deletion of a given node
• Deletion after a  node with given value
• Deletion before a node with given value
• Deletion at a given position

## Deletion at the Beginning

When a node has to be deleted at the beginning of the linked list, the original second node becomes the first node.  This is done by assigning the address stored in the LINK part of first node to START pointer.

## Deletion in a linked list at the End

After deleting node at the end of the linked list, the second last node becomes the last node.  This is done by traversing to the end of the Linked List. While traversing, the current node address PTR  is SAVE pointer and PTR pointer is updated with PTR->LINK.

At the end of traversal the last node’s address is stored in a pointer PTR and address of second last node in SAVE pointer. LINK part of the second last node is assigned the link part of last node. Since the last node’s LINK part is NULL, when it is assigned to LINK part of last node, it becomes the last node now.

## Deletion a node with given value

Deletion of a node with a given value, is done by following these steps –

• Traverse the linked list to locate the element which is to be deleted.  Store address of this node in a pointer PTR and its previous node’s address in SAVE pointer.
• Store value of LINK part of the node identified by PTR in LINK part of SAVE node.

## Deletion before a node with given value

A node can be deleted before a node with given value by following these steps

• Traverse the linked list to locate the element before which the new node is to be deleted. Store address of its previous node in SAVE pointer and the current node in PTR pointer. Here the DATA part of PTR’s next node (accessing PTR->LINK->DATA) is compared with the given value.
• Address stored in LINK part of the node identified by PTR in assigned to LINK part of SAVE node

## Deletion after a node with given value

A node can be deleted after a node with given value by following these steps

• Traverse the linked list to locate the element after which the node is to be deleted. Store address of this node in PTR pointer.