Question

Explain the mechanism of Deleting an element from front, rare and any of the Single Linked List?

Answer 1

Linked List example:

Deleting an element with a specific value from a linked list.

Here are some constraints for our example:

The list holds char's.

Deletion can occur anywhere in the list.

The delete operation will not return the element that we delete, it only need remove it from the list.

Now, recall the basic structure of a singly-linked list:

list | v --------- --------- --------- | a | --+---> | b | --+---> | c | 0 | --------- --------- ---------

In other words, there is a node for each element, where nodes consist of a part in which the element is stored and a link to the next node. The last node links to nothing (i.e., there are no nodes after it). Also, there is a link to the beginning of the list.

What do these links correspond to in C?

Answer: Pointers!

We'll consider our elements and nodes to have the following types:

typedef char elementT; ... typedef struct nodeTag { elementT element; struct nodeTag *next; } nodeT;

and thus, the pointer to the beginning of the list will be:

nodeT *list;

Aside: Although list is a pointer, we won't use the convention of naming it "listP". That's because we want to be abstract about what "list" is. I.e., users of the list don't really care whether it is implemented as a linked list or array or whatever--when they want to access a list, they just call list functions on this variable.

When the list is empty, what value will the pointer to the beginning have?

Answer: There are no nodes to point to, so it will be NULL!

Different cases:

There are a few steps to deleting a specific element from the list:

Find the node with the element (if it exists).

Remove that node.

Reconnect the linked list.

Update the link to the beginning (if necessary).

The order in which we perform these steps will depend on how we implement the deletion operation.

Note: For simplicity, if there are two elements with the value we want, we'll just remove the first one.

Finding the node in question is a matter of traversing the list and looking at each node's element.

Reconnecting the list once a node is to be removed is more interesting. Let's consider at least 3 cases:

Removing a node from the beginning.

Removing a node from the middle.

Removing a node from the end.

Removing from the beginning

When removing the node at the beginning of the list, there is no relinking of nodes to be performed, since the first node has no preceding node. For example, removing node with a:

list | v --------- --------- --------- | a | --+---> | b | --+---> | c | 0 | --------- --------- ---------

However, we must fix the pointer to the beginning of the list:

list | +-------------+ | v --------- --------- --------- | a | --+---> | b | --+---> | c | 0 | --------- --------- ---------

Removing from the middle

Removing a node from the middle requires that the preceding node skips over the node being removed. For example, removing the node with b:

list | v --------- --------- --------- | a | --+--+ | b | --+---> | c | 0 | --------- | --------- --------- | ^ +----------------+

This means that we need some way to refer to the node before the one we want to remove.

Removing from the end

Removing a node from the end requires that the preceding node becomes the new end of the list (i.e., points to nothing after it). For example, removing the node with c:

list | v --------- --------- --------- | a | --+---> | b | 0 | | c | 0 | --------- --------- ---------

Note that the last two cases (middle and end) can be combined by saying that "the node preceding the one to be removed must point where the one to be removed does