Lists In Java

A Listis an ordered Collection(sometimes called a sequence). Lists may contain duplicate elements. In addition to the operations inherited from Collection, the List interface includes operations for:

• Positional Access: manipulate elements based on their numerical position in the list.
• Search: search for a specified object in the list and return its numerical position.
• List Iteration: extend Iterator semantics to take advantage of the list's sequential nature.
• Range-view: perform arbitrary range operations on the list.

List Interface

List Implementations

• ArrayList
• Vector
•  LinkedList

 

Comparing List to Vector

ListIterator Interface

Operations on Lists

There are various type of operations that can be performed on lists:

• Collection Operations on Lists -  Simple and Bulk
• Positional Access and Search Operations on List
• Iterating over the List
• Range view operations on lists

Generic Lists in Java
Performance of List implementations in java

Map implementations in java

A number of classes implement the Map interface, including HashMap, TreeMap, LinkedHashMap, WeakHashMap, ConcurrentHashMap, and Properties. The most generally useful class is HashMap.

• java.util.HashMap is implemented with a hash table. Access time is O(1). Entries are unsorted.
  – similar to HashTable but allows null keys and values
  – not thread safe
• java.util.LinkedHashMap is implemented with a hash table. Access time is O(1). Entries are sorted in either entry order or order of last access, which is useful for implementing a LRU (least recently used) caching policy.
• java.util.TreeMap is implemented as a balanced binary tree. Access time is O(log N). Entries are sorted. 
• java.util.HashTable(old classes)
  – updated class from earlier Java versions
  – does not allow null keys or values
  – thread safe
• java.util.WeakHashMap -
  – like HashMap
  – entry is automatically removed from HashMap if no more "ordinary" references to key
• java.util.IdentityHashMap
• java.util.EnumMap
• java.util.Properties

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

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();    

Set tutorial in java

A Set is a Collection that cannot contain duplicate elements. Set models the mathematical set abstraction. The Set interface contains no methods other than those inherited from Collection. It adds the restriction that duplicate elements are prohibited. Set also adds a stronger contract on the behavior of the equals and hashCode operations, allowing Set objects with different implementation types to be compared meaningfully. Two Set objects are equal if they contain the same elements.

 

Set Interfaces

• Set Interface in java
• SortedSet Interface

 

Set Implementations

• LinkedHashSet
  Creating a set that retains the order of insertion
• HashSet
HashSet class in java
Converting ArrayList to HashSet
• TreeSet
  TreeSet class in java – constructors

 

Operations on Sets

• Operating on a set
• Bulk Operations : Operations between the 2 sets in java

 

SortedSet

• SortedSet Interface
• SortedSet Operations
• Standard constructors for SortedSet interface
• Range-view operations on SortedSet interface
• Creating a sorted set

 

How is set implemented internally?

Set and serializations

Sets and synchronization

Iterators returned by set implementation and concurrent modification

When to use which set implementation?

Performance of set interface implementations

 

The SortedSet interface

A SortedSetis a Setthat maintains its elements in ascending order, sorted according to the elements' natural order, or according to a Comparator provided at SortedSet creation time. (Natural order and Comparators are discussed in the previous section, on Object Ordering.) In addition to the normal Set operations, the Set interface provides operations for:

• Range-view: Performs arbitrary range operations on the sorted set.
• Endpoints: Returns the first or last element in the sorted set.
• Comparator access: Returns the Comparator used to sort the set (if any).

The SortedSet interface is shown below:

public interface SortedSet extends Set {
    // Range-view
    SortedSet subSet(Object fromElement, Object toElement);
    SortedSet headSet(Object toElement);
    SortedSet tailSet(Object fromElement);
    // Endpoints
    Object first();
    Object last();
    // Comparator access
    Comparator comparator();
}

SortedSet Operations 

Standard Constructors 

Range-view Operations on SortedSet

Example – Creating a SortedSet

The List interface

A List is an ordered Collection (sometimes called a sequence).(Sets are unordered collections)
Unlike sets, Lists may contain duplicate elements. In addition to the operations inherited from Collection, the List interface includes operations for:

• Positional Access: manipulate elements based on their numerical position in the list.
• Search: search for a specified object in the list and return its numerical position.
• List Iteration: extend Iterator semantics to take advantage of the list's sequential nature.
• Range-view: perform arbitrary range operations on the list.

The List interface is shown below:

public interface List extends Collection {
    // Positional Access
    Object get(int index);
    Object set(int index, Object element);
            // Optional
    void add(int index, Object element);
              // Optional
    Object remove(int index);
                         // Optional
    abstract boolean addAll(int index, Collection c);
     // Optional    // Search
    int indexOf(Object o);
    int lastIndexOf(Object o);
    // Iteration
    ListIterator listIterator();
    ListIterator listIterator(int index);
    // Range-view
    List subList(int from, int to);
}

Comparing List to Vector

ListIterator Interface

List Implementations in java

Operations on Lists

Generic Lists in Java

Performance of List implementations in java

Maps in java collections

There is Map interface in java, but also there are other interfaces like SortedMap and Map.Entry interfaces. This tutorial will cover following:

Introduction to Maps in java

Map interfaces

• Map implemented by HashMap and TreeMap
  Map Interface methods
• SortedMap implemented by TreeMap.
  SortedMap interface methods
• Map.Entry which describes access methods to the key-value pairs.
  Map.Entry interface methods

Classes Implementing Map

• HashMap in java
• TreeMap in java
• HashTable in java
• IdentityHashMap
• WeakHashMap
• LinkedHashMap
• Properties class

 

Iterating over a Map

Comparison of maps to Hashtable

Basic Operations on Maps

Bulk Operations on Maps

Collection Views for Maps

Fancy Uses of Collection-Views: Map Algebra

Multimaps

Examples
Creating a weak hashmap
Creating a hashmap in java
Creating a Map That Retains Order-of-Insertion
Creating type-specific map

Vector Tutorial in java

Introduction to Vectors in java

Operating on Vector in java – Common operations like create,add, Delete

How To Iterate over the elements of a Vector

Common Vector Methods

Insuring use of the new Vector API Methods

Replacements for old methods

 

ArrayList in java

ArrayList – Basic methods and constructors

When to use Arrays or ArrayList?

Automatic expansion of ArrayList

Objects only limitation on Collections in java

To get successive elements from an ArrayList

Sorting an ArrayList in java

Vector vs ArrayList

Convert Array to ArrayList and vice-versa in java

How to convert ArrayList to HashSet in java?

 

Examples
Alphabetize
ArrayList example 2
Operating on list
Sorting a list