List Tutorial

Javimmutable provides two interfaces with signatures similar to java.util.List. Both of these interfaces provide access to elements in the List using an integer index. As with List valid indexes are always in the range zero through size() - 1. Javimmutable uses assign() instead of set(), insert() instead of add(), and delete() instead of remove() so that when converting code from java.util.List to JImmutableList the compiler will find all of the places that you need to replace a simple method call with an assignment.

The simpler interface, JImmutableList, provides indexed access to elements within the list but restricts addition and removal of values to the end of the list. Values added to the list are always stored in the same order that they were added. Cursors also traverse the values in the same order as they were added to the list. The current implementation uses a 32-way tree which provides O(log32(n)) performance for all operations. (see [Comparative Performance])

As with all of the immutable collection classes any method that modifies the list actually creates a new list instance and returns it as the method's result. This result can be assigned to the original list variable or to a new variable as needed. The original, unmodified, version of the list remains in memory until garbage collected. The lists reuse as much structure as possible so adding and removing elements requires very little copying and only a small amount of additional memory.

In the example below notice that changed's third value is now 45 and list's third value is still 30. The two lists internally contain shared copies of the common values to minimize memory consumption and improve performance but as a user of the list you don't need to worry about that.

        JImmutableList<Integer> list = JImmutables.list();
        list = list.insert(10).insert(20).insert(30);
        assertEquals(10, list.get(0));
        assertEquals(20, list.get(1));
        assertEquals(30, list.get(2));

        JImmutableList<Integer> changed = list.deleteLast().insert(45);
        assertEquals(10, list.get(0));
        assertEquals(20, list.get(1));
        assertEquals(30, list.get(2));
        assertEquals(10, changed.get(0));
        assertEquals(20, changed.get(1));
        assertEquals(45, changed.get(2));

The JImmutableList interfaces provide a getList() method that returns an object implementing java.util.List that uses the original list as its data source. The actual data is not copied so this method has very low overhead. You can use this any time you need to pass a JImmutableList to code that needs a java.util.List. The resulting List is unmodifiable so set, remove, etc methods all throw UnsupportedOperationExceptions.

        assertEquals(Arrays.asList(10, 20, 30), list.getList());
        assertEquals(Arrays.asList(10, 20, 45), changed.getList());

The JImmutableRandomAccessList interface provides all of the same methods as JImmutableList but also allows insertion and removal of values from anywhere in the list. The current implementation uses a 2-3 tree which provides O(log2(n)) performance for all operations.

The JImmutables.ralist() factory method can be used to create new JImmutableRandomAccessList. In the example below a new JImmutableRandomAccessList is created and values are inserted to place its elements in the same order as list from the first example.

        JImmutableRandomAccessList<Integer> ralist = JImmutables.ralist();
        ralist = ralist.insert(30).insert(0, 20).insert(0, 10);
        assertEquals(10, ralist.get(0));
        assertEquals(20, ralist.get(1));
        assertEquals(30, ralist.get(2));
        JImmutableRandomAccessList<Integer> ralist2 = ralist;
        ralist2 = ralist2.delete(1).insert(1, 87);
        assertEquals(10, ralist.get(0));
        assertEquals(20, ralist.get(1));
        assertEquals(30, ralist.get(2));
        assertEquals(10, ralist2.get(0));
        assertEquals(87, ralist2.get(1));
        assertEquals(30, ralist2.get(2));
        assertEquals(Arrays.asList(10, 20, 30), ralist.getList());
        assertEquals(Arrays.asList(10, 87, 30), ralist2.getList());