Pages

Showing posts with label LinkedList. Show all posts
Showing posts with label LinkedList. Show all posts

Tuesday, June 2, 2020

List in Collection

List

List Hierarchy in Collection
Fig: List Hierarchy in Collection


Properties
ArrayList
LinkedList
Vector
1
Duplicate allowed?
Allowed
Allowed
Allowed
2
Insertion order?
Preserved
Preserved
Preserved
3
Heterogeneous allowed?
Allowed
Allowed
Allowed
4
Null allowed?
Allowed
Allowed
Allowed
5
Version
1.2
1.2
1.0 legacy
6
Non-synchronized?
Non-sync
Non-sync
Synchronized
7
Implement Random Access
Yes
Not implement
Yes
8
Implement interface Serializable, Cloneble?
Yes
Yes
Yes
9
When to use?
To retrieve object
To add & delete object
Thread safety to retrieve object
10
Underlying Data structure
Array
Doubly linked list
Array
11
How Iteration takes place?
Iterator &
ListIterator
Iterator & ListIterator
Iterator ListIterator and Enumeration too









  


ArrayList:


1.   Implements List (I) and extends AbstractList class.

2.   Underlying Data structure is growable Array (resizable array)

3.   Insertion order is preserved.

4.   Duplicate objects are allowed.

5.   Heterogeneous objects allowed.

6.   “null” insertion is possible.

7. Initial capacity = 10 and new capacity will be new capacity= (3/2 current capacity)+1

8.   It should use when Retrieval operation is performs.

9.   Should not be used in case of insertion and deletion of an objects.

10. Can iterate/traverse using ListIterator and Iterator.

11.It also implements Random Access, serializable and Cloneble interfaces.

12. ArrayList class is same as that of Vector except all methods in Vector are synchronized and ArrayList .

          Please click on link for Oracle Docs for ArrayList 

Note: I've not posted any method's declarations here to avoid any human error. This is Oracle website where we can fully trust and can learn all methods definitions, internal design etc.


Programs on Arraylist:


1. Maintain Insertion Order:

import java.util.*;

public class ArayListInsertionOrder {

     public static void main(String args[]) {

    ArrayList<String> list = new ArrayList<String>(); 
   //Creating ArrayList
   
       list.add("John");// Adding object in ArrayList
       list.add("Adam");
       list.add("Adam"); //Duplicate entry: allowed
       list.add("Chris");
       list.add("Des");

          System.out.println(list); // Printing objects of ArrayList
     }
}

Output:

     [John, Adam, Adam, Chris, Des]

Note: Here Duplicate elements allowed and Insertion order is maintained using ArrayList i.e. how we insert Objects in ArrayList in that order it will executed.


2. Methods of ArrayList:

public class ArrayListMethods {
    
     public static void main(String args[]) {
         
          ArrayList list = new ArrayList(); // Creating Arraylist
         
          /** Check ArrayList is Empty or not : isEmpty()*/
          System.out.println("Is Empty? " + list.isEmpty());
          list.add("John");// Adding object in Arraylist
          list.add("Adam");
          list.add("Chris");
          list.add("Des");
          System.out.println(list); // Printing objects of Arraylist

          /** Check ArrayList is Empty or not: after adding Elements*/
          System.out.println("After adding elements, Is Empty? " + list.isEmpty());
          
          /** Check size of ArrayList: size()*/
          System.out.println("Size of ArrayList: " + list.size());
          
          /** Check Element contained in ArrayList or not: contains()*/
          System.out.println("Contains Element Adam? " + list.contains("Adam"));
          System.out.println("Contains Element Tony? " + list.contains("Tony"));
          
          /** Get selected Element from ArrayList*/
          System.out.println("Get index at 2: " + list.get(2));
          
          /** Remove an Element from ArrayList*/
          list.remove(2); // Remove Index at 1st
          //list.removeAll(list) // Remove Index all elements
          System.out.println("After removing index at 3rd place: " + list);
          
          /** Add 1 list to another: addAll()*/
          ArrayList<String> list2 = new ArrayList<String>(); // Creating new Arraylist
          list2.add("Gary");
          list2.add("Matt");

          list.addAll(1, list2)//adding list2 at 2nd place to Original list
          System.out.println("New List2 is: "+list2);
          System.out.println("Original List: "+list);
          
          /** Set data/element in a ArrayList*/
          System.out.println("Before Setting data: " + list);
          list.set(2, "Ricky");
          System.out.println("After Setting data: " + list);
          
          /** Clear an ArrayList: clear()*/
          list.clear(); // Clear the List
          System.out.println("List is cleared now, No data ==>"+list);
          System.out.println("Is Empty: " + list.isEmpty());
         
          System.out.println("End of ArrayList Tutorial. Thank you....!");
     }
}

