Java array list remove time complexity
Java:
We know that java is one of the programming languages. The main feature of java which is not in C or object oriented programming language is platform independence.
Not only the platform independence there are many other features in java such as secure, highly interpreted, robust, portable etc. We have a JVM (Java Virtual Machine) , JRE ( Java Runtime Environment ) , JDK ( Java Development Kit ). It is used to convert .class file to .exe file.
Array List:
The elements are stored in a dynamic array using the Java ArrayList class. Similar to an array, but with no size restrictions. At any time, we can add or remove components.
As a result, it is significantly more adaptable than a conventional array. The java.util package contains it. It is comparable to the C++ Vector. Java's ArrayList allows for the addition of duplicate elements.
Duplicate elements are possible in Java's Array List class. The Java Array List class preserves the order of insertion. Java's Array List class lacks synchronization. Because the array operates on an index basis, Java Array List permits random access.
Because there needs to be a lot of shifting done if any element is removed from the array list, manipulation of an array list takes a little bit longer than it does with a LinkedList in Java.
The primitive types, such as int, float, char, etc., cannot be organized into an array list. In such circumstances, the necessary wrapper class must be used.
Syntax to define array list in java:
We need to follow a particular syntax to define a particular variable, key word or method in java. The syntax to define array list in java is as shown below:
ArrayList < data type > variable_name = new ArrayList < data type > ( );
Now let us see a small program using array list in java using the following code as shown below:
Example:
import java . io . *;
import java.util . *;
class Demo
{
public static void main ( String args [ ] )
{
ArrayList < String > al = new ArrayList < String > ( );
al . add ( “ Mango “ );
al . add ( “ Apple “ );
al . add ( “ Guava “ );
al . add ( “ Grapes “ );
al . add ( “ Apricot “ );
System . out . println ( “ The array list elements are : “ );
for( String str : al )
{
System . out .println ( str );
} // for each loop
} // main method
} // Demo
Output:
Mango
Apple
Guava
Grapes
Apricot
Removing elements in array list:
The array list's size can be changed, like an array. The Array List class extends the List interface and is included in the Java.util package. Utilizing the Array List's built-in functions add( ) and remove makes adding and removing elements from the list relatively simple ( ).
We can remove an array element in two ways using the default method called remove ( ). They are:
- Remove using value
- Remove using index
1. Time complexity in remove by value:
It is comparable to increasing value at a specific index. We must iterate through each element to reach the desired index before removing the value in order to remove an element by value from an ArrayList or LinkedList. The complexity of this operation is O(N).
The distinction is that in LinkedList, removing an element only requires changing pointers, which has O(1) complexity, whereas in ArrayList, we must shift all entries after the removed value's index to close the gap.
Even though shifting and modifying pointers have the same total complexity, O(N), we prefer LinkedList since it requires more delete by value operations.
Now let us see an example to remove an element in an array using the value by the following code as shown below:
Example:
import java . io . *;
import java.util . *;
class Demo
{
public static void main ( String args [ ] )
{
ArrayList < String > al = new ArrayList < String > ( );
al . add ( “ Mango “ );
al . add ( “ Apple “ );
al . add ( “ Guava “ );
al . add ( “ Grapes “ );
al . add ( “ Apricot “ );
System . out . println ( “ The array list elements before removing are : “ );
for( String s : al )
{
System . out .println ( s );
} // for each loop
System . out . println ( “ The array list elements after removing are : “ );
al . remove ( “Guava “ );
al . remove ( “Apricot “ );
} // main method
} // Demo
Output:
The array list elements before removing are:
Mango
Apple
Guava
Grapes
Apricot
The array list elements after removing are:
Mango
Apple
2 .Time complexity in remove by index:
Array List is a definite winner when retrieving an element by index. Due to the array's random access property, Array List can provide any element in O(1) complexity. You don't need to iterate through the entire array to get any index directly.
The sequential access attribute of LinkedList exists. Getting a value by index from a LinkedList requires iterating through each member in order to reach a specific index, hence the time complexity is O( N ) .
Now let us see an example to remove an element in an array using the index by the following code as shown below:
Example:
import java . io . *;
import java.util . *;
class Demo
{
public static void main ( String args [ ] )
{
ArrayList < String > al = new ArrayList < String > ( );
al . add ( “ Mango “ );
al . add ( “ Apple “ );
al . add ( “ Guava “ );
al . add ( “ Grapes “ );
al . add ( “ Apricot “ );
System . out . println ( “ The array list elements before removing are : “ );
for( String s : al )
{
System . out .println ( s );
} // for each loop
System . out . println ( “ The array list elements after removing are : “ );
al . remove ( “ 1 “ );
al . remove ( “ 3 “ );
} // main method
} // Demo
Output:
The array list elements before removing are :
Mango
Apple
Guava
Grapes
Apricot
The array list elements after removing are :
Mango
Guava
Apricot
3. Semantic error:
Semantic errors are errors that happen when the compiler is unable to comprehend the written code. Despite being syntactically correct, a semantic error will be produced if the compiler cannot understand the code.
It is analogous to using the incorrect word in the incorrect context when speaking English. A semantic mistake will result, for instance, from adding a string to an integer.
Semantic mistakes are distinct from syntax errors since the former indicate that a program's structure is flawed without taking into account its meaning. Semantic mistakes, on the other hand, represent a program's improper implementation when the program's intent is taken into account.
Use of uninitialized variables and type compatibility and also array index out of bounds are the two semantic mistakes that occur more frequently.
Now let us see an example of semantic error in C language using the following code as shown below:
Example 5:
# include < stdio . h >
# include < conio . h >
void main ( void )
{
int a , b , c;
a * b = c;
} // main method
Output 5:
error : lvalue required as left operand of assignment.
Here in this example we can see that we are assigning the left side operant to the right side. So it becomes a semantic error in this program or example.
Now let us see another example of semantic error in C language using the following code as shown below:
Example 6:
# include < stdio . h >
# include < conio . h >
void main ( void )
{
int i;
int a [ 5 ] = { 2, 4, 6, 8, 10 };
for ( i=0 ; i<=5 ; i++ )
{
printf ( “ % d \ n “, a [ i ] );
} // for loop
} // main method
Output 6:
2
4
6
8
10
863264
Here in this example we can see that the array index is a [ 0 ] to a [ 4 ] but it is counting the array elements from a [ 0 ] to a[ 5 ] which is an index out of bound and hence it raises semantic error in this example.
4. Syntax error:
When a programmer types incorrectly or commits typographical errors, they commit syntax errors. In other words, a programmer makes a syntax error when they deviate from the set of guidelines established for the C language's syntax.
Because the compiler always detects syntax problems, they are sometimes sometimes referred to as compilation errors. In most cases, programmers can quickly spot and fix these mistakes.
In the C language, the following syntactic mistakes are the most typical:
- without a semicolon (;)
- Absence of a parenthesis ()
- Assigning the value to a variable without declaring the variable.
Now let us see an example of syntax error in C language using the following code as shown below:
Example 7:
# include < stdio . h >
# include < conio . h >
void main ( void )
{
var = 15;
printf ( “ % d “ , var );
} // main method
Output 7:
error: ‘ var ‘ is undeclared
Now let us see another example of syntax error in C language using the following code as shown below:
Example 8:
# include < stdio . h >
# include < conio . h >
void main ( void )
{
int i;
for ( i=0 ; i <=5 ; )
{
printf ( “ Hello world “ );
} // for
} // main method
Output 8:
error : expected expression before ‘ ) ‘ token
Here in this example we can see that we have not followed a particular syntax in for loop and therefore it returns a syntax error.
5. Linker error:
The object files produced by the compiler are combined into a single executable file by a program called a linker. When the executable file of the code cannot be generated even though the code is correctly built, linker faults are present.
When an additional object file is unable to link with the primary object file, this error is produced. A linked error can occur if we import the wrong header file, have an erroneous function declaration, etc.
Now let us see an example of linker error in C language using the following code as shown below:
Example 9:
# include < stdio . h >
# include < conio . h >
void Main ( void )
{
int var = 20;
printf ( “ % d “ , var );
} // main method
Output 9:
error : undefined reference to ‘ main ‘
In this example there is a reference which is not defined in a correct way. We have defined ‘ Main ‘ in the ‘ main ‘ section . Hence it returns a linker error.