Java/Collections Data Structure/List

A class that wraps an array with a List interface.

   <source lang="java">
  

/*

* Licensed to the Apache Software Foundation (ASF) under one
* or more contributor license agreements.  See the NOTICE file
* distributed with this work for additional information
* regarding copyright ownership.  The ASF licenses this file
* to you under the Apache License, Version 2.0 (the
* "License"); you may not use this file except in compliance
* with the License.  You may obtain a copy of the License at
*
*   http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing,
* software distributed under the License is distributed on an
* "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
* KIND, either express or implied.  See the License for the
* specific language governing permissions and limitations
* under the License.
*/

import java.lang.reflect.Array; import java.util.AbstractList; /**

* A class that wraps an array with a List interface.
*
* @author Chris Schultz <chris@christopherschultz.net$gt;
* @version $Revision: 685685 $ $Date: 2006-04-14 19:40:41 $
* @since 1.6
*/

public class ArrayListWrapper extends AbstractList {

   private Object array;
   public ArrayListWrapper(Object array)
   {
       this.array = array;
   }
   public Object get(int index)
   {
       return Array.get(array, index);
   }
   public Object set(int index, Object element)
   {
       Object old = get(index);
       Array.set(array, index, element);
       return old;
   }
   public int size()
   {
       return Array.getLength(array);
   }

}

 </source>
   
  
 
  

Add to end Performance compare: LinkList and ArrayList

   <source lang="java">
    

/* time for LinkedList = 501 time for ArrayList = 126

• /

import java.util.ArrayList; import java.util.LinkedList; import java.util.List; public class ListDemo {

 // number of objects to add to list
 static final int SIZE = 1000000;
 static long timeList(List list) {
   long start = System.currentTimeMillis();
   Object obj = new Object();
   for (int i = 0; i < SIZE; i++) {
     // add object to the rear of the list
     list.add(obj);
   }
   return System.currentTimeMillis() - start;
 }
 public static void main(String args[]) {
   // do timing for LinkedList
   System.out.println("time for LinkedList = " + timeList(new LinkedList()));
   // do timing for ArrayList
   System.out.println("time for ArrayList = " + timeList(new ArrayList()));
 }

}

 </source>
   
  
 
  

Add to start Performance compare: LinkList and ArrayList

   <source lang="java">
    

/* time for LinkedList = 62 time for ArrayList = 7488

• /

import java.util.ArrayList; import java.util.LinkedList; import java.util.List; public class ListDemoHead {

 static final int SIZE = 100000;
 static long timeList(List list) {
   long start = System.currentTimeMillis();
   Object obj = new Object();
   for (int i = 0; i < SIZE; i++) {
     // add object to the head of the list
     list.add(0, obj);
   }
   return System.currentTimeMillis() - start;
 }
 public static void main(String args[]) {
   // do timing for LinkedList
   System.out.println("time for LinkedList = " + timeList(new LinkedList()));
   // do timing for ArrayList
   System.out.println("time for ArrayList = " + timeList(new ArrayList()));
 }

}

 </source>
   
  
 
  

Bidirectional Traversal with ListIterator

   <source lang="java">
    

import java.util.ArrayList; import java.util.Iterator; import java.util.List; import java.util.ListIterator; public class MovingPlanets {

 public static void main(String args[]) {
   String names[] = { "Mercury", "Venus", "Earth", "Mars", "Jupiter",
       "Saturn", "Uranus", "Neptune", "Pluto" };
   List planets = new ArrayList();
   for (int i = 0, n = names.length; i < n; i++) {
     planets.add(names[i]);
   }
   ListIterator lit = planets.listIterator();
   String s;
   lit.next();
   lit.next();
   s = (String) lit.next();
   lit.remove();
   lit.next();
   lit.next();
   lit.next();
   lit.add(s);
   lit.next(); // Gets back just added
   lit.previous();
   lit.previous();
   s = (String) lit.previous();
   lit.remove();
   lit.next();
   lit.next();
   lit.add(s);
   Iterator it = planets.iterator();
   while (it.hasNext()) {
     System.out.println(it.next());
   }
 }

}

 </source>
   
  
 
  

Build your own Linked List class

   <source lang="java">
    

public class Main {

 public static void main(String[] args) {
   LinkedList theList = new LinkedList();
   LinkedListIterator theItr;
   theItr = theList.zeroth();
   printList(theList);
   for (int i = 0; i < 10; i++) {
     theList.insert(new Integer(i), theItr);
     printList(theList);
     theItr.advance();
   }
   System.out.println("Size was: " + listSize(theList));
  }
 public static int listSize(LinkedList theList) {
   LinkedListIterator itr;
   int size = 0;
   for (itr = theList.first(); itr.isValid(); itr.advance())
     size++;
   return size;
 }
 public static void printList(LinkedList theList) {
   if (theList.isEmpty())
     System.out.print("Empty list");
   else {
     LinkedListIterator itr = theList.first();
     for (; itr.isValid(); itr.advance())
       System.out.print(itr.retrieve() + " ");
   }
   System.out.println();
 }

} class LinkedList {

 public LinkedList() {
   header = new ListNode(null);
 }
 public boolean isEmpty() {
   return header.next == null;
 }
 public void makeEmpty() {
   header.next = null;
 }
 public LinkedListIterator zeroth() {
   return new LinkedListIterator(header);
 }
 public LinkedListIterator first() {
   return new LinkedListIterator(header.next);
 }
 public void insert(Object x, LinkedListIterator p) {
   if (p != null && p.current != null)
     p.current.next = new ListNode(x, p.current.next);
 }
 public LinkedListIterator find(Object x) {
   ListNode itr = header.next;
   while (itr != null && !itr.element.equals(x))
     itr = itr.next;
   return new LinkedListIterator(itr);
 }
 public LinkedListIterator findPrevious(Object x) {
   ListNode itr = header;
   while (itr.next != null && !itr.next.element.equals(x))
     itr = itr.next;
   return new LinkedListIterator(itr);
 }
 public void remove(Object x) {
   LinkedListIterator p = findPrevious(x);
   if (p.current.next != null)
     p.current.next = p.current.next.next; // Bypass deleted node
 }
 private ListNode header;

} class LinkedListIterator {

 LinkedListIterator(ListNode theNode) {
   current = theNode;
 }
 public boolean isValid() {
   return current != null;
 }
 public Object retrieve() {
   return isValid() ? current.element : null;
 }
 public void advance() {
   if (isValid())
     current = current.next;
 }
 ListNode current;

} class ListNode {

 public ListNode(Object theElement) {
   this(theElement, null);
 }
 public ListNode(Object theElement, ListNode n) {
   element = theElement;
   next = n;
 }
 public Object element;
 public ListNode next;

}

 </source>
   
  
 
  

Convert a List to a Set

   <source lang="java">
   

import java.util.ArrayList; import java.util.HashSet; import java.util.List; import java.util.Set; public class Main {

 public static void main(String[] args) {
   List<String> myList = new ArrayList<String>();
   myList.add("A");
   myList.add("B");
   myList.add("C");
   myList.add("D");
   Set<String> mySet = new HashSet<String>(myList);
   for (Object theFruit : mySet)
     System.out.println(theFruit);
 }

} /* D A B C

• /

 </source>
   
  
 
  

Convert array to list and sort

   <source lang="java">
    

import java.util.Arrays; import java.util.Collections; import java.util.List; public class Sort {

 public static void main(String args[]) {
   String[] strArray = new String[] { "Java", "Source", "And", "and",
       "Support", "jexp" };
   List l = Arrays.asList(strArray);
   Collections.sort(l);
   System.out.println(l);
 }

}

 </source>
   
  
 
  

Convert collection into array

   <source lang="java">
  

import java.util.ArrayList; import java.util.List; public class Main {

 public static void main(String[] args) {
   List<String> list = new ArrayList<String>();
   list.add("A");
   list.add("B");
   list.add("C");
   list.add("D");
   Object[] array = list.toArray();
   for (int i = 0; i < array.length; i++) {
     System.out.println(array[i].toString());
   }
 }

}

 </source>
   
  
 
  

Convert LinkedList to array

   <source lang="java">
  

import java.util.LinkedList; import java.util.List; public class Main {

 public static void main(String[] args) {
   List<String> list = new LinkedList<String>();
   list.add("A");
   list.add("B");
   list.add("C");
   list.add("D");
   String[] colors = new String[list.size()];
   list.toArray(colors);
   for (int i = 0; i < colors.length; i++) {
     System.out.println("color = " + colors[i]);
   }
 }

}

 </source>
   
  
 
  

Convert Set into List

   <source lang="java">
   

import java.util.ArrayList; import java.util.Date; import java.util.HashSet; import java.util.List; import java.util.Set; public class Main {

 public static void main(String[] args) {
   Set<Object> set = new HashSet<Object>();
   set.add("A");
   set.add(new Long(10));
   set.add(new Date());
   List<Object> list = new ArrayList<Object>(set);
   for (int i = 0; i < list.size(); i++) {
     Object o = list.get(i);
     System.out.println("Object = " + o);
   }
 }

}

 </source>
   
  
 
  

Generic to list

   <source lang="java">
  

/*

 Milyn - Copyright (C) 2006
 This library is free software; you can redistribute it and/or
 modify it under the terms of the GNU Lesser General Public
 License (version 2.1) as published by the Free Software
 Foundation.
 This library is distributed in the hope that it will be useful,
 but WITHOUT ANY WARRANTY; without even the implied warranty of
 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
 See the GNU Lesser General Public License for more details:
 http://www.gnu.org/licenses/lgpl.txt

• /

import java.util.*; /**

* Collections Utilities.
* 
* @author 
*/

