List Interface with Implementation Classes

About List Interface

List is an interface that belongs to the utility package and can be imported to our program using the “import Java.util.List” statement. It helps to store linear and ordered data. Any inserted elements will be placed in order of their insertion inside the list. It also allows us to store the duplicate elements and null values to our data structure. List implements the “Collection” interface which also implements the “Iterable” interface.

Implementing Classes From Collections

ArrayList, LinkedList, Stack, Vector, AbstractList.

List Declaration is:

Where E is the type of elements our list will handle.

Points About List Interface

List interface provides four more ways to index or access the stored elements, like zero indexing (for array, LinkedList).

It provides two methods that we can use to remove and insert multiple elements at a certain point from the list.

List interface gives the special iterator, which is “ListIterator”, to perform insertion or updating of elements in List.

Methods provided by List Interface

boolean addAll( listobj ) : It inserts all the elements in the parameter to the end of the list.

boolean add() : Appends the element to the end of the list.

boolean equals(obj) : It compares the content of two lists.

E get(int index) : Returns the element at a particular index.

int lastIndexOf(obj) : Returns the last index of a repeating element “obj”.

E remove(int index) : It removes the element which is stored at a particular index.

set(int index, element) : It inserts the element to the specified index in the list.

int size() : The number of elements present in the list will be returned.

ArrayList

It uses dynamic arrays internally to store the elements. We can easily perform insert and delete operations from the methods given by the class ArrayList. It is a preferred data structure when we need to store and fetch the elements, as it will be fast. But in the case of element manipulation it is not preferred to use ArrayList, as it internally performs bit manipulation.

Points to remember

It extends the abstract list, which in turn implements the list interface.
ArrayList is non-synchronized, hence it is faster.
ArrayList is preferred over LinkedList when inserting and getting value from ArrayList is required.
It was introduced in version 1.5 (which was a generic Java collection).
Java creates the instance of ArrayList with 10 as its default capacity.

Load Factor

It is a value that decides when to increase the capacity of a collection. The default value of the load factor in every collection ArrayList, LinkedList, and HashMap is 0.75. It means that when our ArrayList is filled to 75% of capacity then its size will be automatically increased with the increasing factor.

Array Declaration

Where E is the type of data our list will contain.

Java Implementation With Method Description

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
import java.util.*;
import java.lang.*;

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

    //Creating Arralist with def capacity 10
    ArrayList < String > list = new ArrayList < String > ();

    // adding elements to list using add() method
    list.add("Avtar");
    list.add("Pindi");
    list.add("Sarpal");
    list.add("Assar");
    list.add("Assar");
    list.add("Baadi");

    System.out.println("\nArrayList: " + list);

    //finding lastIndexof "Assar"
    System.out.println("\nLast index of Assar:" + list.lastIndexOf("Assar"));

    //removing elements
    list.remove("Baadi");

    System.out.println("\nArrayList: " + list);

    //set item at particular index
    list.set(2, "Baadi");

    System.out.println("\nArrayList: " + list);

    // adding at particular index
    list.add(2, "Singh");

    System.out.println("\nArrayList: " + list + "\n\n");

    //Iterating over a list using Iterator
    //Create iterator object
    Iterator < String > itrList = list.iterator();
    System.out.println("Printing using Iterator");
    while (itrList.hasNext()) {
      System.out.print(itrList.next() + " ");
    }
  } //Main method ends
}

Code Snippet

So far we have discussed list and its implementation class ArrayList. Now we will discuss LinkedList, Stack and Vector classes with their Java implementation.

LinkedList

This class is the implementation of list and deque interfaces. It internally uses the doubly LinkedList to store the elements in LinkedList. Data is stored in a node and all the nodes are linked to each other using the address. All the data in LinkedList is stored in a non-contiguous location. It belongs to the “Java.util” package.

LinkedList Declaration

Structure of a LinkedList and Node

1
2
3
4
5
6
7
8
9
10
class LinkedList {
  Node head; // a pointer pointing to first Node 
  class Node { //node 
    int data;
    Node next;
    Node(int d) {
      data = d;
    } //constructor to create new Node
  }
}

Points to remember about LinkedList

LinkedList maintains the insertion order.

It is non-synchronized, hence it is fast.

Duplicates are allowed in LinkedList.

It can act as a list and queue.

LinkedList is preferred when deletion, updation or transformation is performed because it is easy to delete a node and insert a new node as it does not involve any bit manipulation.

LinkedList Methods

LinkedList() : Will create an empty LinkedList with head pointing to null.

boolean add(index, node) : Used to insert a new node at the specified index of LinkedList.

boolean addFirst(node) : Used to add a node to the start of LinkedList.

boolean addLast(node): Used to add a node to the end of LinkedList.

void clear() : Removes all the nodes present in a LinkedList.

Java Implementation for LinkedList

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
import java.util.*;
import java.lang.*;

import java.util.*;

public class Solution {

  public static void main(String args[]) {
    List < Integer > list = new LinkedList < Integer > ();

    list.add(100);
    list.add(200);
    list.add(300);

    System.out.println(
      "LinkedList:" + list);

    //to insert at 1st index
    list.add(1, 0);

    System.out.println("After adding at 1st Index LinkedList:" + list);

    //to remove element at index 1	
    list.remove(1);

    System.out.println(
      "After the Index Removal " + list);

    //finding the index of Node
    //if node doesn't exist -1 will be returned		
    System.out.println(
      "After addLast() method calls:" + list.indexOf(300));

  }
}

Code Output

Vector Class in Java

It is like an array as its elements can be accessed using an integer index. Its size can be increased and decreased automatically when we add or remove elements to a vector, so it works like a dynamic array. It was first introduced to the Java collection in Java 1.2.

Declaration for Vector:

E : Is type of reference.

Methods for Vector

Vector() : It creates the vector with a default capacity 10.

Vector(Collection c): It creates a vector with elements of c already inserted into the vector object.

add(item): It will add an element to a vector.

remove(int indexVal): This method removes the item at indexVal.

Java Implementation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import java.util.Vector;

class Main {
  public static void main(String[] args) {
    Vector < String > color = new Vector < > ();

    color.add("White");
    color.add("Red");

    color.add(2, "Green");
    System.out.println("Vector: " + color);

    Vector < String > rang = new Vector < > ();
    rang.add("Yellow");

    rang.addAll(color);
    System.out.println("New Vector: " + rang);
  }
}

Output

Stack Class in Java

Stack is a linear data structure like an array that is based on LIFO (last in, first out operations). Stack class provides various methods to perform create, read, update, and delete operations. It extends the vector class.

Stack Declaration:

Methods in Stack Class

push(int item): It inserts the item to the top of the stack.

pop(): It removes the item from top of the stack.

empty(): It returns true if the stack is empty, otherwise it returns false.

peek(): It returns the topmost element from the stack but it does not remove the element.

search(data): It will search the data from the vector and return its position.

Java Implementation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import java.util.Stack;
public class Solution {
  public static void main(String[] args) {

    //It will create the empty stack  
    Stack < String > stk = new Stack < > ();

    //check if the stack is empty
    System.out.println("Stack empty or not: " + stk.empty() + "\n\n");

    // push method to insert at top of stack  
    stk.push("Red");
    stk.push("White");
    stk.push("Green");
    stk.push("Black");
    //printing whole stack
    System.out.println("Stack: " + stk + "\n\n");

    System.out.println("Stack empty or not: " + stk.empty() + "\n\n");
  }
}

Output Snippet