LinkedList Class In Collection Framework

LinkedList collection class in present under java.util package. LinkedList underlying data structure is double linked list. As LinkedList implements List interface, so duplicates are allowed in LinkedList and insertion order is preserved. If we are not using generic implementation of LinkedList then Heterogeneous objects are allowed in LinkedList same as ArrayList. (Note: Except TreeSet and TreeMap every where in Collection Framework Heterogeneous objects are allowed for non generic concrete implementation class). Null insertion is also possible in LinkedList.

LinkedList class implements List,Cloneable, Serializable interfaces  and extends AbstractSequentialList class, but LinkedList  class not implements RandomAccess Interface.  Let see the LinkedList class declaration:

 

LinkedList Constructors

 

 Constructor Description
LinkedList() LinkedList list = new LinkedList();

There is no such type of terminology  like default capacity, initial capacity. It simply create a node & add it.

LinkedList(Collection c) Creates an equivalent LinkedList object for the given collection

 

 

LinkedList Methods

Methods Description
public boolean add(E e) Appends the specified element to the end of this list.
public void add(int index, E element)  Inserts the specified element at the specified position in this list.
public void addAll(int index, Collection<? extends E> c)  Inserts all of the elements in the specified collection into this list, starting at the specified position.
 public void clear()  Removes all of the elements from this list.
 public boolean contains(Object o)  Returns true if this list contains the specified element.
 public Object clone() Returns a shallow copy of this LinkedList.
 public E get(int index)  Returns the element at the specified position in this list.
 public int indexOf(Object o)  Returns the index of the first occurrence of the specified element in this list, or -1 if this list does not contain the element.
 public int lastIndexOf(Object o)  Returns the index of the last occurrence of the specified element in this list, or -1 if this list does not contain the element.
 public ListIterator<E> listIterator()  Returns a list iterator over the elements in this list (in proper sequence). The returned list iterator is fail-fast, if the list is structurally modified at any time after the Iterator is created, in any way except through the list-iterator’s own remove or add methods, the list-iterator will throw a ConcurrentModificationException.
 public ListIterator<E> listIterator(int index) Returns a list-iterator of the elements in this list (in proper sequence), starting at the specified position in the list.
public E remove(int index) Removes the element at the specified position in this list.
public boolean remove(Object o) Removes the first occurrence of the specified element from this list, if it is present. If the element is not present in the list, it is unchanged.
public int size() Returns the number of elements in this list.
public E set(int index, E element) Replaces the element at the specified position in this list with the specified element.
public Spliterator<E> spliterator() Creates a late binding and fail-fast Spliterator over the elements in this list.
public Object[] toArray() Returns an array containing all of the elements in this list in proper sequence (from first to last element).
public <T> T[] toArray(T[] a) Returns an array containing all of the elements in this list in proper sequence (from first to last element); the runtime type of the returned array is that of the specified array.

 

Usually we can use LinkedList to implements stacks & Queue. To provide support for this requirement LinkedList class defines following specific method.           

For Stack (LIFO) Description
public void addLast(E e) Appends the specified element to the end of this list.
public E getLast() Returns the last element in this list.
public E removeLast() Removes and returns the last element from this list.

   

For Qeue (FIFO) Description
public void addFirst(E e) Inserts the specified element at the beginning of this list.
public E getFirst() Returns the first element in this list.
public E removeFirst() Removes and returns the first element from this list.

Non-generic LinkedList Vs Generic LinkedList Collection

Java collection framework was non-generic before JDK 1.5. Afterward version it is generic now. Java new generic collection allows you to have only one type of object in collection. Now it is type safe so typecasting is not required at run time.

Non-generic LinkedList

Generic LinkedList

//creating non-generic LinkedList

LinkedList list=new LinkedList();

//creating generic LinkedList

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

It is not type safe so typecasting is required at run time, If we add objects of different types. LinkedList as generic collection, is forced to have only specified type of objects in it, so it is type safe. If you try to add another type of object, it will give compile time error.

 

Note: ArrayList & Vector classes implements RandomAccess Interface, which is Marker Interface as it doesn’t contain any method, but LinkedList does not implement RandomAccess Interface.

Note:

  1. LinkedList is the best choice, if our frequent operations is insertion or deletion from the middle.
  2. LinkedList is the worst choice, if our frequent operations is retrieval.

Difference Between ArrayList and LinkedList

ArrayList LinkedList
Underlying data structure is re-sizable or grow-able Array Underlying data structure is Double LinkedList
ArrayList implements RandomAccess interface LinkedList not implements RandomAccess interface
ArrayList is best choice if our frequent operation is retrieval. LinkedList is best choice if our frequent operation is insertion & deletion.
ArrayList is worst choice if our frequent operation is insertion & deletion. LinkedList is worst choice if our frequent operation is retrieval.

 

 

Leave a Reply

Your email address will not be published. Required fields are marked *