Output:

Is Empty? true
[John, Adam, Chris, Des]
After adding elements, Is Empty? false
Size of ArrayList: 4
Contains Element Adam? true
Contains Element Tony? false
Get index at 2: Chris
After removing index at 3rd place: [John, Adam, Des]
New List2 is: [Gary, Matt]
Original List: [John, Gary, Matt, Adam, Des]
Before Setting data: [John, Gary, Matt, Adam, Des]
After Setting data: [John, Gary, Ricky, Adam, Des]
List is cleared now, No data ==>[ ]
Is Empty: true
End of ArrayList Tutorial. Thank you....!


3. How to Iterate an ArrayList? :

We ca iterate using :
1. Iterator interface and 
2. ListIterator  interface


1. Using Iterator interface : (Forward Iteration only)

public class UniDirectionalIteration {

     public static void main(String args[]) {

          ArrayList list = new ArrayList(); // Creating Arraylist

          list.add("John");// Adding object in Arraylist
          list.add("Adam");
          list.add("Chris");
          list.add("Des");
          list.add("Dan");
          list.add("Des");
         
          System.out.println("ArrayList: "+list); // Printing objects of Arraylist

          System.out.println("Iteration as below using Iterator:");
          Iterator itr = list.iterator();
          while (itr.hasNext()) {
              System.out.println(itr.next());
          }
    } 

}

Output:
ArrayList: [John, Adam, Chris, Des, Dan, Des]
Iteration as below:
John
Adam
Chris
Des
Dan
Des


2. Using ListIterator interface : (Forward & Reverse Iteration)

public class BiDirectionalIteration {

     public static void main(String args[]) {

          ArrayList list = new ArrayList(); // Creating Arraylist

          list.add("John");// Adding object in Arraylist
          list.add("Adam");
          list.add("Chris");
          list.add("Des");
          list.add("Dan");
          list.add("Des");
         
          System.out.println("ArrayList: "+list);

          // Forward iteration
          System.out.println("Forward Iteration :- ");
          ListIterator listItr = list.listIterator();
          while (listItr.hasNext()) {
              System.out.println(listItr.next());
          }

          System.out.println("Reverse iteration:- ");
          // Reverse iteration
          while (listItr.hasPrevious()) {
              System.out.println(listItr.previous());
          }
     }
}


Output:

ArrayList: [John, Adam, Chris, Des, Dan, Des]

Forward Iteration :- 
John
Adam
Chris
Des
Dan
Des

Reverse iteration:- 
Des
Dan
Des
Chris
Adam
John



LinkedList

1.   Came in 1.2 version, implement List, Cloneble, serializable.

2.   Underlying Data structure is doubly LinkedList.

3.   Best choice when used for insertion and deletion of an objects.

4.   Not good for retrieving an object.

5.   Duplicates allowed.

6.   Insertion order maintained.

7.   “null” insertion possible.

8.   Heterogeneous object possible.

9.   Not implements Random Access.

          Please click on link for Oracle Docs for LinkedList 


Programs on LinkedList:

1. Basic program: adding of LinkedList :

public class A {

public static void main(String args[]) {

         LinkedList linList = new LinkedList(); // Creating LinkedList

          linList.add("Adam");
          linList.add("Chris");
          linList.add("John");
          linList.add("John");
          linList.add("Des");
         System.out.println(linList);
     }
}

Output:

[Adam, Chris, John, John, Des]



2. Methods of LinkedList? :



public class LinkedListMethods {

