Arrays, Collection Framework - Yash-777/MyWorld GitHub Wiki

What are Data Structures?

Data Structure is used for organizing the data in memory. There are various ways of organizing the data in the memory, for eg. array, list, stack, queue, and many more.

A data structure is defined as a format for arranging, processing, accessing, and storing data.

Array

An array is a collection of similar data elements stored at contiguous memory locations. It is the simplest data structure where each data element can be accessed directly by only using its index number.

The length of an array is established when the array is created. After creation, its length is fixed.

An array of 10 elements

Creating, Initializing, and Accessing an Array

int[] anArray;         // declares an array of integers
anArray = new int[10]; // allocates memory for 10 integers
anArray[0] = 100;      // initialize first element

System.out.println("Element 1 at index 0: " + anArray[0]);  // Accessing

Copying Arrays System.arraycopy(Object src, int srcPos, Object dest, int destPos, int length) : void

The java.lang.System.arraycopy() method copies an array from the specified source array, beginning at the specified position, to the specified position of the destination array. A subsequence of array components are copied from the source array referenced by src to the destination array referenced by dest.The number of components copied is equal to the length argument.

Exception thrown

• IndexOutOfBoundsException − if copying would cause access of data outside array bounds.
• ArrayStoreException − if an element in the src array could not be stored into the dest array because of a type mismatch.
• NullPointerException − if either src or dest is null.

int arr1[] = { 0, 1, 2, 3, 4, 5 };
int[] arr2 = new int[10];

// copies an array from the specified source array
System.arraycopy(arr1, 3, arr2, 2, 2);  // arr2 = { 0, 0, 3, 4, 0, 0, 0, 0, 0, 0} 

ArrayList internally uses System.arraycopy() ^sourcecode

Array Manipulations (common tasks, such as copying, sorting and searching arrays)

java.util.Arrays methods

equals(int[] a, int[] a2)                     : boolean  //Returns true if the two specified arrays of ints are equal to one another.
copyOf(int[] original, int newLength)         : int[]    //Copies the specified array, truncating or padding with zeros (if necessary) so the copy has the specified length.
copyOfRange(int[] original, int from, int to) : int[]    //Copies the specified range of the specified array into a new array.
sort(int[] a)          : void     //Sorts the specified array into ascending numerical order.
parallelSort(int[] a)  : void     //Sorts the specified array into ascending numerical order.

int[] copyFrom = { 0, 1, 2, 3, 4, 5 };
int[] copyTo  = java.util.Arrays.copyOfRange(copyFrom, 2, 5);
System.out.println(java.util.Arrays.toString(copyTo)); // [1,2,3,4]

Programs:

Find minimum and maximum value of an array
Reverse of an Array, find duplicate numbers, largest and smallest value

What is Collection in Java?

A collection — sometimes called a container — is simply an object that groups multiple elements into a single unit. Collections are used to store, retrieve, manipulate, and communicate aggregate data. Typically, they represent data items that form a natural group, such as a poker hand (a collection of cards), a mail folder (a collection of letters), or a telephone directory (a mapping of names to phone numbers).

Any group of individual objects which are represented as a single unit is known as the collection of the objects. In Java, a separate framework named the “Collection Framework” has been defined in JDK 1.2 which holds all the collection classes and interface in it. The Collection interface (java.util.Collection) and Map interface (java.util.Map) are the two main “root” interfaces of Java collection classes.

What is the difference between Array and Collection in java?

Explain the various interfaces used in the Collection framework.

A List is an ordered Collection (sometimes called a sequence). Lists may contain duplicate elements.

ArrayList:
DataStructure:ResiableArray
Ordered by index(insertion order is preserved) - Intert and retreivew the data in same order Ex: 1,2,3
Implements RandomAccess Interface. So that any rondom element can be accessed at same speed

Dis Adv:- For insertion and deletion of elements it is slow because it needs several shifts among the array indexs.


Vector: same as ArrayList but its synchronized (thread safe)
stack: same as vector     {s.push(10), s.pop(10)}


ArrayList al = new ArrayList( Arrays.asList("A", "B") );
List synchronizedList = Collecitons.synchronizedList( al );

LinkedList
DataStructure: DoubleLinkedList
ordered by index (means we can insert data between two nodes as well)  
Ex:- Input:  3->5->8->10, data = 2, position = 2
     Output: 3->2->5->8->10

