ArrayList<E>
Introduction
Certainly! At its core, an ArrayList in Java is a wrapper around an array that can resize itself dynamically as elements are added or removed. This is necessary because while arrays in Java have a fixed size once they're created, an ArrayList can grow or shrink as needed. Let us look at a basic conceptual overview of how an ArrayList manages its dynamic size using an Object array.
-
Initial Capacity: When an ArrayList is created, it starts with an initial capacity (which is 10 by default if you don't specify one). This capacity is the size of the underlying array.
-
Adding Elements: When you add elements to an ArrayList, it adds them to the underlying array. If the array is full (i.e., the number of elements equals the capacity of the array), the ArrayList needs to increase the capacity of the underlying array to accommodate more elements.
-
Resizing: To increase the array size, ArrayList creates a new array with a larger capacity. A common strategy is to increase the size by 50% of the original array's length. Then it copies the elements from the old array to the new one. This operation is costly in terms of time, so it's best to minimize how often resizing happens by setting a realistic initial capacity if you have an estimate of the number of elements you'll need.
-
Accessing Elements: Elements can be accessed via their index. Since the underlying structure is an array, this operation is very fast (constant time, O(1)).
-
Removing Elements: When elements are removed, the ArrayList may need to shift elements to fill up the space left by the removed element, which can be costly (linear time, O(n)) since it may involve copying elements to new positions.
To the left one can see a simplified code of how this could look like.
ArrayList<E>
Object[] Array
In Java, generics were introduced to provide tighter type checks at compile time and to support generic programming. However, because of the way Java implements generics using type erasure, generic types are erased and replaced by their bounds or Object if the type is unbounded during the compilation. This is where the use of Object[] comes into play in classes like ArrayList. Let us discuss why the usage of Object[] is the only way to make this work in Java with the knowledge we have.
-
Type Erasure: Java implements generics through a process called type erasure to maintain backward compatibility with older Java versions that did not include generics. When the code is compiled, all generic type information is erased, and all that is left is the raw type, which, in the case of collections, is typically Object. This means that at runtime, there's no T; there's just Object.
-
Array Store Type: In Java, arrays are covariant, meaning an Integer[] is a subtype of Object[], and you can assign an Integer[] to an Object[] reference. However, you cannot create a generic array like T[] because at runtime the actual type of T is not known due to type erasure. So ArrayList uses an Object[], which can hold any type of object, to store its elements internally.
-
Type Safety: Even though an ArrayList uses an Object[] internally to store its elements, from the perspective of the ArrayList API, it is type-safe. The generic type parameter T is used in the method signatures to enforce type safety at compile time. When you add an element to an ArrayList<T>, you can only add objects of type T. Similarly, when you retrieve an element, it is automatically cast to T.
Abstract Datatypes
Definition and Usage
An Abstract Data Type (ADT) in computer science is a mathematical model for data types, where a data type is defined by its behavior (semantics) from the point of view of a user, specifically in terms of possible values, possible operations on data of this type, and the behavior of these operations. This definition focuses on the what of the data type rather than the how.
In Java, ADTs are typically implemented using classes. These classes define a set of operations available to clients without exposing the underlying implementation details. Common examples of ADTs are the following.
-
List ADT: Represents a sequence of elements with operations to add, remove, and search for elements in the sequence. Java has List interface as a part of its Collections Framework which ArrayList, LinkedList, and others implement.
-
Stack ADT: Represents a collection of elements with two principal operations: push, which adds an element to the collection, and pop, which removes the most recently added element. Java has a Stack class that implements these operations.
-
Queue ADT: Represents a collection of elements with operations to add and to remove elements. Elements are removed in the order they were added. Queue is an interface in Java, and classes like LinkedList and PriorityQueue implement this interface.
-
Map ADT: Represents a collection of key-value pairs with operations to add, remove, and search for keys. In Java, Map is an interface implemented by classes like HashMap, TreeMap, and LinkedHashMap.
-
Set ADT: Represents a collection of unique elements with operations to add, remove, and check for membership. In Java, Set is an interface implemented by HashSet, TreeSet, and others.
-
Graph ADT: Represents a set of nodes and edges with operations to add and remove nodes or edges and to find paths between nodes. Java doesn't have a built-in Graph ADT, but it can be implemented using a combination of Maps and Sets, or by creating custom classes.
-
Tree ADT: Represents a hierarchical tree structure with a root value and subtrees of children with a parent node, represented as a set of linked nodes. In Java, a tree can be implemented using custom classes or by using TreeSet or TreeMap which internally use Red-Black tree data structure.
ADTs encapsulate the data and provide abstraction. This means that the implementation can change as long as the interface stays the same, ensuring that code relying on the ADT does not need to change. For instance, a List ADT could be implemented using an array or a linked list, but the user of the List wouldn't need to know which implementation is being used. The key idea of an ADT is that it provides a contract specified by the behavior of the operations provided and not by the details of how these operations are implemented. This allows for modular programming, improves maintainability, and promotes reusability.