Array List:
- ArrayList is a part of the Collection Framework and implements the java List Interface. This class provides the methods to resize the list based on needs.
- It allows having null and duplicate values.
- The Array List is similar to a vector in java except that it is unsynchronized. It is not thread-safe but faster than vectors.
- It is an ordered collection that can insert elements with help of indexes.
- ArrayList can hold only objects but cannot handle primitive types.
The operations performed in ArrayList are:
- add() – insert element to ArrayList
- clear() – remove all elements from list.
- contains() – check if the element is present in the list.
- get() – returns the index of element.
- size() – return size of list.
Below is the code to show the implementation of the ArrayList:
Java
// To implement list we need to add this// util package.import java.io.*;import java.util.*;class GFG { public static void main(String[] args) { ArrayList<String> al = new ArrayList<String>(); // Add elements to the ArrayList al.add("Java"); al.add("Python"); al.add("JavaScript"); al.add("PHP"); System.out.println(al); // Get elements by index System.out.println("Element at given index: " + al.get(1)); System.out.println("Does list contains JAVA? " + al.contains("JAVA")); // Add elements at a specific index al.add(2, "MySql"); System.out.println(al); System.out.println("To check list empty or not:" + al.isEmpty()); System.out.println("Index of PHP:" + al.indexOf("PHP")); System.out.println("Size of the arraylist is: " + al.size()); }} |
Output
[Java, Python, JavaScript, PHP] Element at given index: Python Does list contains JAVA? false [Java, Python, MySql, JavaScript, PHP] To check list empty or not:false Index of PHP:4 Size of the arraylist is: 5
Advantages of ArrayList:
- It is very fast because of its asynchronous behavior.
- It maintains order which means the new element added directly to the end of the list
- When ArrayList is exceeded, the size is increased by 50% only.
- It is dynamic in size
Disadvantages of ArrayList:
- ArrayList only holds objects but not primitive types.
- If the element is removed from the array, the whole array is shifted to update the list which leads to memory wastage.
- Data is arranged in a sequential manner, for larger lists, it required a larger contiguous block of memory.
Queue:
- A queue is an abstract linear data type that follows FIFO(first-in-first-out).
- A queue can enqueue elements at the rear end and dequeue elements from the front end.
- Java has a Queue Interface which is a part of the Collection framework.
The operations performed in the queue are:
- enqueue(): This adds an item or data to the queue.
- dequeue(): Dequeue removes the item from the queue.
- peek(): This function gets the element at the front without removing it.
- isfull(): This checks if the queue is full.
- isempty(): This function checks if the queue is empty or not.
Below is the implementation of Queue in Java:
Java
// Java code to implement Queue:import java.util.*;// Define queue classclass GFG { int arr[], front, rear, cap, n1; // Queue constructor GFG(int n) { arr = new int[n]; cap = n; front = 0; rear = -1; n = 0; } // dequeue function for removing the // front element public void dequeue() { // Check for queue underflow if (isEmpty()) { System.out.println( "No items in the queue, cannot delete"); System.exit(1); } System.out.println("Deleting " + arr[front]); front = (front + 1) % cap; n1--; } // enqueue function for adding an item // to the rear public void enqueue(int val) { // Check for queue overflow if (isFull()) { System.out.println( "OverFlow!!Cannot add more values"); System.exit(1); } System.out.println("Adding " + val); rear = (rear + 1) % cap; arr[rear] = val; n1++; } // Peek function to return front // element of the queue public int peek() { if (isEmpty()) { System.out.println( "Queue empty!!Cannot delete"); System.exit(1); } return arr[front]; } // Returns the size of the queue public int size() { return n1; } // To check if the queue is empty // or not public Boolean isEmpty() { return (size() == 0); } // To check if the queue is full // or not public Boolean isFull() { return (size() == cap); } // Queue implementation in java public static void main(String[] args) { // Create a queue of capacity 5 GFG q = new GFG(5); q.enqueue(10); q.enqueue(20); q.enqueue(30); System.out.println("Front element is: " + q.peek()); q.dequeue(); System.out.println("Front element is: " + q.peek()); System.out.println("Queue size is " + q.size()); q.dequeue(); q.dequeue(); if (q.isEmpty()) System.out.println("Queue Is Empty"); else System.out.println("Queue Is Not Empty"); }} |
Output
Adding 10 Adding 20 Adding 30 Front element is: 10 Deleting 10 Front element is: 20 Queue size is 2 Deleting 20 Deleting 30 Queue Is Empty
Advantages of Queue:
- The queue has two ends, one for inserting other for deleting.
- Enqueue and dequeue take only O(1) time.
- Queues are flexible
- It is helpful in managing multiple user needs.
Disadvantages of Queue:
- Inserting and deleting elements from the middle is complex.
- Size is limited and predefined.
- The new element cannot be inserted when the queue is full, the old element has to be removed to insert a new one.
- Memory is not efficiently used, as when we delete an element that memory is not utilized again in a linear queue, this can be overcome by using a circular queue.
When to use queues over ArrayList?
- The queues are efficiently used when the size is predefined, as it is not possible to increase the size the of queue dynamically.
- When the operation of deleting and inserting elements in the middle of the list is not there, it is easy to implement with the help of queues as it can insert and delete elements at ends with O(1) complexity.
- For example, in a shopping mall billing counter, it is frustrating to work with ArrayList when customers from the middle come for billing. Instead using a queue data structure is clear and easy for billing. As we know, by using a queue we have to follow FIFO so that the first customer will get the bill first without any complications. By using ArrayList there are chances that it can add or remove elements from the middle of the list. Using queues for such scenarios can help in better optimization and concurrency.
- From the above example, we can conclude that we have to use queue when we want the operation of the elements in order, while we have to use ArrayList when we want data from the middle of the list, and size is not predefined.
- Stacks and Queues are implemented using lists but the insertion and deletion of elements are restricted to only ends.
- Queues are used when multiple objects wish to use a “resource”, but only one object can use the resource at a time.