public class CollectionsUtil {

   /**
    * Private constructor.
    */
   private CollectionsUtil() {
   }
   /**
    * Create an Object {@link Set} from the supplied objects.
    * @param objects The objects to be added to the set.
    * @return The {@link Set}.
    */
   public static <T> Set<T> toSet(T... objects) {
       Set<T> theSet = new HashSet<T>();
       addToCollection(theSet, objects);
       return theSet;
   }
   /**
    * Create an Object {@link List} from the supplied objects.
    * @param objects The objects to be added to the list.
    * @return The {@link List}.
    */
   public static <T> List<T> toList(T... objects) {
       List<T> theSet = new ArrayList<T>();
       addToCollection(theSet, objects);
       return theSet;
   }
   private static <T> void addToCollection(Collection<T> theCollection, T... objects) {
       for(T object : objects) {
           theCollection.add(object);
       }
   }

}

 </source>
   
  
 
  

Helper method for creating list

   <source lang="java">
  

/**

* Copyright (C) 2007 Google Inc.
*
* This library is free software; you can redistribute it and/or
* modify it under the terms of the GNU Lesser General Public
* License as published by the Free Software Foundation; either
* version 2.1 of the License, or (at your option) any later version.
* This library is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
* Lesser General Public License for more details.
* You should have received a copy of the GNU Lesser General Public
* License along with this library; if not, write to the Free Software
* Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA
*/

import java.util.ArrayList; import java.util.Collections; import java.util.LinkedList; import java.util.List; /**

* Helper methods related to {@link List}s.
*
* @author maxr@google.ru (Max Ross)
*/

public class Lists {

 private Lists() { }
 /**
  * Construct a new {@link ArrayList}, taking advantage of type inference to
  * avoid specifying the type on the rhs.
  */
 public static <E> ArrayList<E> newArrayList() {
   return new ArrayList<E>();
 }
 /**
  * Construct a new {@link ArrayList} with the specified capacity, taking advantage of type inference to
  * avoid specifying the type on the rhs.
  */
 public static <E> ArrayList<E> newArrayListWithCapacity(int initialCapacity) {
   return new ArrayList<E>(initialCapacity);
 }
 /**
  * Construct a new {@link ArrayList} with the provided elements, taking advantage of type inference to
  * avoid specifying the type on the rhs.
  */
 public static <E> ArrayList<E> newArrayList(E... elements) {
   ArrayList<E> set = newArrayList();
   Collections.addAll(set, elements);
   return set;
 }
 /**
  * Construct a new {@link ArrayList} with the contents of the provided {@link Iterable}, taking advantage of type inference to
  * avoid specifying the type on the rhs.
  */
 public static <E> ArrayList<E> newArrayList(Iterable<? extends E> elements) {
   ArrayList<E> list = newArrayList();
   for(E e : elements) {
     list.add(e);
   }
   return list;
 }
 /**
  * Construct a new {@link LinkedList}, taking advantage of type inference to
  * avoid specifying the type on the rhs.
  */
 public static <E> LinkedList<E> newLinkedList() {
   return new LinkedList<E>();
 }

}

 </source>
   
  
 
  

If a List contains an item

   <source lang="java">
  

