List Interface

Welcome to the blog about List Interface. In this article, I am going to introduce a concept of List and its implementations such as Vector and Stack with the accent to the ArrayList and LinkedList. I hope you will enjoy the content and gain some new experience.

The Java List Interface represents a collection of elements. What is characteristic about List is that same element can occur more than once, also elements in a List have an insertion order and they can be iterated in that order.

Implementation

The Java.util.List is a child interface of Collection, therefore all methods from Collection can be used in List Interface as well.

List Interface is implemented by classes listed below:

Creating List Objects

A List is an interface, and the instances of List can be created in the following ways:

List list1 = new ArrayList();
List list2 = new LinkedList();
List list3 = new Vector(); 
List list4 = new Stack();

Operations on List

A List allows add, remove, get and set operations based on numerical positions of elements in List. A List provides the following methods for these operations:

Bellow, you can find a few more methods, for further information feel free to check the official website:

Example:

// Creating a list 
List<Integer> list1 = new ArrayList<Integer>(); 
list1.add(0, 5);  // adds 5 at 0 index 
list1.add(1, 6);  // adds 6 at 1 index
list1.add(2, 7);  // adds 7 at 2 index
System.out.println(list1);  // [5, 6, 7] 
  
// Creating a 2nd list
List<Integer> list2 = new ArrayList<Integer>(); 
list2.add(1); 
list2.add(2); 
list2.add(3); 
  
// Will add list list2 from 2 index 
list1.addAll(2, list2); 
System.out.println(list1); 
  
// Removes element from index 3 
list1.remove(3);      
System.out.println(list1); 
  
// Prints element at index 3 
System.out.println(list1.get(3)); 
  
// Replace 0th element with 5 
list1.set(0, 5);    
System.out.println(list1);

Result:

[5, 6, 7]
[5, 6, 1, 2, 3, 7]
[5, 6, 1, 3, 7]
3
[5, 6, 1, 3, 7]

ArrayList

The ArrayList class implements a List Interface and represents dynamic arrays that can grow as needed. All elements of an ArrayList are stored in a Java array, but unlike an array that has a fixed length, ArrayLists are created with an initial size. That means that if the size is exceeded the collection is automatically enlarged and if an element is removed from ArrayList the array may be shrunk.

Size enlargement is done by copying the old elements to the new array and using that new array instead of the old one. Since the size of an array doubles every time it needs more space, this can be controlled by using trimToSize() method. This method copies all the elements from the existing array to a new array with size of exactly same number as the elements in the existing array.

As ArrayList is generic that means that you work with a general type T, where T can be replaced by any type such as int, double, String, Object etc. The most important thing is that ArrayList and ArrayList are different. For ArrayList, you must specify the type of elements that will be stored. For example, if you want to store textual values in your ArrayList, this is the way of declaration:

ArrayList<String> text = new ArrayList<String>();

You can, also, see a declaration such as List<String> text = new ArrayList<String>();. This way, named Polymorphism, is usually used because the object named “text” is intended to be used as a List and it is recommended to declare it as List type.

LinkedList

A LinkedList is a linear data structure where elements are linked by using pointers. That means that the elements are not stored at contiguous memory locations. A LinkedList consists of nodes where each node contains a data field and a reference to the next node in the list.

In other words, the LinkedList is nothing but a series of elements, where each has 2 fields. In one is the value of the element (what would be in that place in the ordinary sequence), and in the second is a pointer to the next element of the string. The last element shows NULL.

The differences between ArrayList and LinkedList are:

The way of declaring LinkedList is similar to ArrayList. For example, if you want to store textual values in your ArrayList, the way of a declaration is:

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

Example - The “throws” function

public Object pop() throws UnderflowException {
        
   if(this.isempty()) {
      throw new UnderflowException();
   }
                
   DoublyLinkedList oldback = this.back;
   Object result = oldback.element;
   this.back = oldback.next;
                
   if(this.front == oldback) {
      this.front = null;
   }
                 
   oldback.remove();                
   return result;
}

public boolean isempty() {
          
   if(this.front == null || this.back == null) {
                  
      if(this.back != this.front) {
         throw new RuntimeException("Losa reprezentacija, front="+front+" back="+back);
      }                          
      return true;                          
      } else {
         return false;
      }
}

Example - The “insert” function

public void push(Object x) throws OverflowException {
           
      if (this.isempty()){
         this.front = this.back = new DLL(null, x, null);
      } else {
         DLL oldback = this.back;
         this.back = new DLL(null, x, oldback);
      }
}

public boolean isempty() {
         
   if(this.front == null || this.back == null) {
                
         if(this.back != this.front) {
            throw new RuntimeException("Losa reprezentacija, front="+front+" back="+back);
         }                          
         return true;
         } else {
           return false;
         }
}

If you liked this article, you might be interested in Lists, Sets, Maps, Queues and Deques. Feel free to browse.