Skip to content

Yet another programming solutions log

Sample bits from programming for the future generations.

Technologies Technologies
  • Algorithms and Data Structures
  • Java Tutorials
  • JUnit Tutorial
  • MongoDB Tutorial
  • Quartz Scheduler Tutorial
  • Spock Framework Tutorial
  • Spring Framework
  • Bash Tutorial
  • Clojure Tutorial
  • Design Patterns
  • Developer’s Tools
  • Productivity
  • About
Expand Search Form

Linked List – insert element at position

farenda 2017-06-10 0

In this post we’ll implement another algorithm for Linked List – insert element at position. The algorithm works in linear time in the worst case.

Linked List insert element at position

We base our Linked List implementation on Node class, we’ve defined in the previous post.

public void insert(int position, T value) {
    Node<T> newNode = new Node<>(value);

    // insert as the new head?
    if (position == 0) {
        // The 1st case.
        newNode.next = head;
        head = newNode;
    } else {
        // The 2nd case.
        // start from the head:
        Node<T> node = head;
        // find position just before the expected one:
        while (--position > 0) {
            node = node.next;
        }
        // insert the new node:
        newNode.next = node.next;
        node.next = newNode;
    }
}

How it works

The insertion algorithm has to support two cases.

The first case is inserting the element at the head of the list – be it an empty list or just at index 0 in an existing list. To handle this correctly we have to be sure to not overwrite the old head with the new one.
The second case is inserting the element at a position other than the head of list. To do that we have to find the node just before the expected one and insert the new node there.
Because in the second case we may need to traverse whole Linked List, the worst time complexity of the algorithm is linear – O(n).
Both cases are handled in the above code.

JUnit tests

As always, to check that the algorithms actually works and inserts given elements at specified positions, we’ll write unit tests:

package com.farenda.tutorials.algorithms.lists;

import org.junit.Test;

import static org.junit.Assert.*;

public class LinkedListTest {

    private LinkedList<Integer> list = new LinkedList<>();

    @Test
    public void shouldInsertAtSpecifiedPosition() {
        list.insert(0, 2);
        assertEquals(1, list.size());
        list.printContent();

        list.insert(1, 3);
        assertEquals(2, list.size());
        list.printContent();

        list.insert(0, 1);
        assertEquals(3, list.size());
        list.printContent();
    }
}

When we run the tests, they will produce:

[2]
[2,3]
[1,2,3]

References:

  • Algorithms and Data Structures Tutorial
  • Basic Linked List constructs – add, count, print contents
Share with the World!
Categories Algorithms Tags algorithms, java, lists
Previous: Linked List add element at the end
Next: Linked List – remove element

Recent Posts

  • Java 8 Date Time concepts
  • Maven dependency to local JAR
  • Caesar cipher in Java
  • Java casting trick
  • Java 8 flatMap practical example
  • Linked List – remove element
  • Linked List – insert element at position
  • Linked List add element at the end
  • Create Java Streams
  • Floyd Cycle detection in Java

Pages

  • About Farenda
  • Algorithms and Data Structures
  • Bash Tutorial
  • Bean Validation Tutorial
  • Clojure Tutorial
  • Design Patterns
  • Java 8 Streams and Lambda Expressions Tutorial
  • Java Basics Tutorial
  • Java Collections Tutorial
  • Java Concurrency Tutorial
  • Java IO Tutorial
  • Java Tutorials
  • Java Util Tutorial
  • Java XML Tutorial
  • JUnit Tutorial
  • MongoDB Tutorial
  • Quartz Scheduler Tutorial
  • Software Developer’s Tools
  • Spock Framework Tutorial
  • Spring Framework

Tags

algorithms bash bean-validation books clojure design-patterns embedmongo exercises git gof gradle groovy hateoas hsqldb i18n java java-basics java-collections java-concurrency java-io java-lang java-time java-util java-xml java8 java8-files junit linux lists log4j logging maven mongodb performance quartz refactoring regex rest slf4j solid spring spring-boot spring-core sql unit-tests

Yet another programming solutions log © 2022

sponsored
We use cookies to ensure that we give you the best experience on our website. If you continue to use this site we will assume that you are happy with it.Ok