import java.util.ArrayList; import java.util.List; public class Main {

 public static void main(String[] args) {
   List list = new ArrayList();
   list.add("Item 1");
   list.add("Item 2");
   if (list.contains("Item 1")) {
     System.out.println("True");
   } else {
     System.out.println("False");
   }
 }

}

 </source>
   
  
 
  

Int list

   <source lang="java">
    

/*

* Copyright (c) 2000 David Flanagan.  All rights reserved.
* This code is from the book Java Examples in a Nutshell, 2nd Edition.
* It is provided AS-IS, WITHOUT ANY WARRANTY either expressed or implied.
* You may study, use, and modify it for any non-commercial purpose.
* You may distribute it non-commercially as long as you retain this notice.
* For a commercial use license, or to purchase the book (recommended),
* visit http://www.davidflanagan.ru/javaexamples2.
*/

import java.io.File; import java.io.FileInputStream; import java.io.FileOutputStream; import java.io.IOException; import java.io.ObjectInputStream; import java.io.ObjectOutputStream; import java.io.PipedInputStream; import java.io.PipedOutputStream; import java.io.Serializable;

/**

* A simple class that implements a growable array of ints, and knows how to
* serialize itself as efficiently as a non-growable array.
*/

public class IntList implements Serializable {

 protected int[] data = new int[8]; // An array to store the numbers.
 protected transient int size = 0; // Index of next unused element of array
 /** Return an element of the array */
 public int get(int index) throws ArrayIndexOutOfBoundsException {
   if (index >= size)
     throw new ArrayIndexOutOfBoundsException(index);
   else
     return data[index];
 }
 /** Add an int to the array, growing the array if necessary */
 public void add(int x) {
   if (data.length == size)
     resize(data.length * 2); // Grow array if needed.
   data[size++] = x; // Store the int in it.
 }
 /** An internal method to change the allocated size of the array */
 protected void resize(int newsize) {
   int[] newdata = new int[newsize]; // Create a new array
   System.arraycopy(data, 0, newdata, 0, size); // Copy array elements.
   data = newdata; // Replace old array
 }
 /** Get rid of unused array elements before serializing the array */
 private void writeObject(ObjectOutputStream out) throws IOException {
   if (data.length > size)
     resize(size); // Compact the array.
   out.defaultWriteObject(); // Then write it out normally.
 }
 /** Compute the transient size field after deserializing the array */
 private void readObject(ObjectInputStream in) throws IOException,
     ClassNotFoundException {
   in.defaultReadObject(); // Read the array normally.
   size = data.length; // Restore the transient field.
 }
 /**
  * Does this object contain the same values as the object o? We override
  * this Object method so we can test the class.
  */
 public boolean equals(Object o) {
   if (!(o instanceof IntList))
     return false;
   IntList that = (IntList) o;
   if (this.size != that.size)
     return false;
   for (int i = 0; i < this.size; i++)
     if (this.data[i] != that.data[i])
       return false;
   return true;
 }
 /** A main() method to prove that it works */
 public static void main(String[] args) throws Exception {
   IntList list = new IntList();
   for (int i = 0; i < 100; i++)
     list.add((int) (Math.random() * 40000));
   IntList copy = (IntList) Serializer.deepclone(list);
   if (list.equals(copy))
     System.out.println("equal copies");
   Serializer.store(list, new File("intlist.ser"));
 }

}

/*

* Copyright (c) 2000 David Flanagan.  All rights reserved.
* This code is from the book Java Examples in a Nutshell, 2nd Edition.
* It is provided AS-IS, WITHOUT ANY WARRANTY either expressed or implied.
* You may study, use, and modify it for any non-commercial purpose.
* You may distribute it non-commercially as long as you retain this notice.
* For a commercial use license, or to purchase the book (recommended),
* visit http://www.davidflanagan.ru/javaexamples2.
*/

/**

* This class defines utility routines that use Java serialization.
*/

class Serializer {

 /**
  * Serialize the object o (and any Serializable objects it refers to) and
  * store its serialized state in File f.
  */
 static void store(Serializable o, File f) throws IOException {
   ObjectOutputStream out = // The class for serialization
   new ObjectOutputStream(new FileOutputStream(f));
   out.writeObject(o); // This method serializes an object graph
   out.close();
 }
 /**
  * Deserialize the contents of File f and return the resulting object
  */
 static Object load(File f) throws IOException, ClassNotFoundException {
   ObjectInputStream in = // The class for de-serialization
   new ObjectInputStream(new FileInputStream(f));
   return in.readObject(); // This method deserializes an object graph
 }
 /**
  * Use object serialization to make a "deep clone" of the object o. This
  * method serializes o and all objects it refers to, and then deserializes
  * that graph of objects, which means that everything is copied. This
  * differs from the clone() method of an object which is usually implemented
  * to produce a "shallow" clone that copies references to other objects,
  * instead of copying all referenced objects.
  */
 static Object deepclone(final Serializable o) throws IOException,
     ClassNotFoundException {
   // Create a connected pair of "piped" streams.
   // We"ll write bytes to one, and them from the other one.
   final PipedOutputStream pipeout = new PipedOutputStream();
   PipedInputStream pipein = new PipedInputStream(pipeout);
   // Now define an independent thread to serialize the object and write
   // its bytes to the PipedOutputStream
   Thread writer = new Thread() {
     public void run() {
       ObjectOutputStream out = null;
       try {
         out = new ObjectOutputStream(pipeout);
         out.writeObject(o);
       } catch (IOException e) {
       } finally {
         try {
           out.close();
         } catch (Exception e) {
         }
       }
     }
   };
   writer.start(); // Make the thread start serializing and writing
   // Meanwhile, in this thread, read and deserialize from the piped
   // input stream. The resulting object is a deep clone of the original.
   ObjectInputStream in = new ObjectInputStream(pipein);
   return in.readObject();
 }
 /**
  * This is a simple serializable data structure that we use below for
  * testing the methods above
  */
 public static class DataStructure implements Serializable {
   String message;
   int[] data;
   DataStructure other;
   public String toString() {
     String s = message;
     for (int i = 0; i < data.length; i++)
       s += " " + data[i];
     if (other != null)
       s += "\n\t" + other.toString();
     return s;
   }
 }
 /** This class defines a main() method for testing */
 public static class Test {
   public static void main(String[] args) throws IOException,
       ClassNotFoundException {
     // Create a simple object graph
     DataStructure ds = new DataStructure();
     ds.message = "hello world";
     ds.data = new int[] { 1, 2, 3, 4 };
     ds.other = new DataStructure();
     ds.other.message = "nested structure";
     ds.other.data = new int[] { 9, 8, 7 };
     // Display the original object graph
     System.out.println("Original data structure: " + ds);
     // Output it to a file
     File f = new File("datastructure.ser");
     System.out.println("Storing to a file...");
     Serializer.store(ds, f);
     // Read it back from the file, and display it again
     ds = (DataStructure) Serializer.load(f);
     System.out.println("Read from the file: " + ds);
     // Create a deep clone and display that. After making the copy
     // modify the original to prove that the clone is "deep".
     DataStructure ds2 = (DataStructure) Serializer.deepclone(ds);
     ds.other.message = null;
     ds.other.data = null; // Change original
     System.out.println("Deep clone: " + ds2);
   }
 }

}

 </source>
   
  
 
  

