Array, ArrayList,LinkedList in Java.
Array:
An array is a fixed-size data structure that stores elements of the same type in contiguous memory locations. Elements are accessed using indices, which start from 0.
We can use both primitive types and wrapper classes in Java arrays. However, there are some differences between the two.
-Primitive types are stored directly in the array. This means that they are stored more efficiently and are faster to access.
- Wrapper classes are objects that wrap primitive types. This means that they are stored on the heap and have a reference pointing to them.
- They are slower to access than primitive types, but they offer more features, such as the ability to be null and to be used with the Collections framework.
Here is an example of an array that uses both primitive types and wrapper classes:
int[] marks = new int[5]; //primitive
Integer[] scores = new Integer[5]; // wrapperAlso we can directly define it with values.
String[] myArray = {"Value1", "Value2"};Major Characteristics:
Fixed size: Once an array is created, its size remains constant.
Direct access: Elements are accessed by their index.
Memory-efficient: Arrays store elements in a contiguous block of memory.
Homogeneous elements: All elements must be of the same type.
When to Use:
When the size of the collection is known and won’t change.
For simple data structures where direct access by index is essential.
When memory efficiency is important.
Detailed summary
· Data Type: Arrays are a primitive data type in Java. This means that they are not objects. However, you can use them with generics and other features of the Java language.
· Wrapper Class: There is no direct wrapper class for arrays of primitive types. However, you can use the Object wrapper class to store an array.
· Mandatory to Define Size When Initiated?: Yes, the size must be defined during initialization. You cannot create an array without specifying its size.
· Fixed Size: Yes, arrays have a fixed size once created. The size cannot be changed.
· Default Size: Not applicable (size must be specified during initialization).
· Resizable: Arrays are not resizable; their size remains constant after creation.
· Duplicate Values: Yes, arrays can store duplicate values.
· Null Values: Yes, arrays can store null values.
· Add Values after initialization: No, you cannot add values to an array after it has been initialized. However, you can create a new array with the additional values and then copy the contents of the old array to the new array.
· Remove Values: Yes, you can remove values from an array. However, you cannot remove elements from an array in place. You need to create a new array with the remaining elements and then copy the contents of the old array to the new array.
· Replace values: Yes, you can replace values in an array. You can do this by accessing the element at the desired index and assigning a new value to it.
· Maintain the Order: Yes, arrays maintain the order of elements based on their indices.
· Storing Value: Contiguous memory location. The values are stored sequentially in memory, making it easy to access them using their index.
· Sorting: Possible; you can sort arrays of primitive data types using algorithms like Arrays.sort(). Sorting is not inherent to arrays but can be achieved through programming.
· Direct Access: Elements in an array can be directly accessed using their index, which provides constant-time (O(1)) access.
· Index Range: The valid index range for an array with ’n’ elements is from 0 to n-1.
· Memory Overhead: Arrays have lower memory overhead compared to certain dynamic data structures like ArrayList, which may have extra storage for managing size.
· Multi-Dimensional Arrays: Java supports multi-dimensional arrays.
· Arrays are not thread-safe: This means that multiple threads cannot access an array at the same time without causing problems. If you need to access an array from multiple threads, you need to use a thread-safe data structure like Vector or CopyOnWriteArrayList.
A sample code of Array-
package array.example;
import java.util.Arrays;
import java.util.Comparator;
/* A good video tutorial
https://www.youtube.com/watch?v=NbYgm0r7u6o&ab_channel=CodingwithJohn
*/
public class ArrayMain {
public static void main(String[] args) {
// We must define the Type and size while initiating.
String[] names = new String[3];
names[0] = "Alice";
names[1] = "Bob";
names[2] = "Charlie";
// To print all the elements you have to use a loop since this will print the Object. Ljava.lang.String;@15aeb7ab
System.out.println("names object will be printed = "+names);
// Using an enhanced for-each loop
for (String name : names) {
System.out.println(name);
}
// We can directly add values so element's size will be it's size.
String[] titles={"Designer","Manager","Director"};
// Get size of the Array
System.out.println("Size of the array is= "+titles.length);
// replace element based on index.
titles[0] = "Developer";
// Get element using index of an Array
System.out.println("First element of Array= "+titles[0]);
// Ascending order (natural order)
Arrays.sort(names);
System.out.println("Ascending order:");
for (String name : names) {
System.out.println(name);
}
// Descending order using a custom comparator
Arrays.sort(names, Comparator.reverseOrder());
System.out.println("Descending order:");
for (String name : names) {
System.out.println(name);
}
}
}ArrayList:
- Explanation: ArrayList is a dynamic-size implementation of an array. It resizes automatically as elements are added or removed, providing a more flexible interface than a regular array.
- Major Characteristics:
- Dynamic size: It can grow or shrink based on the number of elements.
- Random access: Elements are accessed using indices like an array.
- Resizable array: Internally backed by an array that resizes as needed.
- Homogeneous elements: Stores elements of the same type.
- ArrayLists are not thread-safe. This means that multiple threads cannot access an ArrayList at the same time without causing problems.
- When to Use:
- When the collection size may change over time.
- For scenarios where random access by index is required.
- For simplicity when handling a list of elements without worrying about memory management.
- When the trade-off of occasional resizing is acceptable.
Detailed summary
· Data Type: ArrayList can store elements of any type, including primitive types and wrapper classes. However, it is more efficient to store wrapper classes in an ArrayList, as the primitive types are wrapped in objects when they are added to the ArrayList.
· Get value using index: Yes, you can get the value at a specific index in an ArrayList using the get() method. The get() method takes an index as its argument and returns the element at that index.
· Mandatory to Define Size When Initiated?: No, you do not need to define the size of an ArrayList when you create it. The ArrayList will automatically grow as needed.
· Fixed Size: No, ArrayLists are not fixed size. They can grow or shrink as needed.
· Default Capacity: The default capacity of an ArrayList is 10 elements. This means that when you create an ArrayList with no elements, it will initially allocate space for 10 elements.
· Add Values after initialization: Yes, you can add values to an ArrayList after it has been initialized. You can use the add() method to add a value to the end of the ArrayList.
· Duplicate Values: Yes, ArrayLists can store duplicate values.
· Null Values: Yes, ArrayLists can store null values.
· Remove Values: Yes, you can remove values from an ArrayList. You can use the remove() method to remove a value at a specific index.
· Replace values: Yes, you can replace values in an ArrayList. You can use the set() method to replace the value at a specific index.
· Maintain the Order: Yes, ArrayLists maintain the order of elements as they are added.
· Storing Value In Memory As: ArrayList stores values as objects. This is because the elements of an ArrayList are references to objects, not the objects themselves.
· Sorting: You can sort the elements of an ArrayList using the Collections.sort() method.
· Direct Access: Yes, you can access elements directly using their index. However, it is important to note that accessing elements by index in an ArrayList is not as efficient as accessing elements by index in an array.
· Index Range: The index range of an ArrayList is from 0 to size — 1, where size is the number of elements in the ArrayList.
· Memory Overhead: ArrayList has a memory overhead due to the wrapper objects used for primitive types and additional bookkeeping for dynamic resizing.
· Homogeneous Elements: ArrayLists can hold elements of different types. However, it is more efficient to store elements of the same type in an ArrayList.
// Give type as Object to Store differnt elements
ArrayList<Object> myList = new ArrayList<>();
myList.add("Hello");
myList.add(10);
myList.add(new Date())A sample code of ArrayList-
package sam.collection.arraylistexample;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
/* A good video
https://www.youtube.com/watch?v=M_0q6rGUsNc&ab_channel=KeepOnCoding
*/
public class ArrayListExample {
public static void main(String[] args) {
// ArrayList No fixed size. You can't use Primitive data types so use Wrapper Class.
ArrayList<String> friends = new ArrayList<>();
friends.add("Monica");
friends.add("Anna");
friends.add("Chandler");
// We can easily add element to the end of ArrayList
friends.add("Xena");
// get the size of the ArrayList
System.out.println("The size of the ArrayList " + friends.size());
// Get index based on the value.
int monicaIndex = friends.indexOf("Monica");
System.out.println("monicaIndex== " + monicaIndex);
// Change the value of an ArrayList using Index
friends.set(0, "Meena");
// Get element using index
System.out.println("First element of the ArrayList is= " + friends.get(0));
// sort Ascending order (default)
Collections.sort(friends); // Sort the ArrayList
for (String friend : friends) {
System.out.println(friend);
}
// Descending order using a custom comparator
Collections.sort(friends, Collections.reverseOrder());
System.out.println("Descending order:");
for (String friend : friends) {
System.out.println(friend);
}
// Add elements while initiating.
ArrayList<String> foods = new ArrayList<>(Arrays.asList("Pizza", "Burger", "Bacon"));
// later you can add more.
foods.add("Pastry");
// Remove elements using index
foods.remove(0);
// Remove elements using value
foods.remove("Burger");
System.out.println(foods);
}
}LinkedList
Explanation: LinkedList is a data structure where each element (node) contains a value and references to the next and previous elements.
It forms a chain-like structure.
Major Characteristics:
Dynamic size: Can grow or shrink based on the number of elements.
Efficient add/remove at start/end: Constant time for these operations.
Requires traversal: Accessing elements or adding/removing in the middle requires traversing the list.
Not memory-efficient: Extra references for next and previous elements.
When to Use:
When frequent insertions or removals are needed at the beginning or end.
When the order of elements matters and needs to be maintained.
For implementing queues, stacks, or other data structures with specific insertion/removal patterns.
When you can accept slightly lower performance for certain operations in exchange for flexibility.
linked lists are not thread-safe by default.
When to Use and When Not to Use:
Use Array when the collection size is known and fixed, and you need direct access by index.
Use ArrayList when the collection size may change and you need both random access and automatic resizing.
To add/remove elements at the end, ArrayList might be more efficient,because appending elements to the end does not require shifting of existing elements.
Use LinkedList when you require efficient add/remove operations at the beginning or middle, or when you need to maintain the order of elements.
Avoid using Array or ArrayList when frequent insertions/removals are required in the middle, as these operations can be inefficient due to element shifting.
Avoid using LinkedList when you need frequent random access, as accessing elements by index in a LinkedList is slower compared to ArrayList.
Detailed summary
· Data Type: A linked list can store elements of any type, including primitive types and wrapper classes. However, it is more efficient to store primitive types in a linked list, as the wrapper classes need to be boxed and unboxed, which takes time.
· Get value using index: Yes, you can get the value at a specific index in a linked list using the get() method. The get() method takes an index as its argument and returns the element at that index.
· Mandatory to Define Size When Initiated?: No, you do not need to define the size of a linked list when you create it. The linked list will grow or shrink as needed.
· Fixed Size: No, linked lists are not fixed size. They can grow or shrink as needed.
· Default Capacity: Linked lists do not have a default capacity.
· Add Values after initialization: Yes, you can add values to a linked list after it has been initialized. You can use the add() method to add a value to the end of the linked list.
· Duplicate Values: Yes, linked lists can store duplicate values.
· Null Values: Yes, linked lists can store null values.
· Remove Values: Yes, you can remove values from a linked list. You can use the remove() method to remove a value at a specific index.
· Replace values: Yes, you can replace values in a linked list. You can use the set() method to replace the value at a specific index.
· Maintain the Order: Linked lists do not maintain the order of elements as they are added. The order of the elements in a linked list depends on how the elements are added to the list.
· Storing Value In Memory As: Linked lists store values as objects. This is because the elements of a linked list are references to objects, not the objects themselves.
· Sorting: Use Collections.sort() method.
· Direct Access: No, you cannot access elements directly using their index in a linked list. You need to traverse the linked list to get to the element that you want to access.
· Index Range: Linked lists do not have an index range.
· Memory Overhead: Linked lists have a lower memory overhead than ArrayLists, as they do not need to store any additional bookkeeping information.
· Homogeneous Elements: Linked lists can hold elements of different types. However, it is more efficient to store elements of the same type in a linked list.
Sample Code-
package sam.linkedlistexample;
import java.util.Collections;
import java.util.Iterator;
import java.util.LinkedList;
/*
https://www.youtube.com/watch?v=5dscMs2hnDI&ab_channel=CodingwithJohn
Linked lists have references to next and previous elements like a chain. This is how linked lists are able to maintain the order of their elements. Each element in a linked list has a reference to the next element in the list, and the last element in the list has a reference to null.
Getting the value at a specific index in a linked list is slow. This is because you need to traverse the linked list from the beginning to find the element at the specified index. The more elements there are in the linked list, the longer it will take to get the value at a specific index.
Adding or removing elements at the beginning or end of a linked list is faster than in an ArrayList. This is because you only need to adjust a few references in the linked list to accommodate the change. In an ArrayList, you need to shift the entire array of elements to make room for the new element or to remove an element.
*/
public class LinkedListMain {
public static void main(String[] args) {
LinkedList<String> namesLinkedList= new LinkedList<>();
namesLinkedList.add("Mike");
namesLinkedList.add("Rob");
namesLinkedList.add("Brad");
namesLinkedList.add("Temp");
// Get size
System.out.println(namesLinkedList.size());
// get element by index
System.out.println(namesLinkedList.get(2));
// To remove element using index
namesLinkedList.remove(2);
namesLinkedList.remove("Temp");
// To sort
Collections.sort(namesLinkedList);
System.out.println(namesLinkedList);
// Iterate though LinkedList using Advanced for loop
for (String name : namesLinkedList) {
System.out.println(name);
}
// Also using Iterator
Iterator<String> iterator = namesLinkedList.iterator();
while (iterator.hasNext()) {
String name = iterator.next();
System.out.println(name);
}
// Also using foreach from Java 8 onwards.
namesLinkedList.forEach(name -> {
System.out.println(name);
});
}
}Quick Summary-