LinkedList list = new LinkedList();
list.add(E element)
lsit.add(int index,E element)

ArrayList<Integer> al = new ArrayList<Integer>(); // Generics - Type argument
al.add(10);
al.add(30);
al.add(1, 20); // add(index, object)

al.get(0);
System.out.println(al);

LinkedList<Integer> ll = new LinkedList<Integer>();
ll.add(10);
ll.add(30);
ll.add(1, 20); // add(index, object)

ll.get(0);
ll.getFirst(); ll.getLast();
System.out.println(ll);

A Set is a Collection that cannot contain duplicate elements.

HashSet: Elements inserted based on hashcode, insertion order is not maintained.
DataStructure - HashTable

LinkedHashSet: display in the order we insert
DataStructure - HashTable + DoubleLinkedList

TreeSet: Insertion order is not maintained as elements get sorted before insertion
DataStructure - BalancedTree

A Map is an object that maps keys to values. A map cannot contain duplicate keys: Each key can map to at most one value. It models the mathematical function abstraction. The Map interface includes methods for basic operations (such as put, get, remove, containsKey, containsValue, size, and empty), bulk operations (such as putAll and clear), and collection views (such as keySet, entrySet, and values).

Map implementations: HashMap, TreeMap, and LinkedHashMap

Cursors are mainly used to access the elements of any collection. We have the following three types of cursors in Collection Framework:

• Iterator: This cursor is used to access the elements in the forward direction only. This cursor can be applied to any Collection Interfaces. While accessing the methods we can also delete the elements.

Syntax: Iterator it = c.iterator();

Methods of Iterator:
boolean hasNext(): returns true if there is a next element in the array list.
Object next(): returns the next element in the array list.
void remove(): removes an element from an array list.

• ListIterator: This cursor is used to access the elements of Collection in both forward and backward directions. This cursor can be applied only for List category Collections. While accessing the methods we can also add, set, delete elements.

LinkedList < Integer > ll = new LinkedList < Integer > ();

ListIterator < Integer > lit = ll.listIterator ();
  System.out.println ("Elements in Forward Direction");
  while (lit.hasNext ())
  {
   System.out.println (lit.next () + " ");
  }

    System.out.println ("\n elements in Backward direction");
    while (lit.hasPrevious ())
    {
     System.out.println (lit.previous () + " ");
    }

• Enumeration: This cursor is used to access the elements of Collection only in a forward direction. This is a legacy cursor and can be applied only for legacy classes like Vector, Stack, Hashtable.

Methods of Enumeration
boolean hasMoreElements(): When implemented, it must return true while there are still more elements to extract
                           and false when all the elements have been enumerated.
Object nextElement(): This returns the next object in the enumeration as a generic Object reference.

Vector<Integer> v = new Vector<Integer>();
Enumeration e = v.elements();
  while(e.hasMoreElements()) {
   System.out.println(e.nextElement()+" ");
  }

Comparison Between Iterator, ListIterator and Enumeration Cursors in Java ^ref

ArrayList vs Vector

Hashtable<String, Integer> hashTable = new Hashtable<String, Integer>();
//hashTable.put(null, null); // java.lang.NullPointerException
//hashTable.put("null", null); // java.lang.NullPointerException
System.out.println(hashTable);

HashMap<String, Integer> hashMap = new HashMap<String, Integer>();
hashMap.put(null, null);
hashMap.put("nul", null);
System.out.println(hashMap);

The java.util.concurrent package includes a number of additions to the Java Collections Framework. These are most easily categorized by the collection interfaces provided:

• BlockingQueue defines a first-in-first-out data structure that blocks or times out when you attempt to add to a full queue, or retrieve from an empty queue.
• ConcurrentMap is a subinterface of java.util.Map that defines useful atomic operations. These operations remove or replace a key-value pair only if the key is present, or add a key-value pair only if the key is absent. Making these operations atomic helps avoid synchronization. The standard general-purpose implementation of ConcurrentMap is ConcurrentHashMap, which is a concurrent analog of HashMap.
• ConcurrentNavigableMap is a subinterface of ConcurrentMap that supports approximate matches. The standard general-purpose implementation of ConcurrentNavigableMap is ConcurrentSkipListMap, which is a concurrent analog of TreeMap.