     public static void main(String args[]) {

          LinkedList lnkList = new LinkedList();
          lnkList.add("Minerals");
          lnkList.add("Protein");
          lnkList.add("Carbohydrate");
          lnkList.add("Fat");
          lnkList.add("Calcium");
          lnkList.add("Vitamins");

          System.out.println(lnkList);

          /** peek methods: Only retrieves element not remove: */
          System.out.println("peek: " + lnkList.peek());
          System.out.println("peekFirst: " + lnkList.peekFirst());
          System.out.println("peekLast: " + lnkList.peekLast());

          /** getFirst and getLast elements: */
          System.out.println("getFirst: " + lnkList.getFirst());
          System.out.println("getLast: " + lnkList.getLast());

          /** poll methods: Retrieves and remove element: */
          System.out.println(lnkList);
          System.out.println("poll: " + lnkList.poll());
          System.out.println(lnkList);
          System.out.println("pollFirst: " + lnkList.pollFirst());
          System.out.println(lnkList);
          System.out.println("pollLast: " + lnkList.pollLast());

          System.out.println("LinkList: " + lnkList);

          /** Add first and last element: */
          lnkList.addFirst("Iron");
          lnkList.addLast("Sodium");
          System.out.println("After adding first and Last element:" + lnkList);

          /** Remove first and last element: */
          System.out.println("removeFirst: " + lnkList.removeFirst());
          System.out.println("removeFirst: " + lnkList.removeLast());

          System.out.println("LinkList: " + lnkList);
     }
}


Output:
[Minerals, Protein, Carbohydrate, Fat, Calcium, Vitamins]
peek: Minerals
peekFirst: Minerals
peekLast: Vitamins
getFirst: Minerals
getLast: Vitamins
[Minerals, Protein, Carbohydrate, Fat, Calcium, Vitamins]
poll: Minerals
[Protein, Carbohydrate, Fat, Calcium, Vitamins]
pollFirst: Protein
[Carbohydrate, Fat, Calcium, Vitamins]
pollLast: Vitamins
LinkList: [Carbohydrate, Fat, Calcium]
After adding first and Last element:[Iron, Carbohydrate, Fat, Calcium, Sodium]
removeFirst: Iron
removeFirst: Sodium
LinkList: [Carbohydrate, Fat, Calcium]



3. How to Iterate an LinkedList? :

It can iterate same as of ArrayList



Vector :

1.   Legacy class.

2.   Underlying Datastructure growable array.

3.   Duplicates allowed.

4.   Insertion order maintained.

5.   Heterogeneous object allowed.

6.   Null insertion possible.

7.   Implements Random access, Serializable, Cloneble and List.

8.   All methods are (thread safe) synchronized.

9.   Same as that of ArrayList except this synchronized.

10.Initial capacity= 10; new capacity= current capacity*2;

11.addElement () used to add element.

12.Can iterate using all cursors Listiterator, iterator and Enumeration.

          Please click on link for Oracle Docs for Vector 

Note: Methods in ArrayList and Vector are same. So programs will be same


Iteration of vector:

Vector can iterate same as of ArrayList using Iterator and ListIterator interface.
But in List, only Vector can be iterate using Enumeration interface as below:



public class EnumarationIteration {

     public static void main(String args[]) {

          Vector vector = new Vector();
          vector.add("Protein");
          vector.add("Carbohydrate");
          vector.add("Fat");
          vector.add("Calcium");
          vector.add("Vitamins");

          Enumeration en = vector.elements();

          System.out.println("Vector List: "+vector);
          System.out.println("Iteration using Enumeration:");

          while (en.hasMoreElements()) {
              System.out.println(en.nextElement());
          }
     }
}


Output:
Vector List: [Protein, Carbohydrate, Fat, Calcium, Vitamins]
Iteration using Enumeration:
Protein
Carbohydrate
Fat
Calcium
Vitamins




Stack: (Subclass of Vector) :
1.   Legacy class (1.0).

2.   Synchronized.

3.   Duplicates allowed.

4.   Insertion order maintained.

5.   Child class of vector and implement serializable + Cloneble.

6.   When LIFO order used / required then to for stack.

7.   Contains only one constructor.

Please click on link for Oracle Docs for Stack 


Methods of Stack:

·         Object push (obj o) --- add element
·         Object pop() --- remote and return top element
·         Object peek () --- return top element without remove
·         Boolean empty() ---(true) if empty
·         int search (obj o) --- search element 


Program of Stack:

public static void main(String[] args) {

                   Stack s=new Stack();  //Stack object created
                   s.push("A");
                   s.push("B");
                   s.push("C");
                   s.push("D"); //added element (A,B,C,D)

                   System.out.println(s); //[A B C D]

                   System.out.println(s.pop()); //D
                   System.out.println(s); //[A B C]

                   System.out.println(s.peek());//C
                   System.out.println(s);//[A B C]

                   System.out.println(s.search("A")); //3
                   System.out.println(s.search("Z")); //-1 not in list= -1

                   System.out.println(s.empty()); //false
          }