Guide to Programming & Automation by Vinod: Java collections: List

1) List is an ordered collection and can contain duplicate elements.

2) You can access any element from it’s index.

3) List is more like array with dynamic length.

List interface operations:
1) Positional access:
Manipulates elements based on their numerical position in the list.

This includes methods such as get, set, add, addAll, and remove.

2) Search:
Searches for a specified object in the list and returns its index.
Search methods include indexOf and lastIndexOf.

3) Iteration:
The Iterator allows you to traverse the list in forward direction.
The three methods that ListIterator inherits from Iterator which are hasNext, next, and remove

4) Range-view:
The range-view operation like subList(int fromIndex, int toIndex), returns a List view whose indices range from fromIndex, inclusive, to toIndex.

List Algorithms:

sort — sorts a List.

shuffle — randomly permutes the elements in a List.
reverse — reverses the order of the elements in a List.
rotate — rotates all the elements in a List by a specified distance.
swap — swaps the elements at specified positions in a List.
replaceAll — replaces all occurrences of one specified value with another.
fill — overwrites every element in a List with the specified value.
copy — copies the source List into the destination List.
binarySearch — searches for an element in an ordered List using the binary search algorithm.
indexOfSubList — returns the index of the first sublist of one List that is equal to another.
lastIndexOfSubList — returns the index of the last sublist of one List that is equal to another.

Lists are further classified into the following:

ArrayList

LinkedList

Vectors

Let’s go into detail on each one of them:

1) ArrayList:

Java ArrayList class uses a dynamic array for storing the elements.
It maintains insertion order.
ArrayList class can contain duplicate elements.
It takes NULL, TRUE, FALSE as elements of the list.
ArrayList class is non synchronized.
Accessing element is faster than LinkedList because array works on the index basis.
Manipulation of arraylist is slow because a lot of shifting needs to be occurred if any element is removed from the array list.
It is not synchronized that means it is not Thread safe. We can create a synchronised ArrayList using Collections.synchronizedList() method.

Hierarchy of ArrayList class:

As shown in above diagram, Java ArrayList class extends AbstractList class which implements List interface. The List interface extends Collection and Iterable interfaces in hierarchical order.

Declaration:

ArrayList<String> list=new ArrayList<String>(); //creating new generic arraylist

Methods of arraylist:

ArrayList Examples

1) Add element and traverse through ArrayList

import java.util.*;

class Arraylist{  
 public static void main(String args[]){  

  ArrayList<String> list=new ArrayList<String>();   //Creating arraylist  

  list.add("Pune");//Adding object in arraylist  
  list.add("Mumbai");  
  list.add("Nagpur");  
  list.add("Kolhapur");

  //Remove
  list.remove(2);

  //To reset value 
  list.set(2, "Bangalore");

  //To get the Index of an Item
  System.out.println(list.indexOf("Pune")); 

  ArrayList<String> list_1=new ArrayList<String>();   //Creating arraylist 

  list_1.add("Chennai");      //Adding object in arraylist  
  list_1.add("Jaipur");  

  //Example of addAll()
  list.addAll(list_1);

  //Example of removeAll()
  list.removeAll(list_1);                                               

  //Traversing list through Iterator  
  Iterator<String> itr=list.iterator();  

  while(itr.hasNext()){  
   System.out.println(itr.next());  
  }  
  
  //Traversing through for-each Iterator
  for(String obj:list)  
     System.out.println(obj);  
  }  
}

2) User-defined class objects in Java ArrayList

public class Student {
 int rollno;
 String name;
 int age;

 Student(int rollno, String name, int age) {
  this.rollno = rollno;
  this.name = name;
  this.age = age;
 }
}

import java.util.*;
public class CollectionExample {
 public static void main(String args[]) {

  // Creating user-defined class objects
  Student s1 = new Student(401, "Rohan", 23);
  Student s2 = new Student(402, "Gaurav", 21);
  Student s3 = new Student(403, "Ashish", 25);

  // creating arraylist
  ArrayList<Student> list = new ArrayList<Student>();
  list.add(s1);// adding Student class object
  list.add(s2);
  list.add(s3);

  // Getting Iterator
  Iterator itr = list.iterator();

  // traversing elements of ArrayList object
  while (itr.hasNext()) {
   Student st = (Student) itr.next();
   System.out.println(st.rollno + " " + st.name + " " + st.age);
  }
 }
}

