Skip to content

List Tutorial

Jump to bottom
Brian Burton edited this page Sep 1, 2023 · 10 revisions

List Tutorial

Javimmutable provides an IList interface with a signature similar to java.util.List. This interface provides access to elements in the IList 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 IList the compiler will find all of the places that you need to replace a simple method call with an assignment.

The interface, IList, provides indexed access to elements within the list and allows addition and removal of values at any index. Values added to the end of list are always stored in the same order that they were added. In addition entire ILists can be inserted into or appended to other ILists very efficiently (roughly the same effort to insert an entire IList as to insert a single element). The current implementation uses a balanced binary tree with leaf nodes containing up to 64 values each which provides O(log2(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 detail.

IList<Integer> list = ILists.of();
list = list.insert(10).insert(20).insert(30);
assertEquals(10, list.get(0));
assertEquals(20, list.get(1));
assertEquals(30, list.get(2));

IList<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 IList interfaces provide a getList() method that returns an object implementing java.util.List using 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 IList 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());

In versions prior to 3.0.0 the JImmutableRandomAccessList interface was provided to extend IList with additional methods supporting insertion and removal of values within the list (not just the beginning or end). Since 3.0.0 this interface was removed and IList supports this feature.

IList<Integer> list = ILists.of();
list = list.insert(30).insert(0, 20).insert(0, 10);
assertEquals(Arrays.asList(10, 20, 30), list.getList());

IList<Integer> list2 = list.delete(1).insert(1, 87);
assertEquals(Arrays.asList(10, 20, 30), list.getList());
assertEquals(Arrays.asList(10, 87, 30), list2.getList());

IList provides special methods for filtering the values in the list. The select() method returns a list containing only those values for which a Predicate returns true. The reject() method returns a list containing all elements except those for which a Predicate returns true. Both methods are optimized for the Predicate returning true less often than false. Additionally forEach() and reduce() methods can be used to quickly scan and execute a function on all elements of the list without the overhead of creating Iterators. The stream() method allows the use of Java streams to manipulate the contents of the list. Full support is provided for parallel streams.

IList<String> source = ILists.of("able", "baker", "charlie", "delta", "echo");
assertEquals(ILists.of("baker", "charlie"), source.select(str -> str.contains("r")));
assertEquals(ILists.of("able", "baker", "delta"), source.reject(str -> str.contains("h")));
assertEquals("ablebakercharliedeltaecho", source.reduce("", (answer, str) -> answer + str));
assertEquals(ILists.of("baker", "charlie"),
              source.stream()
                  .filter(str -> str.contains("r"))
                  .collect(ICollectors.toList()));

IDeque

The IDeque interface is similar to IList. It provides most of the same methods and offers better performance for single item gets, assigns, inserts, and deletes. Insertion and deletion are allowed at the ends but not in the middle. In most cases an IDeque provides all the functionality an application needs and, because it uses 32-way trees rather than balanced binary trees, offers better performance than IList.

Clone this wiki locally