Linked List example

   <source lang="java">
    

/*

* Copyright (c) 2000 David Flanagan.  All rights reserved.
* This code is from the book Java Examples in a Nutshell, 2nd Edition.
* It is provided AS-IS, WITHOUT ANY WARRANTY either expressed or implied.
* You may study, use, and modify it for any non-commercial purpose.
* You may distribute it non-commercially as long as you retain this notice.
* For a commercial use license, or to purchase the book (recommended),
* visit http://www.davidflanagan.ru/javaexamples2.
*/

/**

* This class implements a linked list that can contain any type of object that
* implements the nested Linkable interface. Note that the methods are all
* synchronized, so that it can safely be used by multiple threads at the same
* time.
*/

public class LinkedList {

 /**
  * This interface defines the methods required by any object that can be
  * linked into a linked list.
  */
 public interface Linkable {
   public Linkable getNext(); // Returns the next element in the list
   public void setNext(Linkable node); // Sets the next element in the list
 }
 // This class has a default constructor: public LinkedList() {}
 /** This is the only field of the class. It holds the head of the list */
 Linkable head;
 /** Return the first node in the list */
 public synchronized Linkable getHead() {
   return head;
 }
 /** Insert a node at the beginning of the list */
 public synchronized void insertAtHead(Linkable node) {
   node.setNext(head);
   head = node;
 }
 /** Insert a node at the end of the list */
 public synchronized void insertAtTail(Linkable node) {
   if (head == null)
     head = node;
   else {
     Linkable p, q;
     for (p = head; (q = p.getNext()) != null; p = q)
       /* no body */;
     p.setNext(node);
   }
 }
 /** Remove and return the node at the head of the list */
 public synchronized Linkable removeFromHead() {
   Linkable node = head;
   if (node != null) {
     head = node.getNext();
     node.setNext(null);
   }
   return node;
 }
 /** Remove and return the node at the end of the list */
 public synchronized Linkable removeFromTail() {
   if (head == null)
     return null;
   Linkable p = head, q = null, next = head.getNext();
   if (next == null) {
     head = null;
     return p;
   }
   while ((next = p.getNext()) != null) {
     q = p;
     p = next;
   }
   q.setNext(null);
   return p;
 }
 /**
  * Remove a node matching the specified node from the list. Use equals()
  * instead of == to test for a matched node.
  */
 public synchronized void remove(Linkable node) {
   if (head == null)
     return;
   if (node.equals(head)) {
     head = head.getNext();
     return;
   }
   Linkable p = head, q = null;
   while ((q = p.getNext()) != null) {
     if (node.equals(q)) {
       p.setNext(q.getNext());
       return;
     }
     p = q;
   }
 }
 /**
  * This is a test class that implements the Linkable interface
  */
 static class LinkableInteger implements Linkable {
   int i; // The data contained in the node
   Linkable next; // A reference to the next node in the list
   public LinkableInteger(int i) {
     this.i = i;
   } // Constructor
   public Linkable getNext() {
     return next;
   } // Part of Linkable
   public void setNext(Linkable node) {
     next = node;
   } // Linkable
   public String toString() {
     return i + "";
   } // For easy printing
   public boolean equals(Object o) { // For comparison
     if (this == o)
       return true;
     if (!(o instanceof LinkableInteger))
       return false;
     if (((LinkableInteger) o).i == this.i)
       return true;
     return false;
   }
 }
 /**
  * The test program. Insert some nodes, remove some nodes, then print
  * out all elements in the list. It should print out the numbers 4, 6,
  * 3, 1, and 5
  */
 public static void main(String[] args) {
   LinkedList ll = new LinkedList(); // Create a list
   ll.insertAtHead(new LinkableInteger(1)); // Insert some stuff
   ll.insertAtHead(new LinkableInteger(2));
   ll.insertAtHead(new LinkableInteger(3));
   ll.insertAtHead(new LinkableInteger(4));
   ll.insertAtTail(new LinkableInteger(5));
   ll.insertAtTail(new LinkableInteger(6));
   System.out.println(ll.removeFromHead()); // Remove and print a node
   System.out.println(ll.removeFromTail()); // Remove and print again
   ll.remove(new LinkableInteger(2)); // Remove another one
   // Now print out the contents of the list.
   for (Linkable l = ll.getHead(); l != null; l = l.getNext())
     System.out.println(l);
 }

}

 </source>
   
  
 
  

List containing other lists

   <source lang="java">
  

/*

* $Id: ListOfLists.java,v 1.1.1.1 2005/04/07 18:36:24 pocho Exp $
*/

import java.util.AbstractList; import java.util.ArrayList; import java.util.Collection; import java.util.Iterator; import java.util.List; import java.util.ListIterator; /**

* Creates list containing other lists, access another list"s elements as it would belong
* to this list. 
* 
* @version $Name:  $ - $Revision: 1.1.1.1 $ - $Date: 2005/04/07 18:36:24 $
* TODO Test
*/

public class ListOfLists extends AbstractList {

