Collection Operations on Lists–Simple and Bulk

Create the lists

List list1 = new ArrayList(); 
List list2 = new ArrayList(); 

Add the elements

// Add elements to the lists ...
list1.add("Hanuman");

Bulk Add
Copy all the elements from list2 to list1 (list1 += list2). list1 becomes the union of list1 and list2

list1.addAll(list2); 

Bulk Remove
Remove all the elements in list1 from list2 (list1 -= list2). list1 becomes the asymmetric difference of list1 and list2

list1.removeAll(list2); 

Intersection of Lists
Get the intersection of list1 and list2. list1 becomes the intersection of list1 and list2

list1.retainAll(list2); 

Remove all elements from a list

list1.clear(); 

Truncate the list

int newSize = 2;
list1.subList(newSize, list1.size()).clear(); 

LinkedList in java

Introduction

LinkedList also implements List. But unlike its brothers like ArrayList and Vector, it doesn't use arrays as their underlying implementation. In a LinkedList each element has a pointer to the element before it and to the element following it. Because of this LinkedLists and ArrayLists will perform differently from processing time and memory usage standpoints. So it gives kind of sequential access and not random access. See the post – difference between iterator and index access for more.

I am not going to get into all the differences in performance here except to say a LinkedList can add elements very quickly to its beginning or middle, and there is no capacity to manage. Ultimately performance really depends on what you are doing with your collection. When performance is a concern you are best off testing each side by side and seeing which is better for your particular application.

Common methods of LinkedList

A simple example on LinkedList

User-defined implementation of linked list in java

Further you can implement your on linkedList in java.

SimpleSinglyLinkedList implemented in java

SimpleDoublyLinkedList implemented in java

Performance of List implementations in java

Common methods of LinkedList in java

Often LinkedLists are selected for use because of the methods in this class. LinkedList has most of the common methods ArrayList has (add(), get(), set(), remove(), size(), etc) plus a number of new methods that can be very convenient:

addFirst(object) & addLast(object): adds the object to the beginning or end of the LinkedList.

peek(): This just returns the first element of the LinkedList. Appreciate this method name: The language architect here seemed to be feeling cutesy, which you don't see often.

poll():This returns and removes the first element of the LinkedList. Also this will return null if the LinkedListis empty.

offer(): Attempts to add object to the end of the LinkedLists, and returns a Boolean based on weather it was added or not.

removeFirst() & removeLast(): Returns and removes the last element.

Operations on Lists in java

Creating a list:

List listA = new ArrayList();

Adding Elements

To add elements to a List you call its add() method. This method is inherited from the Collection interface. Here are a few examples:

listA.add("element 1");
listA.add("element 2");
listA.add("element 3");

Adding element at particular index, like index 0 here:

listA.add(0, "element 0");

Accessing elements:

This is done by get method, which gets the element from particular index:

String element0 = listA.get(0);

Removing elements:

You can remove elements in two ways:

1. remove(Object element)
   
2. remove(int index)

remove(Object element) removes that element in the list, if it is present. All subsequent elements in the list are then moved up in the list. Their index thus decreases by 1.

remove(int index) removes the element at the given index. All subsequent elements in the list are then moved up in the list. Their index thus decreases by 1.

 

Iterating over elements:

This can be done in many ways, like using iterator, foreach style for loop, simple for loop with get method :

//access via Iterator
Iterator iterator = listA.iterator();
while(iterator.hasNext(){
  String element = (String) iterator.next();
}


//access via new for-loop i.e. foreach style
for(Object object : listA) {
    String element = (String) object;
}

//old style for loop
for(int i = 0;i<listA.size();i++) {
    String element = listA.get(i);
}

List Implementations in java

Being a Collection subtype all methods in the Collection interface are also available in the List interface.

Since List is an interface you need to instantiate a concrete implementation of the interface in order to use it. You can choose between the following List implementations in the Java Collections API:

 

• java.util.Vector
  Vectors(Java 1.1) (Click on link to see tutorial on it)
  --uses array to implement list
• java.util.ArrayList
  ArrayList (Click on link to see tutorial on it)
  --uses array to implement List
  – not thread-safe, otherwise same as Vector
• java.util.LinkedList
  LinkedList  (Click on link to see tutorial on it)
  --List interface implemented as a doubly-linked list
  – access to elements is not constant time
  – better performance for frequent add/remove operations in middle of List
• java.util.Stack
  Stack

There are also List implementations in the java.util.concurrent package, which we will see later.

Here are a few examples of how to create a List instance:

List listA = new ArrayList();
List listB = new LinkedList();
List listC = new Vector();
List listD = new Stack();    

Performance of List interface implementations

LinkedList

- Performance of get and remove methods is linear time [ Big O Notation is O(n) ] - Performance of add and Iterator.remove methods is constant-time [ Big O Notation is O(1) ]

ArrayList

- The size, isEmpty, get, set, iterator, and listIterator operations run in constant time. [ Big O Notation is O(1) ]
- The add operation runs in amortized constant time [ Big O Notation is O(1) ] , but in worst case (since the array must be resized and copied) adding n elements requires linear time [ Big O Notation is O(n) ]
- Performance of remove method is linear time [ Big O Notation is O(n) ]
- All of the other operations run in linear time [ Big O Notation is O(n) ]. The constant factor is low compared to that for the LinkedList implementation.