Lists in Java — I

In Java, a List is a data structure that stores a collection of elements in a specific order. Each element in the List is identified by an index, which is a unique integer value that represents its position in the List. Lists provide a flexible and efficient way to store and manipulate data in Java.

A List in Java can potentially store several types of data varying from Integer & String to Unknown T types. This is made possible with the concept of Generics. A type safe list allows insertion of elements of that exact type, ensuring type safety and leading to less potential errors.

Characteristics of Lists

A List has the following characteristics which sets it apart from the rest of the data structures present out there:

• Order of Retrieval of Elements: Retrieval of elements depends on the type of ordering a data structure follows. For a List, it depends on its implementation whether it follows Last-in-First-out(LIFO) order or First-in-First-out(FIFO) order.
• Accessing of Elements: Accessing of elements in a list again depends on its implementation. Generally, the elements can be accessed from both the start and the end of the data structure.
• Implementation: This is the most important part of a data structure. It decides as to how you can access elements of a list and retrieve them. Some lists are customized in a manner such that they store the position of their previous element and the position of their successive element, enabling multiple access points throughout the list while some lists are customized in a way in which the current node stores the current element and the position of successive element. Though this might sound complex, it is an efficient way to create lists in the memory. Another way in which one may create a list is through the use of Arrays. The list, thereby created by that method, will be a linear data structure, and is less efficient in terms of memory.

Time Complexity based on the type of implementation of Lists.

• Array Based Implementation:

Accessing Time: O(1)

Retrieving Time: O(1)

Modification Time: O(1)

1. Accessing, retrieving and modifying an element of an array based implementation of a list is a constant time operation. Since arrays support indexing hence it becomes easier for one to perform these operations.

• Linked List and Doubly Linked List

Accessing Time: O(n)

Retrieving Time: O(n)

Modification Time: O(n)

1. In a linked list, the index of an element is not known, for which one has to perform a linear search throughout the unsorted linkedlist to get its elements, making it consume linear time.
2. In case of doubly linked list, bidirectional traversals are allowed but that doesnt change the reality of the fact that the time complexity for accessing a single element still remains the same.

• Skip List

Accessing Time: O(log n)

Retrieving Time: O(log n)

Modification Time: O(log n)

1. Skip list are an example of hybrid data structures that makes use of multiple levels of linked lists, thereby reducing the time taken to find an element. Indeed they are efficient that Linked or Doubly Linked Lists but they consume more space on the memory hence becoming memory inefficient.

Trading time against memory space

It is a usual behaviour of programmers to compare data structures based on its efficiency in time and memory space. Some implementations of list make it easier for traversing in less time while some implementations are focused on improving its memory space efficiency.

However, a list with both an efficient time and space doesnt exist but data structures like Dynamic array which can grow dynamically once it has reached its maximum size provides easier access and modification of elements in a short time and provide efficient memory space conservation for large lists.

Update in place & In place mutation

Java provides an option to modify a value of a variable by updating it without creating a new copy of it. This is called update in place. In place mutation thereby refers to the modification of a list element without creating a new copy of it in the memory. Some other classes that follow In-place mutation are StringBuffer and StringBuilder.

For example, if there exists a list of 100,000 elements and we want to modify its elements in a linear fashion, creating a new list in the memory with these many elements would not be feasible for the modification of a single element. Hence with this powerful feature of mutating just the particular element of a list, you can make a memory efficient program.

Hence in-place mutation is a more specific term for modifying values of a data structures without creating its copy while update-in place is the logic behind it.

Implementing a List using Arrays.

Its important to understand how List data structure works and in order to master its working, we need to create it using the fundamental data structures.

When implementing a list, we need to initialize an array with a specific initial size. This is really crucial as the initial size decides if the list is efficient or not. Having a large initial size will result in wastage of memory and a small initial size will result in increasing the size of the array quite often dynamically.

However, before implementing a dynamic list, i.e. a list which can dynamically increase its size on the addition of elements more than its size, we will learn how to implement a static list which cannot increase in size.

Before getting started with the code, we need to sketch out the class design for implementing a static list and decide the methods and their accessibility.

Getting Started

Before creating an actual List class, we need to have a blueprint of what our List class must have. Java thankfully has interfaces for the same to be later implemented to our class. Let’s sketch out an interface here.

public interface List<T> {
    boolean add(T element);
    boolean addAll(T[] element);
    T get(int index);
    boolean remove(int index);
    int size();
    boolean isEmpty();
    boolean isFull();
}

Here List<T> signifies a generic interface of type T. Using a generic interface makes it possible that your data structure is type safe and contains elements of the same type avoid confusion and promote type safety. There are several methods that serve the basic functionality of any list data structure.

Great, now that we have an idea of what methods our List class should have, we can start implementing it using arrays. To begin with, we need to create an array with a fixed size, which will act as the List. We can then implement the methods specified in the interface.

public class CustomList<T> implements List<T>{
    private int size, index;
    private T[] array;

    public CustomList(int size) {
        this.size = size;
        this.index = -1;
        this.array = (T[]) new Object[this.size];
    }

    public CustomList() {
        this.size = 5;
        this.array = (T[]) new Object[this.size];
    }