 private Collection lists = new ArrayList();
 public ListOfLists(Collection c) {
   Iterator it = c.iterator();
   Object o;
   while (it.hasNext()) {
     o = it.next();
     if (o instanceof List)
       lists.add(o);
     else if (o != null)
       throw new UnsupportedOperationException(this.getClass().getName() +
                                               " class supports only instances "+
                                               "of java.util.List interface");
   }
 }
 public int size() {
   Iterator it = lists.iterator();
   int size = 0;
   Object o;
   while (it.hasNext()) {
     o = it.next();
     if (o != null)
       size += ((List) o).size();
   }
   return size;
 }
 public Object get(int index) {
   int size = size();
   if (index < 0)
     throw new IndexOutOfBoundsException("index: " + index +"; size: " + size);
   Iterator it = lists.iterator();
   while (it.hasNext()) {
     List list = (List) it.next();
     if (index < list.size()) {
       return list.get(index);
     }
     else
       index -= list.size();
   }
   // if value has not been returned yet - IndexOutOfBoundsException is thrown
   throw new IndexOutOfBoundsException("index: " + index +"; size: " + size);
 }
 /**
  * Replaces the element at the specified position in underlying list with the
  * specified element.
  *
  * @param index index of element to replace.
  * @param element element to be stored at the specified position.
  * @return the element previously at the specified position.
  */
 public Object set(int index, Object element) {
   int size = size();
   if (index < 0)
     throw new IndexOutOfBoundsException("index: " + index +"; size: " + size);
   Iterator it = lists.iterator();
   while (it.hasNext()) {
     List list = (List) it.next();
     if (index < list.size()) {
       return list.set(index, element);
     }
     else
       index -= list.size();
   }
   // if value has not been returned yet - IndexOutOfBoundsException is thrown
   throw new IndexOutOfBoundsException("index: " + index +"; size: " + size);
 }
 public int indexOf(Object o) {
   ListIterator e = listIterator();
   if (o==null) {
     while (e.hasNext()) {
       if (e.next() == null)
         return e.previousIndex();
     }
   }
   else {
     Object el;
     while (e.hasNext()) {
       el = e.next();
       if (el.equals(o))
         return e.previousIndex();
     }
   }
   return -1;
 }
 public int lastIndexOf(Object o) {
   ListIterator e = listIterator(size());
   if (o==null) {
     while (e.hasPrevious()) {
       if (e.previous() == null)
         return e.nextIndex();
     }
   } else {
     Object el;
     while (e.hasPrevious()) {
       el = e.previous();
       if (el != null && el.equals(o))
         return e.nextIndex();
     }
   }
   return -1;
 }

}

 </source>
   
  
 
  

List implementation with lazy array construction and modification tracking.

   <source lang="java">
  

/*

* Copyright (c) 2006-2009, Dennis M. Sosnoski All rights reserved.
* 
* Redistribution and use in source and binary forms, with or without modification, are permitted provided that the
* following conditions are met:
* 
* Redistributions of source code must retain the above copyright notice, this list of conditions and the following
* disclaimer. Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the
* following disclaimer in the documentation and/or other materials provided with the distribution. Neither the name of
* JiBX nor the names of its contributors may be used to endorse or promote products derived from this software without
* specific prior written permission.
* 
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
* INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
* DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
* SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
* SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
* WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
* OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/

import java.util.AbstractList; import java.util.Iterator; /**

* List implementation with lazy array construction and modification tracking. The lazy array construction is a minor
* optimization, to save the added overhead of a backing array for lists which are frequently empty. The modification
* tracking feature supports filtered list construction with result caching.
* 
* @author Dennis M. Sosnoski
*/

public class LazyList extends AbstractList {

   /** Singleton iterator for empty collection. */
   public static final Iterator EMPTY_ITERATOR = new Iterator() {
       
       public boolean hasNext() {
           return false;
       }
       
       public Object next() {
           throw new IllegalStateException("Internal error - no next");
       }
       
       public void remove() {
           throw new IllegalStateException("Internal error - nothing to remove");
       }
       
   };
   
   /** Unmodifiable empty list instance. */
   public static final LazyList EMPTY_LIST = new LazyList() {
       
       public void add(int index, Object element) {
           throw new UnsupportedOperationException("Internal error: Unmodifiable list");
       }
       
       public Object remove(int index) {
           throw new UnsupportedOperationException("Internal error: Unmodifiable list");
       }
       
       protected void removeRange(int from, int to) {
           throw new UnsupportedOperationException("Internal error: Unmodifiable list");
       }
   };
   
   /** Number of items currently present in list. */
   private int m_size;
   
   /** Maximum number of items allowed before resizing. */
   private int m_limit;
   
   /** Backing array (lazy instantiation, null if not used). */
   private Object[] m_array;
   
   /**
    * Make sure space is available for adding to the list. This grows the size of the backing array, if necessary.
    * 
    * @param count
    */
   private void makeSpace(int count) {
       if (m_limit - m_size < count) {
           Object[] copy;
           if (m_array == null) {
               copy = new Object[count + 4];
           } else {
               copy = new Object[m_size * 2 + count];
               System.arraycopy(m_array, 0, copy, 0, m_size);
           }
           m_array = copy;
           m_limit = copy.length;
       }
   }
   
   /*
    * (non-Javadoc)
    * 
    * @see java.util.AbstractList#get(int)
    */
   public Object get(int index) {
       if (index >= 0 && index < m_size) {
           return m_array[index];
       } else {
           throw new IndexOutOfBoundsException("Index " + index + " is out of valid range 0-" + (m_size - 1));
       }
   }
   
   /*
    * (non-Javadoc)
    * 
    * @see java.util.AbstractCollection#size()
    */
   public int size() {
       return m_size;
   }
   
   /*
    * (non-Javadoc)
    * 
    * @see java.util.AbstractList#add(int, java.lang.Object)
    */
   public void add(int index, Object element) {
       if (index >= 0 && index <= m_size) {
           makeSpace(1);
           if (index < m_size) {
               System.arraycopy(m_array, index, m_array, index + 1, m_size - index);
           }
           m_array[index] = element;
           m_size++;
           modCount++;
       } else {
           throw new IndexOutOfBoundsException("Index " + index + " is out of valid range 0-" + m_size);
       }
   }
   
   /*
    * (non-Javadoc)
    * 
    * @see java.util.AbstractList#iterator()
    */
   public Iterator iterator() {
       if (m_size == 0) {
           return EMPTY_ITERATOR;
       } else {
           return super.iterator();
       }
   }
   
   /*
    * (non-Javadoc)
    * 
    * @see java.util.AbstractList#remove(int)
    */
   public Object remove(int index) {
       if (index >= 0 && index < m_size) {
           Object item = m_array[index];
           int start = index + 1;
           System.arraycopy(m_array, start, m_array, index, m_size - start);
           m_array[--m_size] = null;
           modCount++;
           return item;
       } else {
           throw new IndexOutOfBoundsException("Index " + index + " is out of valid range 0-" + (m_size - 1));
       }
   }
   
   /*
    * (non-Javadoc)
    * 
    * @see java.util.AbstractList#set(int, java.lang.Object)
    */
   public Object set(int index, Object element) {
       if (index >= 0 && index < m_size) {
           Object item = m_array[index];
           m_array[index] = element;
           return item;
       } else {
           throw new IndexOutOfBoundsException("Index " + index + " is out of valid range 0-" + (m_size - 1));
       }
   }
   
