Java Arraylist Remove Time Complexity

Overview

The use of the remove method can be found more frequently in the Java Drove framework. The remove method removes the specified chemical element from any collection of objects. Yet, the ways to remove an object might differ in one case or the other.

Syntax

The remove() method in ArrayList equips you with the ability to remove an element in two dissimilar ways.

To begin with, yous are supposed to know the object itself to get it removed from the list.

                                                                            boolean                                                                  remove                                                                  (Object obj)                      ;

The specified object will be removed from the list and the subsequent objects will be shifted past 1 place to the left.

We know that ArrayList allows the insertion of duplicate objects. So, if the same object is nowadays at multiple positions, the above remove method will remove its first occurrence only.

The other style is to signal the index of the element as a parameter.

                                                                            Object                                            remove                      (                      int                                              alphabetize)                      ;

The to a higher place method removes the element nowadays at the specified index and shifts the subsequent elements by one place to the left.

Parameters of remove() in Java

The remove method takes a single parameter.

obj: the object in the ArrayList to be removed.

Alternatively,

index: the element at the mentioned position will be removed.

Return values of remove() in Java

The remove method returns true if an object passed as a parameter is removed from the listing. Otherwise, it returns false.
The remove method returns the removed element if an index is passed.
- It throws IndexOutOfBoundsException if the specified index is not in range.
Fourth dimension complexity of both the methods will be O(N) .

Instance

The given figure also shows the use of boxing an argument so that the remove() method considers the bodily object instead of the ASCII value of any char data.

Return values of remove() in Java

The return value depends on the parameter of the remove method.

                                                            list.remove(Grapheme.valueOf(                  'A'                  ));

Since character A is present inside the list, the remove method volition remove the character and render truthful.

Simply, what if we pass a character that is not present in the ArrayList? The remove method but returns false in this instance.

Time Complexity of remove(int alphabetize) Method

The fourth dimension complexity of remove(int index) Method is O(Due north).

Reason:

ArrayList implements RandomAccess interface, so accessing any random element volition be done in O(i) complexity. Still, since the remaining elements besides need to be shifted by one place to their left, the overall time complexity becomes O(N).

Alternatively, if the alphabetize is passed as a parameter, the remove method will remove and return the removed chemical element as well. Even so, if the index is not in the range of the ArrayList, the remove method throwsIndexOutOfBoundsException.

IndexOutOfBoundsException.

Time complexity of remove(Object obj) Method

The time complexity of remove(Object obj) method is O(Due north).

Reason:

When we pass an object to the remove method, information technology has to iterate through every element in the list until it finds out the 1 needed for removal. And plain, the remaining elements on the correct also need to be shifted. So, the overall fourth dimension complexity is O(N).

Exceptions for remove() in in Java

IndexOutOfBoundsException

The java.lang.IndexOutOfBoundsException exception is thrown when the index in remove(int index) method is out of range.

ConcurrentModificationException

When nosotros use this method while iterating over the elements of the ArrayList, it may result in ConcurrentModificationException because such modifications are not immune in the ArrayList while we are iterating over its elements simultaneously.

Solution to ConcurrentModificationException: Iterator interface

The alternative hither is to use the remove method of the Iterator interface.

Syntax:

Implementation:

                                                            import                                      java.util.ArrayList;                                                      import                                      java.util.Iterator;                                                      course                                                      Scaler                                                      {                                                                        public                                                      static                                                      void                                                      main                  (String[] args)                                                      {                                                                        // Creating an ArrayList                                                                          ArrayList<Cord> list =                                    new                                      ArrayList<>();                                                                        // Inserting elements in the ArrayList                                                                          list.add(                  "Apple"                  );                                                        list.add(                  "Avocado"                  );                                                        list.add(                  "Assistant"                  );                                                        list.add(                  "Cherry"                  );                                                        list.add(                  "Dragon Fruit"                  );                                                                        // Press elements                                                      System.out.println(listing);                                                                         // Removing Cherry from the list                                                      Iterator<Cord> itr = list.iterator();                                                                         // Iterating over the elements in order to                                                                                          // remove Cherry from the ArrayList                                                                                          while                                      (itr.hasNext()) {                                    String fruit = (Cord) itr.next();                                                      if                                      (fruit ==                                    "Cherry"                  ) itr.remove();                                    }                                                                         // Printing all the remaining elements                                                                                          // to check if cherry is removed                                                      System.out.println(listing);                     }                   }

Output

                                                            [Apple, Avocado, Banana, Cherry, Dragon Fruit]                  [Apple, Avocado, Banana, Dragon Fruit]

Example

Let us consider a simple example of an ArrayList that stores several characters. We demand to focus on what happens when nosotros remove an element from the ArrayList.

                                                            import                                      coffee.util.ArrayList;                                                      class                                                      SimpleExample                                                      {                                                                        public                                                      static                                                      void                                                      primary                  (Cord[] args)                                                      {                                                                        // Creating an ArrayList to shop characters                                                                          ArrayList<Character> list =                                    new                                      ArrayList<>();                                                                        // Inserting elements in the ArrayList                                                                          list.add(                  'A'                  );                                                        list.add(                  'B'                  );                                                        list.add(                  'C'                  );                                                        list.add together(                  'D'                  );                                                        list.add(                  'E'                  );                                                                        // Printing elements                                                                                          for                                      (                  int                                      i =                                    0                  ; i < listing.size(); i++) {                                                        System.out.println(                  "Alphabetize "                                      + i +                                    " : "                                      + list.go(i));                                    }                                                                         // Removing the element at alphabetize two                                                                          System.out.println(list.remove(                  two                  ) +                                    " has been removed from the list"                  );                                                                        // Printing all the remaining elements to cheque if C is actually removed                                                                                          for                                      (                  int                                      i =                                    0                  ; i < list.size(); i++) {                                                        System.out.println(                  "Index "                                      + i +                                    " : "                                      + listing.get(i));                                    }                     }                   }

Output:

                                                            Index                                    0                                      : A                                    Alphabetize                                    ane                                      : B                                    Alphabetize                                    2                                      : C                                    Index                                    iii                                      : D                                    Index                                    4                                      : Eastward                  C has been removed from the list                  Index                                    0                                      : A                                    Index                                    1                                      : B                                    Alphabetize                                    ii                                      : D                                    Index                                    iii                                      : E

Time Complication:

                                                            O(N), where                                    'North'                                      is the number of inputs

Notice that the removal of C besides led to the shifting of all its proceeding elements by one place to their left.

We'll be looking at a few more examples to understand the variants of the remove method.

remove() in Java

The remove method in Java has varied uses in the Collection interface. Although the operation is to only remove an object from a collection of objects, it has several variants where the parameters, too every bit the return values, differ.

In our give-and-take, nosotros'll be primarily focusing on the utilise of the remove method in ArrayList. As well, the apply of the remove method in Prepare, Maps and Queues has been demonstrated in the cease.

More than Examples

1. Remove the Specified Element From the ArrayList

                                                            import                                      java.util.ArrayList;                                                      grade                                                      Scaler                                                      {                                                                        public                                                      static                                                      void                                                      primary                  (String[] args)                                                      {                                                                        // Creating an ArrayList                                                                          ArrayList<String> listing =                                    new                                      ArrayList<>();                                                                        // Inserting elements in the ArrayList                                                                          list.add(                  "Apple"                  );                                                        list.add(                  "Avocado"                  );                                                        list.add(                  "Banana"                  );                                                        list.add(                  "Ruby-red"                  );                                                        list.add together(                  "Dragon Fruit"                  );                                                                        // Press elements                                                      System.out.println(listing);                                                                         // Removing Blood-red from the list                                                                                          boolean                                      outcome = listing.remove(                  "Cherry"                  );                                                        System.out.println(                  "Is blood-red removed from the list? "                                      + result);                                                                        // Printing all the remaining elements to cheque                                                                                                            // if scarlet is really removed                                                      System.out.println(list);                     }                   }

Output:

                                                            [Apple, Avocado, Banana, Cherry, Dragon Fruit]                                    Is carmine removed from the list?                                    truthful                                    [Apple tree, Avocado, Banana, Dragon Fruit]

Fourth dimension Complexity:

                                                            O(N), where                                    'N'                                      is the number of inputs

2. Remove the Element from the Specified Position

                                                            import                                      coffee.util.ArrayList;                                                      class                                                      Scaler                                                      {                                                                        public                                                      static                                                      void                                                      primary                  (String[] args)                                                      {                                                                        // Creating an ArrayList                                                                          ArrayList<String> listing =                                    new                                      ArrayList<>();                                                                        // Inserting elements in the ArrayList                                                                          list.add together(                  "Apple"                  );                                                        list.add(                  "Avocado"                  );                                                        list.add(                  "Banana"                  );                                                        list.add(                  "Blood-red"                  );                                                        listing.add(                  "Dragon Fruit"                  );                                                                        // Printing elements                                                                                          for                                      (                  int                                      i =                                    0                  ; i < list.size(); i++) {                                                        Organisation.out.println(                  "Alphabetize "                                      + i +                                    " : "                                      + list.get(i));                                    }                                                                         //Removing the element at index 3                                                                          Cord fruit = list.remove(                  iii                  );                                    //returns the removed element                                                                          Organization.out.println(fruit +                                    " has been removed"                  );                                                                        // Printing all the remaining elements to cheque                                                                                                            // if ruddy is actually removed                                                      System.out.println(listing);                     }                   }

Output:

                                                            Alphabetize                                    0                                      : Apple                                    Alphabetize                                    one                                      : Avocado                                    Alphabetize                                    2                                      : Banana                                    Alphabetize                                    3                                      : Cherry                                    Index                                    4                                      : Dragon Fruit                  Ruddy has been removed                   [Apple, Avocado, Assistant, Dragon Fruit]

Time Complication:

                                                            O(N), where                                    'N'                                      is the number of inputs

3. Remove the First Occurrence of the Element

If an chemical element appears more than in one case in the ArrayList, then information technology will remove information technology at the start location merely.

                                                            import                                      coffee.io.*;                                                      import                                      coffee.util.ArrayList;                                                      class                                                      Scaler                                                      {                                                                        public                                                      static                                                      void                                                      main                  (String[] args)                                                      {                                                                        // Creating an ArrayList                                                                          ArrayList<String> list =                                    new                                      ArrayList<>();                                                                        // Inserting elements in the ArrayList                                                                          list.add(                  "Apple"                  );                                                        list.add together(                  "Avocado"                  );                                                        list.add together(                  "Assistant"                  );                                                        list.add together(                  "Apple"                  );                                                        list.add together(                  "Ruddy"                  );                                                        listing.add(                  "Dragon Fruit"                  );                                                        list.add(                  "Apple tree"                  );                                                                        // Press elements                                                      Arrangement.out.println(listing);                                                                         // Removing Apple tree from the listing                                                                                          boolean                                      outcome = list.remove(                  "Apple tree"                  );                                                        System.out.println(                  "Is apple removed from the listing? "                                      + outcome);                                                                        // Press elements to check                                                                                                            // if apple is removed only from its get-go location                                                      System.out.println(list);                     }                   }

Output:

                                                            [Apple, Avocado, Banana, Apple tree, Cherry, Dragon Fruit, Apple tree]                                    Is apple removed from the list?                                    truthful                                    [Avocado, Banana, Apple, Blood-red, Dragon Fruit, Apple tree]

Other Uses of Remove() in Java

The remove() method is implemented in the other interfaces besides, including Ready, Queue, Maps, etc. Let us accept a quick wait at some of the examples related to each one of these interfaces where the remove() method is used. Since Set, Queue, Maps are interfaces, we'll need a form that implements these interfaces to create objects.

Queue

Queue is a data structure that follows the Offset In First Out (FIFO) order. It is like to a real queue where the person at the front end end of the queue will exist favored first. The Queue interface is already present in Java which is implemented by other classes. Here, the form LinkedList has been used to implement Queue interface.

                                                            import                                      java.util.LinkedList;                                                      import                                      java.util.Queue;                                                      class                                                      Scaler                                                      {                                                                        public                                                      static                                                      void                                                      main                  (String[] args)                                                      {                                                                        // Creating a Queue                                                                          Queue<Integer> queue =                                    new                                      LinkedList<>();                                                                        // Inserting elements in the queue                                                                          queue.add together(                  10                  );                                                        queue.add(                  20                  );                                                        queue.add(                  30                  );                                                        queue.add together(                  twoscore                  );                                                        queue.add(                  50                  );                                                                        // Printing elements                                                      Organization.out.println(queue);                                                                         // Removing 30 from the list                                                                                          boolean                                      outcome = queue.remove(                  30                  );                                                        System.out.println(                  "Is apple tree removed from the list? "                                      + outcome);                                                                        // Printing elements to bank check                                                                                                            // if 30 is removed only from its first location                                                      System.out.println(queue);                     }                   }

Output:

                                                            [                  10                  ,                                    20                  ,                                    30                  ,                                    xl                  ,                                    50                  ]                                    Is apple removed from the listing?                                    true                                                      [                  ten                  ,                                    20                  ,                                    40                  ,                                    l                  ]

Time Complexity: O(N) where N is the size of the Linked List.

Explanation:

LinkedList form in Queue has an array as its underlying data structure. So, the removal of any element doesn't require the shifting of other elements.
Yet, nosotros still accept to traverse the LinkedList to discover the element to be removed.

Ready

Set is a Collection interface in Java that contains a group of objects without maintaining their insertion order. Also, it doesn't allow the insertion of duplicate values.

For theReady interface, we'll be demonstrating with the help ofLinkedHashSet.

                                                            import                                      coffee.util.LinkedHashSet;                                                      import                                      java.util.Set;                                                      form                                                      Scaler                                                      {                                                                        public                                                      static                                                      void                                                      main                  (String[] args)                                                      {                                                                        // Creating a LinkedHashSet                                                                          Set<String> set up =                                    new                                      LinkedHashSet<>();                                                                        //Inserting elements in the fix                                                                          set.add together(                  "Remove"                  );                                                        set.add(                  "Method"                  );                                                        ready.add(                  "in"                  );                                                        set.add(                  "Fix"                  );                                                                        // Printing elements                                                      Organization.out.println(set);                                                                         // Removing "Method" from the list                                                                                          boolean                                      outcome = fix.remove(                  "Method"                  );                                                        Organization.out.println(                  "Is 'Method' removed from the set? "                                      + event);                                                                        // Printing elements                                                      System.out.println(set);                     }                   }

Output:

                                                            [Remove, Method, in, Prepare]                                    Is                                    'Method'                                      removed from the set?                                    true                                    [Remove, in, Set]

Time Complication: O(one)

Reason:

LinkedHashSet is the combination of HashSet as well as LinkedList. The remove method in LinkedHashSet works in O(1) fourth dimension complexity.
It is because LinkedHashSet maintains links between the nodes in addition to the hash table.
It is not necessary to traverse the whole list for removal, only the list neighbors demand to be updated.
Accessing a specific element is no more expensive than for the HashSet.

Map

Map is an interface that stores a group of key-value pairs as objects, where a primal can be used to fetch its mapped value. Nosotros'll be using HashMap to implement the Map interface.

                                                            import                                      java.util.HashMap;                                                      import                                      java.util.Map;                                                      public                                                      form                                                      Scaler                                                      {                                                                        public                                                      static                                                      void                                                      chief                  (String[] args)                                                      {                                                                        //Creating a HashMap                                                                          Map<Integer, Cord> map =                                    new                                      HashMap<>();                                                                        //Inserting elements                                                                          map.put(                  0                  ,                                    "Remove"                  );                                                        map.put(                  one                  ,                                    "Method"                  );                                                        map.put(                  2                  ,                                    "in"                  );                                                        map.put(                  3                  ,                                    "Map"                  );                                                                        //Printing elements                                                      System.out.println(map);                                                                         //Remove the element with key 1                                                                          String value = map.remove(                  one                  );                                                        System.out.println(value +                                    " has been removed"                  );                                                                        //Printing elements once again                                                      System.out.println(map);                     }                   }

Output:

                                                            {                  0                  =Remove,                                    i                  =Method,                                    2                  =in,                                    3                  =Map}                  Method has been removed                  {                  0                  =Remove,                                    ii                  =in,                                    3                  =Map}

Time Complexity: O(1)

Reason:

HashMap uses Hash Table as its data structure. The remove method in HashMap consumes O(i) time. The put method likewise has O(1) fourth dimension complexity. So, the overall time complexity will be O(1).

Conclusion

The remove method is present in the Java Collection framework. We can remove an chemical element from a collection of objects with the assist of remove() in coffee.
There are two means to pass a parameter to the remove method.
If we laissez passer an object, then the remove method returns true if the removal is successful, else it returns false. boolean remove (Object obj);
If an index is passed as a parameter, the remove method removes the chemical element at the specified index. Object remove(int alphabetize); If the alphabetize is out of range of the ArrayList, it will throw IndexOutOf BoundsException.
If at that place are multiple occurrences of the aforementioned element in the ArrayList, then the remove method will remove its starting time occurrence only.
The overall time complexity of both the variations of remove method in ArrayList volition be O(Due north), where N is the number of inputs.
Using ArrayList.remove() method while iteration may outcome in ConcurrentModificationException.
The remove method also finds its apply in the interfaces like Ready, Map, Queue, etc.