Java 6 Collections: Why use LinkedList

Java collections framework avoid the idiosyncratic programming. Therefore, collection framework is more manageable and usability is unified across the applications, and best practices are enforced. Anyway, it is very important to understand the generics based new collection framework.

I love to do programming with Eclipse. As shown in the above figure, the instance variable ‘d’ can be initialized with with the ‘ArrayList’ whose parameterized type is ‘Dog’. The type of the instance variable d is ‘List’ which is also based on ‘Dog’ generic type. To this array you can add only instances which are type of ‘Dog’. If the generic type is changed to ‘Integer,’ everything will change from ‘Dog’ to ‘Integer’.

If you are comfortable with Java Generics, this is the time to consider that how they have implemented Collection to cater for any Object.

Linked List

Array and her counterpart ArrayList has direct access which cost Ο(1) time . Comparably, this is the cheapest. However, array has a problem of removing or inserting an element to the middle of the array, because all the elements beyond the removed element must be moved toward the beginning of the array. LinkedList solves the problem because it cost Ο(1) for insert and delete operation. But for the search operation it costs Θ(n) in the worst case. An array stores instance references in the sequential manner  (use consecutive memory locations ), unlike Linkedlist uses node (link) to store.

LinkedList is ordered collection in which the position of the of the object determined by the insertion order. However, if you just use add() method, instance variable will be added to the end. There is add() method available in the the ListIterator. In addition to that ListIterator provides two other methods which are previous() and the hasPrevious() methods. The method set() is another operator available in the ListIterator.

package com.ojitha.list;

import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;

/**
* This program demonstrate the use of Linked List.
*
* @version 1.0 2009-06-30
* @author Ojitha K.
*
*/
public class LinkedListTest {

 /**
  * @param args
  *            command line arguments
  */
 public static void main(String[] args) {
  List people = new LinkedList();

  // add element to the beginning of the List
  people.add("Ojitha");
  people.add("Kamal");
  people.add("Erica");

  // use toString() method to display the contents
  System.out.println("Poeple: " + people);

  // add 'Ruwan' to in between 'Kamal' and 'Erica'
  ListIterator LIt = people.listIterator();
  // pass 'Ojitha' and 'Kamal'
  LIt.next();
  LIt.next();
  LIt.add("Ruwan");
  // use toString() method to display the contents
  System.out.println("Add 'Ruwan' to the Poeple: " + people);

  // if you add another person
  LIt.add("John");

  // use toString() method to display the contents
  System.out.println("After add 'John' to the Poeple: " + people);

  // go back and remove Kamal
  LIt.previous(); // at John
  LIt.previous(); // at Ruwan
  LIt.previous(); // at Kamal
  LIt.remove(); // Remove Kamal

  // use toString() method to display the contents
  System.out.println("After removed 'Kamal' in the Poeple: " + people);

  // goto 'ruwan' and replace with 'Mark'
  LIt.next();
  LIt.set("Mark");

  // use toString() method to display the contents
  System.out.println("After replaced 'Ruwan' in the Poeple: " + people);

  System.out.println("Next index is " + LIt.nextIndex());

  Iterator it = people.iterator();
  // go three elements forward
  it.next();
  it.next();
  it.next();
  // remove 'John'
  it.remove();

  // use toString() method to display the contents
  System.out.println("After removed 'John' in the Poeple: " + people);

  // now if you try to change the LinkedList by the you will get
  // java.util.ConcurrentModificationException
  try {
   LIt.previous();
   // LIt.remove();
   // use toString() method to display the contents
   System.out.println("try to move to 'Ojitha' in the Poeple: "
     + people);
  } catch (java.util.ConcurrentModificationException e) {
   System.out.println("cannot delete, concurrent exception");
  }

  try {
   // without forward try to remove the item
   it.remove();
  } catch (java.lang.IllegalStateException e) {
   System.out.print("without forward cannot delete");
  }

 }

}

As shown in the above code, ListIterator plays a major role. Remember, LinkedList don’t support fast random access. If the linked List find that