   /*
    * (non-Javadoc)
    * 
    * @see java.util.AbstractList#removeRange(int, int)
    */
   protected void removeRange(int from, int to) {
       if (from >= 0 && to <= m_size) {
           int length = m_size - to;
           if (length > 0) {
               System.arraycopy(m_array, to, m_array, from, length);
           }
           m_size -= to - from;
           for (int i = m_size; i > to;) {
               m_array[--i] = null;
           }
           modCount++;
       } else {
           throw new IndexOutOfBoundsException("Range of " + from + "-" + to + " exceeds valid range 0-" + m_size);
       }
   }
   
   /**
    * Get modify counter. This supports tracking changes to determine when cached filters need to be updated.
    * 
    * @return count
    */
   public int getModCount() {
       return modCount;
   }
   
   /**
    * Remove range of values. This is just a public version of the protected base class method
    * {@link #removeRange(int, int)}
    * 
    * @param from
    * @param to
    */
   public void remove(int from, int to) {
       removeRange(from, to);
   }
   
   /**
    * Compact the list, removing any null values.
    */
   public void compact() {
       int offset = 0;
       while (offset < m_size) {
           if (m_array[offset] == null) {
               break;
           } else {
               offset++;
           }
       }
       if (offset < m_size) {
           int fill = offset;
           while (++offset < m_size) {
               if (m_array[offset] != null) {
                   m_array[fill++] = m_array[offset];
               }
           }
           m_size = fill;
           modCount++;
       }
   }

}

 </source>
   
  
 
  

List Reverse Test

   <source lang="java">
    

import java.util.*; public class ReverseTest {

 public static void main(String args[]) {
   ArrayList simpsons = new ArrayList();
   simpsons.add("Bart");
   simpsons.add("Hugo");
   simpsons.add("Lisa");
   simpsons.add("Marge");
   simpsons.add("Homer");
   simpsons.add("Maggie");
   simpsons.add("Roy");
   Comparator comp = Collections.reverseOrder();
   Collections.sort(simpsons);
   System.out.println(simpsons);
 }

}

 </source>
   
  
 
  

List Search Test

   <source lang="java">
    

