Set
- Set prevents duplication.The common use of set is to check for duplication
- Since its is helpful for lookups for duplicate value HashSet provides an optimized implementation
- If you want the result to be sorted use TreeSet instead of HashSet
Daily Archives: July 10, 2013
ArrayList vs LinkedList
Why ArrayList Faster than LinkedList during Random Access?
ArrayList has direct references to every element in the list, so it can get the n-th element in constant time. LinkedList has to traverse the list from the beginning to get to the n-th element.
Why LinkedList faster than ArrayList during Insertion/Deletion?
ArrayList is slower because it needs to copy part of the array in order to remove the slot that has become free. If the deletion is done using the ListIterator.remove() API, LinkedList just has to manipulate a couple of references; if the deletion is done by value or by index, LinkedList has to potentially scan the entire list first to find the element(s) to be deleted.
- LinkedList takes constant-time insertions or removals. I can walk the list forwards or backwards, but grabbing an element in the middle takes time proportional to the size of the list.
- ArrayLists allows random access, so I can grab any element in constant time. But adding or removing from anywhere but the end requires shifting all the latter elements over, either to make an opening or fill the gap. Also, if I add more elements than the capacity of the underlying array, a new array (twice the size) is allocated, and the old array is copied to the new one, so adding to an ArrayList is O(n) in the worst case but constant on average.
- Iterating over both the Types is equally cheap.
- If you have large lists, the memory usage is different. Each element of a LinkedList has more overhead since pointers to the next and previous elements are also stored
When should I use LinkedList?
- When you need efficient removal in between elements or at the start.
- When you don’t need random access to elements, but can live with iterating over them one by one
When should I use ArrayList?
- When you need random access to elements (“get the nth. element”)
- When you don’t need to remove elements from between others. It’s possible but it’s slower since the internal backing-up array needs to be reallocated.
- Adding elements is amortized constant time (meaning every once in a while, you pay some performance, but overall adding is instantly done)
| Operation | Linked List | Array List |
|---|---|---|
| Access | O(n) | O(1) |
| Insertion | Access time + O(1) | Access time + O(n) |
| Deletion | Access time + O(1) | Access time + O(n) |
Iterator vs ListIterator
When you are simple moving through List but you are not modifying the List object foreach is more efficient.In case you want to perform operations on each element of list individually taking out the element in such case use Iterator.
List<Fruits> arrFruits = new ArrayList<Fruits>();
Iterator<Fruits> itFrt = arrFruits.iterator();
while(itFrt.hasNext())
{
Fruits frt = itFrt.next();
System.out.println(frt);
}
ListIterator
- While using Iterator in particular to List using a ListIterator is more powerful over Iterator.
- ListIterator is bidirectional
- It also keep track of Indexes of next and previous elements
- It can replace last element it visited using set method
List<fruits> arrFruits = fruits.arrayList(5);
ListIterator<fruits> itFrt = arrFruits.listIterator();
while(itFrt.hasNext())
{
System.out.println(it.next());
System.out.println(it.nextIndex());
System.out.println(it.previousIndex());
}
List Notes
- List maintains elements in Particular Sequence.
- Two types of List 1.ArrayList and 2.LinkedList
- ArrayList is faster while accessing elements but slower while Insertion and Deletion
- LinkedList is slow in random access but faster during insertion and deletion
Operations in ArrayList
class Fruits
{
String Name = "Fruit";
}
class Apple extends Fruits
{
public Apple()
{
Name = "Apple";
}
}
class Orange extends Fruits
{
public Orange()
{
Name = "Orange";
}
}
class Mango extends Fruits
{
public Mango()
{
Name = "Mango";
}
}
Adding Element – List.add()
List<Fruits> arrFruits = new ArrayList<Fruits>(); Fruits objApple = new Apple(); Fruits objMango = new Mango(); arrFruits.add(objApple); arrFruits.add(objMango);
Removing Element – List.remove()
arrFruits.remove(objApple);
Removing by Index – List.remove()
arrFruits.remove(1);
Index of Element – List.indexOf()
arrFruits.indexOf(objMango);
Index of Element – List.indexOf()
arrFruits.indexOf(objMango);
SubList – List.subList(StartPOS, EndPOS)
List<Fruits> arrNewFruits = arrFruits.subList(0,2);
containsAll – NewList.containsAll(OrgList)
arrNewFruits.containsAll(arrFruits);
set Value at Index
arrNewFruits.set(1, new Orange());
removeAll
arrFruits.removeAll(arrFruits);
addAll
arrFruits.addAll(arrNewFruits);
retainAll – set Intersection Operation
retainAll performs set Interscetion Operation by taking Two ArrayList. It Retains Boolean true if intersection finds element false otherwise.
List<Integer> arrNums1 = new ArrayList<Integer>(); arrNums1.add(1); arrNums1.add(2); arrNums1.add(3); List<Integer> arrNums2 = new ArrayList<Integer>(); arrNums2.add(1); System.out.println(arrNums1.retainAll(arrNums2)); System.out.println(arrNums1);