Support us


to write
more tutorials




to create new
visualizers




to keep sharing
free knowledge
for you


every dollar helps
Need help with a programming assignment? Get affordable programming homework help.

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.

Removal a node from this list with one node example

Remove first

In this case, first node (current head node) is removed from the list.

Remove first example

It can be done in two steps:
  1. Update head link to point to the node, next to the head.

    Remove first example, update head link

  2. Dispose removed node.

    Remove first example, 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.

Remove last example

It can be done in three steps:

  1. 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.

    Remove last example, update tail link

  2. Set next link of the new tail to NULL.

    Remove last example, set next link of the new tail to NULL

  3. Dispose removed node.

    Remove last example, 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.

Removal from a singly-linked list, general case

Such a removal can be done in two steps:

  1. Update next link of the previous node, to point to the next node, relative to the removed node.

    Removal from a singly-linked list, general case, updating previous next link

  2. Dispose removed node.

    Removal from a singly-linked list, node disposal

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

  1. Cormen, Leiserson, Rivest. Introduction to algorithms. (Theory)
  2. Aho, Ullman, Hopcroft. Data Structures and Algorithms. (Theory)
  3. Robert Lafore. Data Structures and Algorithms in Java. (Practice)
  4. Mark Allen Weiss. Data Structures and Problem Solving Using C++. (Practice)

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!

Leave a reply

Your name (optional):
Your e-mail (optional):
Message: