How many pointers will have to be changed if a node is deleted from a linear linked list?

Answer 1

For a singly-linked list, only one pointer must be changed. If the node about to be deleted (let's call it node for the sake of argument) is the head of the list, then the head node pointer must be changed to node->next. Otherwise, the node that comes before the deleted node must change its next pointer to node->next.
Note that given a singly-linked node has no knowledge of its previous node, we must traverse the list from the head in order to locate that particular node, unless the node is the head of the list:

void remove (List* list, Node* node) {

if (!list !node) return; // sanity check!

if (list->head == node) {

list->head = node->next;

} else {

Node* prev = list->head;

while (prev->next != node) prev = prev->next; // locate the node's previous node

prev->next = node->next;

}

}

Note that the remove function only removes the node from the list, it does not delete it. This allows us to restore the node to its original position, because the node itself was never modified (and thus still refers to its next node in the list). So long as we restore all removed nodes in the reverse order they were removed, we can easily restore the list. In order to delete a node completely, we simply remove it and then free it:

void delete (List* list, Node* node) {

if (!list !node) return; // sanity check!

remove (list, node);

free (node);

}

For a doubly-linked list, either two or four pointers must be changed. If the node about to be deleted is the head node, then the head node pointer must be changed to n->next and n->next->prev must be changed to NULL, otherwise, n->prev->next becomes n->next. In addition, if the node about to be deleted is the tail node, then the tail node pointer must be changed to n->prev and n->prev->next must be changed to NULL, otherwise, n->next->prev becomes n->prev.


Deletion from a doubly-linked list is generally quicker than deletion from a singly linked list because a node in a doubly-linked list knows both its previous node and its next node, so there's no need to traverse the list to locate the previous node to the one being deleted.

void remove (List* list, Node* node) {

if (!list !node) return; // sanity check!

if (list->head == node) {

list->head = node->next;

node->next->prev = NULL;

} else {

node->prev->next = node->next;

}

if (list->tail == node) {

list->tail = node->prev;

node->prev->next = NULL;

} else {

node->next->prev = node->prev;

}

}

Again, to physically delete the node we simply remove and then free the node:

void delete (List* list, Node* node) {

if (!list !node) return; // sanity check!

remove (list, node);
free (node);
}

Answer 2

One in each element.