Singly-linked list. Removal (deletion) operation.
There are four cases, which can occur while removing the node. These cases are similar to the cases in add operation. We have the same four situations, but the order of algorithm actions is opposite. Notice, that removal algorithm includes the disposal of the deleted node, which may be unnecessary in languages with automatic garbage collection (i.e., Java).
List has only one node
When list has only one node, which is indicated by the condition, that the head points to the same node as the tail, the removal is quite simple. Algorithm disposes the node, pointed by head (or tail) and sets both head and tail to NULL.
Remove first
In this case, first node (current head node) is removed from the list.
- Update head link to point to the node, next to the head.
- Dispose removed node.
Remove last
In this case, last node (current tail node) is removed from the list. This operation is a bit more tricky, than removing the first node, because algorithm should find a node, which is previous to the tail first.
It can be done in three steps:
- Update tail link to point to the node, before the tail. In order to find it, list should be traversed first, beginning from the head.
- Set next link of the new tail to NULL.
- Dispose removed node.
General case
In general case, node to be removed is always located between two list nodes. Head and tail links are not updated in this case.
Such a removal can be done in two steps:
- Update next link of the previous node, to point to the next node, relative to the removed node.
- Dispose removed node.
Code snippets
All cases, shown above, can be implemented in one function with a single argument, which is node previous to the node to be removed. For remove first operation, the argument is NULL. For remove last operation, the argument is the node, previous to tail. Though, it's better to implement this special cases (remove first and remove last) in separate functions. Notice, that removing first and last node have different complexity, because remove last needs to traverse through the whole list.
Java implementation
public class SinglyLinkedList {
…
public void removeFirst() {
if (head == null)
return;
else {
if (head == tail) {
head = null;
tail = null;
} else {
head = head.next;
}
}
}
public void removeLast() {
if (tail == null)
return;
else {
if (head == tail) {
head = null;
tail = null;
} else {
SinglyLinkedListNode previousToTail = head;
while (previousToTail.next != tail)
previousToTail = previousToTail.next;
tail = previousToTail;
tail.next = null;
}
}
}
public void removeNext(SinglyLinkedListNode previous) {
if (previous == null)
removeFirst();
else if (previous.next == tail) {
tail = previous;
tail.next = null;
} else if (previous == tail)
return;
else {
previous.next = previous.next.next;
}
}
}
C++ implementation
void SinglyLinkedList::removeFirst() {
if (head == NULL)
return;
else {
SinglyLinkedListNode *removedNode;
removedNode = head;
if (head == tail) {
head = NULL;
tail = NULL;
} else {
head = head->next;
}
delete removedNode;
}
}
void SinglyLinkedList::removeLast() {
if (tail == NULL)
return;
else {
SinglyLinkedListNode *removedNode;
removedNode = tail;
if (head == tail) {
head = NULL;
tail = NULL;
} else {
SinglyLinkedListNode *previousToTail = head;
while (previousToTail->next != tail)
previousToTail = previousToTail->next;
tail = previousToTail;
tail->next = NULL;
}
delete removedNode;
}
}
void SinglyLinkedList::removeNext(SinglyLinkedListNode *previous) {
if (previous == NULL)
removeFirst();
else if (previous->next == tail) {
SinglyLinkedListNode *removedNode = previous->next;
tail = previous;
tail->next = NULL;
delete removedNode;
} else if (previous == tail)
return;
else {
SinglyLinkedListNode *removedNode = previous->next;
previous->next = removedNode->next;
delete removedNode;
}
}
Recommended books
- Cormen, Leiserson, Rivest. Introduction to algorithms. (Theory)
- Aho, Ullman, Hopcroft. Data Structures and Algorithms. (Theory)
- Robert Lafore. Data Structures and Algorithms in Java. (Practice)
- Mark Allen Weiss. Data Structures and Problem Solving Using C++. (Practice)
Previous: Adding a node to a singly-linked list
|
Contribute to AlgoList
Liked this tutorial? Please, consider making a donation. Contribute to help us keep sharing free knowledge and write new tutorials.
Every dollar helps!