    @Override
    public boolean add(T element) {
        if(this.isFull())
            return false;

        this.array[++this.index] = element;
        return true;
    }

    @Override
    public boolean addAll(T[] element) {
        if(element.length + this.index + 1 > this.size)
            return false;

        for(T t : element)
            this.array[++this.index] = t;

        return true;
    }

    @Override
    public T get(int index) {
        if(index > this.size-1)
            return null;

        return this.array[index];
    }

    @Override
    public T remove(int index) {
        if(index > this.size-1 || index < 0)
            return null;

        T removed = this.array[index];
        for(int i = this.index; i<this.size-1; i++) {
            this.array[i] = this.array[i+1];
        }
        this.index--;
        return removed;
    }

    @Override
    public int size() {
        return this.size;
    }

    @Override
    public boolean isEmpty() {
        return this.index == -1;
    }

    @Override
    public boolean isFull() {
        return this.index == this.size-1;
    }
}

These methods, with their name prominently stating their purposes, are the most fundamentally used methods in a list. However the two methods isFull and isEmpty are used very frequently in order to check if the list has reached its maximum limit as specified by the user or the default capacity, i.e. 5 in this case and if the list has no elements in it at all.

One thing about this list is the remove method. It is notable that we are using a loop for some reason. But why? This remove method removes the element from the list at a specified index and returns the deleted element. Now when you remove the element, you need to free up its space and shift the rest of the elements present on its right to its left. Hence you perform in place mutation and thereby free up space. While removing the element from the list, we need to keep in mind that the variable index that denotes the current index where the previous element was added to be reinitialized according to the size of the array. Hence we decrease it by 1.

Now let’s initialize our CustomList<T> class and perform the operations defined by it. In order to do that, we need to declare the list in this way with its initial size 10.

CustomList<Integer> list = new CustomList<>(10);

You might notice that the constructor of CustomList<T> class has an empty set of <>. This feature was introduced in Java 7 and is known as diamond operator. With this, the type of CustomList will be inferred by the first half of declaration. This was done to reduce redundancy of code.

Now that we have a CustomList created, we are going to store the squares of first 10 whole numbers. For that, we make use of a for loop which would invoke the add(T element) method of our list and store the squares in it.

for(int i=0; i<10; i++)
 list.add(i*i);

Now that we had stored all the elements in the list, its time to check what is in there. In order to print all the elements, we might consider iterating it the same way we did above in order to store the elements in the array.

System.out.println("Retrieving elements from the CustomList");
for(int i=0; i<10; i++)
   System.out.print(list.get(i) + ", ");

The following code prints this.

Retrieving elements from the CustomList
0, 1, 4, 9, 16, 25, 36, 49, 64, 81,

Now that we have learnt how to implement a static CustomList which has a fixed size, we now will move to create a dynamic CustomList which can increase its size on the addition of more elements in it.

Dynamically increasing List

We have learnt on how to implement a static list, now let’s modify the same class to make it possible to increase its size. In order to increase the size of our List, we would need to check for constraints that say to add elements even when the List is full. This can be done by creating an auxiliary array of size more than the last array size and copy all the elements from the previous array into it.

An easier way to wrap it around in a modular way should be to make sure that the current size of the array plus 1 is less than the size mentioned by the user at the time of initialization of array. This can be done by the means of a method known as ensureSize(int futureSize). This method would check if futureSize is greater than the currentSize and would reinitialize the currentSize by a particular value, ofcourse greater than its previous value, so as to accomodate more elements in the list. In order to achieve this, we will declare this in the blueprint of our List<T> interface first.

Now, our List<T> interface looks somewhat like this.

public interface List<T> {
    boolean add(T element);
    boolean addAll(T[] element);
    T get(int index);
    T remove(int index);
    int size();
    boolean isEmpty();
    boolean isFull();
  // New method to increase list size dynamically.
    boolean ensureSize(int futureSize);
}

Let’s now modify our CustomList<T> class. In there, we just need to replace the conditions that check if the list is completely filled or not with this newly created method ensureSize.

Hence we alter the add(T element) method to somewhat like :

@Override
public boolean add(T element) {
    ensureSize(this.size+1);
    this.array[++this.index] = element;
    return true;
}

But wait, we also need to implement the method ensureSize(int) in order to see this code functioning all good.

@Override
public boolean ensureSize(int futureSize) {
   if(futureSize > this.size) {
     futureSize = this.size + 10;
      this.size = futureSize;
      this.array = Arrays.copyOf(this.array, futureSize);
      return true;
   }
  return false;
}

Using the Arrays.copyOf(T[ ] originalArray, int newSize) creates a new array of the size newSize and copies all the elements of the originalArray into it. In order to see it working, you might store more than 10 elements in the list and try printing the same. You’ll find that the size of list has actually increased.

That’s it. We have successfully implemented a Dynamic CustomList in Java using arrays. In the upcoming article, we will learn how to go about creating our own LinkedList<T> class using the concept of arrays. That’s it for this article guys, do share it with your friends and be sure to reach out to me in case you want me to add new stuffs to the articles.

Thanks and Follow for more.