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 – remove element

farenda 2017-06-15 0

As many other algorithms in Linked List – remove element from given position runs in linear time. Here we are going to implement it to better understand how it works.

In previous posts we’ve implemented add, count, print contents, and insert methods for a Linked List. Now we will implement removal of element from selected position.

Linked List – remove element at position

As previously, we base our Linked List implementation on Node class, we’ve defined in the first post.

public void remove(int position) {
    Node<T> prev = null, node = head;
    // Find node to remove:
    while (position > 0 && node != null) {
        --position;
        prev = node;
        node = node.next;
    }
    // If exists, unpin it from the list:
    if (node != null) {
        if (prev == null) {
            // Removed 1st, so change the head:
            head = node.next;
        } else {
            // Just connect prev with next:
            prev.next = node.next;
        }
    }
}

How it works

The algorithm consists of two parts. First, we have to find the node we want to remove and remember its predecessor, so that we could connect it to the next node.
In the second part, if the node was found, we have to handle two cases. If we remove a node from the first position, it means we are removing the head, therefore we have to promote the next node to be the new head. In every other case we just need to connect previous node with the node after the removed one.

Performance

It’s pretty clear that in the worst case – removal of element from the last position – we have to iterate through whole Linked List. Thus the algorithm runs in linear time – O(n).

Unit Tests

Let’s write a simple unit tests to see how the algorithm works:

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 shouldRemoveElements() {
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        list.printContent();

        list.remove(3);
        assertEquals(3, list.size());
        list.printContent();

        list.remove(0);
        assertEquals(2, list.size());
        list.printContent();

        list.remove(0);
        assertEquals(1, list.size());
        list.printContent();

        list.remove(0);
        assertEquals(0, list.size());
        list.printContent();
    }

}

The above code produces the following output:

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

References:

  • Algorithms and Data Structures Tutorial
Share with the World!
Categories Algorithms Tags algorithms, java, lists
Previous: Linked List – insert element at position
Next: Java 8 flatMap practical example

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