import java.util.*; public class SearchTest {

 public static void main(String args[]) {
   String simpsons[] = {"Bart", "Hugo", "Lisa", "Marge",
                        "Homer", "Maggie", "Roy"};
   // Convert to list
   ArrayList list = new ArrayList(Arrays.asList(simpsons));
   // Ensure list sorted
   Collections.sort(list);
   System.out.println("Sorted list: [length: " + list.size() + "]");
   System.out.println(list);
   // Search for element in list
   int index = Collections.binarySearch(list, "Maggie");
   System.out.println("Found Maggie @ " + index);
   // Search for element not in list
   index = Collections.binarySearch(list, "Jimbo Jones");
   System.out.println("Didn"t find Jimbo Jones @ " + index);
   // Insert
   int newIndex = -index - 1;
   list.add(newIndex, "Jimbo Jones");
   System.out.println("With Jimbo Jones added: [length: " + list.size() + "]");
   System.out.println(list);
 }

}

 </source>
   
  
 
  

ListSet extends List and Set

   <source lang="java">
  

/*

   GNU LESSER GENERAL PUBLIC LICENSE
   Copyright (C) 2006 The Lobo Project
   This library is free software; you can redistribute it and/or
   modify it under the terms of the GNU Lesser General Public
   License as published by the Free Software Foundation; either
   version 2.1 of the License, or (at your option) any later version.
   This library is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
   Lesser General Public License for more details.
   You should have received a copy of the GNU Lesser General Public
   License along with this library; if not, write to the Free Software
   Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
   Contact info: lobochief@users.sourceforge.net

• /

/*

* Created on Sep 3, 2005
*/

import java.util.*; public class ListSet implements List, Set {

 private final List list = new ArrayList();
 private final Set set = new HashSet();
 
 public ListSet() {
   super();
 }
 /* (non-Javadoc)
  * @see java.util.List#add(int, E)
  */
 public void add(int index, Object element) {
   if(this.set.add(element)) {
     list.add(index, element);
   }
 }
 /* (non-Javadoc)
  * @see java.util.List#add(E)
  */
 public boolean add(Object o) {
   if(this.set.add(o)) {
     return this.list.add(o);
   }
   else {
     return false;
   }
 }
 /* (non-Javadoc)
  * @see java.util.List#addAll(java.util.Collection)
  */
 public boolean addAll(Collection c) {
   boolean changed = false;
   Iterator i = c.iterator();
   while(i.hasNext()) {
     Object element = i.next();
     if(this.add(element)) {
       changed = true;
     }
   }
   return changed;
 }
 /* (non-Javadoc)
  * @see java.util.List#addAll(int, java.util.Collection)
  */
 public boolean addAll(int index, Collection c) {
   boolean changed = false;
   int insertIndex = index;
   Iterator i = c.iterator();
   while(i.hasNext()) {
     Object element = i.next();
     if(this.set.add(element)) {
       this.list.add(insertIndex++, element);
       changed = true;
     }
   }
   return changed;
 }
 /* (non-Javadoc)
  * @see java.util.List#clear()
  */
 public void clear() {
   this.set.clear();
   this.list.clear();
 }
 /* (non-Javadoc)
  * @see java.util.List#contains(java.lang.Object)
  */
 public boolean contains(Object o) {
   return this.set.contains(o);
 }
 /* (non-Javadoc)
  * @see java.util.List#containsAll(java.util.Collection)
  */
 public boolean containsAll(Collection c) {
   return this.set.containsAll(c);
 }
 /* (non-Javadoc)
  * @see java.util.List#get(int)
  */
 public Object get(int index) {
   return this.list.get(index);
 }
 /* (non-Javadoc)
  * @see java.util.List#indexOf(java.lang.Object)
  */
 public int indexOf(Object o) {
   return this.list.indexOf(o);
 }
 /* (non-Javadoc)
  * @see java.util.List#isEmpty()
  */
 public boolean isEmpty() {
   return this.set.isEmpty();
 }
 /* (non-Javadoc)
  * @see java.util.List#iterator()
  */
 public Iterator iterator() {
   return this.list.iterator();
 }
 /* (non-Javadoc)
  * @see java.util.List#lastIndexOf(java.lang.Object)
  */
 public int lastIndexOf(Object o) {
   return this.list.lastIndexOf(o);
 }
 /* (non-Javadoc)
  * @see java.util.List#listIterator()
  */
 public ListIterator listIterator() {
   return this.list.listIterator();
 }
 /* (non-Javadoc)
  * @see java.util.List#listIterator(int)
  */
 public ListIterator listIterator(int index) {
   return this.list.listIterator(index);
 }
 /* (non-Javadoc)
  * @see java.util.List#remove(int)
  */
 public Object remove(int index) {
   Object element = this.list.remove(index);
   if(element != null) {
     this.set.remove(element);
   }
   return element;
 }
 /* (non-Javadoc)
  * @see java.util.List#remove(java.lang.Object)
  */
 public boolean remove(Object o) {
   if(this.set.remove(o)) {
     this.list.remove(o);
     return true;
   }
   else {
     return false;
   }
 }
 /* (non-Javadoc)
  * @see java.util.List#removeAll(java.util.Collection)
  */
 public boolean removeAll(Collection c) {
   if(this.set.removeAll(c)) {
     this.list.removeAll(c);
     return true;
   }
   else {
     return false;
   }
 }
 /* (non-Javadoc)
  * @see java.util.List#retainAll(java.util.Collection)
  */
 public boolean retainAll(Collection c) {
   if(this.set.retainAll(c)) {
     this.list.retainAll(c);
     return true;
   }
   else {
     return false;
   }
 }
 /* (non-Javadoc)
  * @see java.util.List#set(int, E)
  */
 public Object set(int index, Object element) {
   this.set.add(element);
   return this.list.set(index, element);
 }
 /* (non-Javadoc)
  * @see java.util.List#size()
  */
 public int size() {
   return this.list.size();
 }
 /* (non-Javadoc)
  * @see java.util.List#subList(int, int)
  */
 public List subList(int fromIndex, int toIndex) {
   return this.list.subList(fromIndex, toIndex);
 }
 /* (non-Javadoc)
  * @see java.util.List#toArray()
  */
 public Object[] toArray() {
   return this.list.toArray();
 }
 /* (non-Javadoc)
  * @see java.util.List#toArray(T[])
  */
 public Object[] toArray(Object[] a) {
   return this.list.toArray(a);
 }
 
 public boolean equals(Object other) {
   return other instanceof ListSet && this.list.equals(((ListSet) other).list);
 }
 
 public int hashCode() {
   return this.list.hashCode();
 }

}

 </source>
   
  
 
  

List to array

   <source lang="java">
    

/*

* Copyright (c) Ian F. Darwin, http://www.darwinsys.ru/, 1996-2002.
* All rights reserved. Software written by Ian F. Darwin and others.
* $Id: LICENSE,v 1.8 2004/02/09 03:33:38 ian Exp $
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
* 1. Redistributions of source code must retain the above copyright
*    notice, this list of conditions and the following disclaimer.
* 2. Redistributions in binary form must reproduce the above copyright
*    notice, this list of conditions and the following disclaimer in the
*    documentation and/or other materials provided with the distribution.
*
* THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS""
* AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
* TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
* PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS
* BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
* CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
* SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
* INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
* CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
* ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
* POSSIBILITY OF SUCH DAMAGE.
* 
* Java, the Duke mascot, and all variants of Sun"s Java "steaming coffee
* cup" logo are trademarks of Sun Microsystems. Sun"s, and James Gosling"s,
* pioneering role in inventing and promulgating (and standardizing) the Java 
* language and environment is gratefully acknowledged.
* 
* The pioneering role of Dennis Ritchie and Bjarne Stroustrup, of AT&T, for
* inventing predecessor languages C and C++ is also gratefully acknowledged.
*/

import java.util.ArrayList; import java.util.List; /** List to array */ public class ToArray {

 public static void main(String[] args) {
   List list = new ArrayList();
   list.add("Blobbo");
   list.add("Cracked");
   list.add("Dumbo");
   // list.add(new Date()); // Don"t mix and match!
   // Convert a collection to Object[], which can store objects
   // of any type.
   Object[] ol = list.toArray();
   System.out.println("Array of Object has length " + ol.length);
   // This would throw an ArrayStoreException if the line
   // "list.add(new Date())" above were uncommented.
   String[] sl = (String[]) list.toArray(new String[0]);
   System.out.println("Array of String has length " + sl.length);
 }

}

 </source>
   
  
 
  

Set Operating on Lists: addAll, removeAll, retainAll, subList

   <source lang="java">
  

import java.util.ArrayList; import java.util.List; public class Main {

 public static void main(String[] argv) throws Exception {
   List list1 = new ArrayList();
   List list2 = new ArrayList();
   list1.addAll(list2);
   list1.removeAll(list2);
   list1.retainAll(list2);
   list1.clear();
   int newSize = 2;
   list1.subList(newSize, list1.size()).clear();
 }

}

 </source>
   
  
 
  

Shuffle a list

   <source lang="java">
    

import java.util.Arrays; import java.util.Collections; import java.util.List; public class Shuffle {

 public static void main(String args[]) {
   String[] strArray = new String[] { "Java", "Source", "And", "and",
       "Support", "jexp" };
   List l = Arrays.asList(strArray);
   Collections.shuffle(l);
   System.out.println(l);
 }

}

 </source>
   
  
 
  

Sort a list

   <source lang="java">
    

import java.util.Arrays; import java.util.Collections; import java.util.List; public class NameSort {

 public static void main(String args[]) {
   String n[] = new String[] { "John", "Lennon", "Karl", "Marx",
       "Groucho", "Marx", "Oscar", "Grouch" };
   List l = Arrays.asList(n);
   Collections.sort(l);
   System.out.println(l);
 }

}

 </source>
   
  
 
  

Using the Double Brace Initialization.

   <source lang="java">
  

import java.util.ArrayList; import java.util.List; public class Main {

 static List<String> list = new ArrayList<String>() {
   {
     add("A");
     add("B");
     add("C");
     add("D");
     add("E");
     add("F");
   }
 };
 public static void main(String args[]) {
   dump(list);
 }
 public static void dump(List<String> list) {
   for (String s : list) {
     System.out.println(s);
   }
 }

}

 </source>
   
  
 
  

Utility methods for operating on memory-efficient lists. All lists of size 0 or 1 are assumed to be immutable.

   <source lang="java">
  

/*

* Copyright 2009 Google Inc.
* 
* Licensed under the Apache License, Version 2.0 (the "License"); you may not
* use this file except in compliance with the License. You may obtain a copy of
* the License at
* 
* http://www.apache.org/licenses/LICENSE-2.0
* 
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
* WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
* License for the specific language governing permissions and limitations under
* the License.
*/

import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; import java.util.ruparator; import java.util.List; /**

* Utility methods for operating on memory-efficient lists. All lists of size 0
* or 1 are assumed to be immutable. All lists of size greater than 1 are
* assumed to be mutable.
*/

public class Lists {

 private static final Class<?> MULTI_LIST_CLASS = ArrayList.class;
 private static final Class<?> SINGLETON_LIST_CLASS = Collections.singletonList(
     null).getClass();
 public static <T> List<T> add(List<T> list, int index, T toAdd) {
   switch (list.size()) {
     case 0:
       // Empty -> Singleton
       if (index != 0) {
         throw newIndexOutOfBounds(list, index);
       }
       return Collections.singletonList(toAdd);
     case 1: {
       // Singleton -> ArrayList
       List<T> result = new ArrayList<T>(2);
       switch (index) {
         case 0:
           result.add(toAdd);
           result.add(list.get(0));
           return result;
         case 1:
           result.add(list.get(0));
           result.add(toAdd);
           return result;
         default:
           throw newIndexOutOfBounds(list, index);
       }
     }
     default:
       // ArrayList
       list.add(index, toAdd);
       return list;
   }
 }
 public static <T> List<T> add(List<T> list, T toAdd) {
   switch (list.size()) {
     case 0:
       // Empty -> Singleton
       return Collections.singletonList(toAdd);
     case 1: {
       // Singleton -> ArrayList
       List<T> result = new ArrayList<T>(2);
       result.add(list.get(0));
       result.add(toAdd);
       return result;
     }
     default:
       // ArrayList
       list.add(toAdd);
       return list;
   }
 }
 public static <T> List<T> addAll(List<T> list, int index, List<T> toAdd) {
   switch (toAdd.size()) {
     case 0:
       // No-op.
       return list;
     case 1:
       // Add one element.
       return add(list, index, toAdd.get(0));
     default:
       // True list merge, result >= 2.
       switch (list.size()) {
         case 0:
           if (index != 0) {
             throw newIndexOutOfBounds(list, index);
           }
           return new ArrayList<T>(toAdd);
         case 1: {
           List<T> result = new ArrayList<T>(1 + toAdd.size());
           switch (index) {
             case 0:
               result.addAll(toAdd);
               result.add(list.get(0));
               return result;
             case 1:
               result.add(list.get(0));
               result.addAll(toAdd);
               return result;
             default:
               throw newIndexOutOfBounds(list, index);
           }
         }
         default:
           list.addAll(index, toAdd);
           return list;
       }
   }
 }
 public static <T> List<T> addAll(List<T> list, List<T> toAdd) {
   switch (toAdd.size()) {
     case 0:
       // No-op.
       return list;
     case 1:
       // Add one element.
       return add(list, toAdd.get(0));
     default:
       // True list merge, result >= 2.
       switch (list.size()) {
         case 0:
           return new ArrayList<T>(toAdd);
         case 1: {
           List<T> result = new ArrayList<T>(1 + toAdd.size());
           result.add(list.get(0));
           result.addAll(toAdd);
           return result;
         }
         default:
           list.addAll(toAdd);
           return list;
       }
   }
 }
 public static <T> List<T> addAll(List<T> list, T... toAdd) {
   switch (toAdd.length) {
     case 0:
       // No-op.
       return list;
     case 1:
       // Add one element.
       return add(list, toAdd[0]);
     default:
       // True list merge, result >= 2.
       switch (list.size()) {
         case 0:
           return new ArrayList<T>(Arrays.asList(toAdd));
         case 1: {
           List<T> result = new ArrayList<T>(1 + toAdd.length);
           result.add(list.get(0));
           result.addAll(Arrays.asList(toAdd));
           return result;
         }
         default:
           list.addAll(Arrays.asList(toAdd));
           return list;
       }
   }
 }
 public static <T> List<T> create() {
   return Collections.emptyList();
 }
 public static <T> List<T> create(T item) {
   return Collections.singletonList(item);
 }
 public static <T> List<T> create(T... items) {
   switch (items.length) {
     case 0:
       return create();
     case 1:
       return create(items[0]);
     default:
       return new ArrayList<T>(Arrays.asList(items));
   }
 }
 public static <T> List<T> normalize(List<T> list) {
   switch (list.size()) {
     case 0:
       return create();
     case 1: {
       if (list.getClass() == SINGLETON_LIST_CLASS) {
         return list;
       }
       return create(list.get(0));
     }
     default:
       if (list.getClass() == MULTI_LIST_CLASS) {
         return list;
       }
       return new ArrayList<T>(list);
   }
 }
 @SuppressWarnings("unchecked")
 public static <T> List<T> normalizeUnmodifiable(List<T> list) {
   if (list.size() < 2) {
     return normalize(list);
   } else {
     return (List<T>) Arrays.asList(list.toArray());
   }
 }
 public static <T> List<T> remove(List<T> list, int toRemove) {
   switch (list.size()) {
     case 0:
       // Empty
       throw newIndexOutOfBounds(list, toRemove);
     case 1:
       // Singleton -> Empty
       if (toRemove == 0) {
         return Collections.emptyList();
       } else {
         throw newIndexOutOfBounds(list, toRemove);
       }
     case 2:
       // ArrayList -> Singleton
       switch (toRemove) {
         case 0:
           return Collections.singletonList(list.get(1));
         case 1:
           return Collections.singletonList(list.get(0));
         default:
           throw newIndexOutOfBounds(list, toRemove);
       }
     default:
       // ArrayList
       list.remove(toRemove);
       return list;
   }
 }
 public static <T> List<T> set(List<T> list, int index, T e) {
   switch (list.size()) {
     case 0:
       // Empty
       throw newIndexOutOfBounds(list, index);
     case 1:
       // Singleton
       if (index == 0) {
         return Collections.singletonList(e);
       } else {
         throw newIndexOutOfBounds(list, index);
       }
     default:
       // ArrayList
       list.set(index, e);
       return list;
   }
 }
 public static <T> List<T> sort(List<T> list, Comparator<? super T> sort) {
   if (list.size() > 1) {
     Collections.sort(list, sort);
   }
   return list;
 }
 private static <T> IndexOutOfBoundsException newIndexOutOfBounds(
     List<T> list, int index) {
   return new IndexOutOfBoundsException("Index: " + index + ", Size: "
       + list.size());
 }

}

 </source>