Question. How does Arraylist in java is internally implemented?
ArrayList can be created in two ways-
List<String> myList=new ArrayList<String>();
In this way, default constructor is invoked and will internally create an array of Object with default size, which is 10.

List<String> myList=new ArrayList<String>(30);

In this way, constructor with an integer argument is invoked and will internally create an array of Object with the size, specified in the constructor argument, which happens to be 30 in this case.

Now, As we all know that unlike normal arrays, the size of the ArrayList grows dynamically. But how its size grows internally?

Inside .add() method there is a size check. So,before adding element into the array it will check what is the current size of filled elements and what is the maximum size of the array. If size of filled elements is greater than maximum size of the array then size of the array must be increased. So what happens internally is a new Array is created with size 1.5*currentSize (increase by 50%) and the data from old Array is copied into this new Array.

2) Linked List:

Java ArrayList class uses a dynamic array for storing the elements.
It maintains insertion order.
ArrayList class can contain duplicate elements.
It takes NULL, TRUE, FALSE as elements of the list.
ArrayList class is non synchronized.
Accessing element is faster than LinkedList because array works on the index basis.
Random access is costlier in linkedlist as you need to go through all the Elements in the list until you reach your destination.
It is not synchronized that means it is not Thread safe. We can create a synchronised LinkedList using Collections.synchronizedList() method.

LinkedList by nature does not have "capacity" and it does not work with fixed sized arrays. LinkedList, simply grows/shrinks since there is no underlying data structure.

Hierarchy of LinkedList class:

As shown in above diagram, Java LinkedList class extends AbstractSequentialList class and implements List and Deque interfaces.

Singly Linked List:
In a singly Linked list each node in this list stores the data of the node and a pointer or reference to the next node in the list. Refer to the below image to get a better understanding of single Linked list.

Question. How does linkedList in java is internally implemented?
LinkedList by nature does not have "capacity". LinkedList does not allocate memory to the items before the items are added to the list. It simply grows/shrinks since there is no underlying data structure.

Declaration:

LinkedList<String> ll=new LinkedList<String>();

Methods of Linked list:

LinkedList Examples :

import java.util.*;

public class LinkedListDemo {

 public static void main(String args[]) {

  // create a linked list
  LinkedList<String> ll = new LinkedList<String>();

  // add elements to the linked list
  ll.add("F");
  ll.add("B");
  ll.add("D");
  ll.add("E");
  ll.add("C");
  ll.addLast("Z");
  ll.addFirst("A");
  ll.add(1, "A2");
  System.out.println("Original contents of ll: " + ll);

  // remove elements from the linked list
  ll.remove("F");
  ll.remove(2);
  System.out.println("Contents of ll after deletion: " + ll);

  // remove first and last elements
  ll.removeFirst();
  ll.removeLast();
  System.out.println("ll after deleting first and last: " + ll);

  // get and set a value
  Object val = ll.get(2);
  ll.set(2, (String) val + " Changed");
  System.out.println("ll after change: " + ll);
 }
}

3) Vector:

Java Vector is legacy class uses a dynamic array for storing the elements.
It inherits AbstractList class and implements List interface.
Java Vector class can contain duplicate elements.
Java Vector class maintains insertion order.
Java Vector class is synchronized.

Hierarchy of vector class:

Syntax:

Vector<String> vct = new Vector<String>();

Methods of Vector:

Vector Example:

import java.util.Iterator;
import java.util.Vector;

public class BasicVectorOperations {

 public static void main(String a[]) {
  
  Vector<String> vct = new Vector<String>();

  // adding elements to the end
  vct.add("First");
  vct.add("Second");
  vct.add("Third");

  // adding element at specified index
  vct.add(2, "Random");

  // getting elements by index
  System.out.println("Element at index 3 is: " + vct.get(3));

  // getting first element
  System.out.println("The first element of this vector is: " + vct.firstElement());

  // getting last element
  System.out.println("The last element of this vector is: " + vct.lastElement());

  // how to check vector is empty or not
  System.out.println("Is this vector empty? " + vct.isEmpty());

  // Print elements
  Iterator<String> itr = vct.iterator();

  while (itr.hasNext()) {
   System.out.println(itr.next());
  }
 }
}

Difference: Arraylist vs LinkedList

Difference: Arraylist vs LinkedList vs Vector

<-- Previous || Next -->

Guide to Programming & Automation by Vinod

Pages

Java collections: List

1 comment: