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. Addition (insertion) operation.

Insertion into a singly-linked list has two special cases. It's insertion a new node before the head (to the very beginning of the list) and after the tail (to the very end of the list). In any other case, new node is inserted in the middle of the list and so, has a predecessor and successor in the list. There is a description of all these cases below.

Empty list case

When list is empty, which is indicated by (head == NULL)condition, the insertion is quite simple. Algorithm sets both head and tail to point to the new node.

Insertion to the empty list example

Add first

In this case, new node is inserted right before the current head node.

Insertion before head example

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

    Insertion before head example, update new node next link

  2. Update head link to point to the new node.

    Insertion before head example, update head link

Add last

In this case, new node is inserted right after the current tail node.

Insertion after tail example

It can be done in two steps:

  1. Update the next link of the current tail node, to point to the new node.

    Insertion after tail example, update current tail next link

  2. Update tail link to point to the new node.

    Insertion after tail example, update tail link

General case

In general case, new node is always inserted between two nodes, which are already in the list. Head and tail links are not updated in this case.

Insertion to a singly-linked list, general case

Such an insert can be done in two steps:

  1. Update link of the "previous" node, to point to the new node.

    Insertion to a singly-linked list, general case, updating previous next link

  2. Update link of the new node, to point to the "next" node.

    Insertion to a singly-linked list, general case, updating new node next link

Code snippets

All cases, shown above, can be implemented in one function with two arguments, which are node to insert after and a new node. For add first operation, the arguments are (NULL, newNode). For add last operation, the arguments are (tail, newNode). Though, this specific operations (add first and add last) can be implemented separately, in order to avoid unnecessary checks.

Java implementation

public class SinglyLinkedList {

     

 

      public void addLast(SinglyLinkedListNode newNode) {

            if (newNode == null)

                  return;

            else {

                  newNode.next = null;

                  if (head == null) {

                        head = newNode;

                        tail = newNode;

                  } else {

                        tail.next = newNode;

                        tail = newNode;

                  }

            }

      }

 

      public void addFirst(SinglyLinkedListNode newNode) {

            if (newNode == null)

                  return;

            else {

                  if (head == null) {

                        newNode.next = null;

                        head = newNode;

                        tail = newNode;

                  } else {

                        newNode.next = head;

                        head = newNode;

                  }

            }

      }

 

      public void insertAfter(SinglyLinkedListNode previous,

                  SinglyLinkedListNode newNode) {

            if (newNode == null)

                  return;

            else {

                  if (previous == null)

                        addFirst(newNode);

                  else if (previous == tail)

                        addLast(newNode);

                  else {

                        SinglyLinkedListNode next = previous.next;

                        previous.next = newNode;

                        newNode.next = next;

                  }

            }

      }

}

C++ implementation

void SinglyLinkedList::addLast(SinglyLinkedListNode *newNode) {

      if (newNode == NULL)

            return;

      else {

            newNode->next = NULL;

            if (head == NULL) {

                  head = newNode;

                  tail = newNode;

            } else {

                  tail->next = newNode;

                  tail = newNode;

            }

      }

}

 

void SinglyLinkedList::addFirst(SinglyLinkedListNode *newNode) {

      if (newNode == NULL)

            return;

      else {

            if (head == NULL) {

                  newNode->next = NULL;

                  head = newNode;

                  tail = newNode;

            } else {

                  newNode->next = head;

                  head = newNode;

            }

      }

}

 

void SinglyLinkedList::insertAfter(SinglyLinkedListNode *previous,

            SinglyLinkedListNode *newNode) {

      if (newNode == NULL)

            return;

      else {

            if (previous == NULL)

                  addFirst(newNode);

            else if (previous == tail)

                  addLast(newNode);

            else {

                  SinglyLinkedListNode *next = previous->next;

                  previous->next = newNode;

                  newNode->next = next;

            }

      }

}

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: