Guide to Scala ListSet

1. Introduction

In this tutorial, we’ll go over the ListSet data type in Scala. We’ll also discuss how to add and remove elements from a ListSet along with some other basic operations.

2. What is ListSet?

In Scala, both List and Set are immutable collections. However, they essentially have two fundamental differences:

• A List maintains the insertion order, while a Set doesn’t.
• A List can contain duplicate elements, while a Set stores only unique elements.

What if we need an immutable collection that maintains the insertion order and, at the same time, stores only unique elements?

We use ListSet to meet these requirements. It implements an immutable set, but uses a list-based data structure for storing the elements. Moreover, it maintains a reversed insertion order. That means the last added element would be stored at the head of a ListSet.

We can create an empty ListSet in two ways – by using the function ListSet.empty() or by using a constructor:

val listSet1 = ListSet.empty;
val listSet2 = ListSet();

assert(listSet1.size == 0);
assert(listSet2.size == 0);

3. ListSet Operations

In this section, we’ll see some of the common operations that we can perform on a ListSet.

3.1. Creating a ListSet and Adding Elements

We can initialize a ListSet with default elements using a constructor. Subsequently, to add elements, we can use the + operator:

var listSet = ListSet(1, 2, 3, 4);
assert(listSet.size == 4);

listSet = listSet + 5; // ListSet(1, 2, 3, 4, 5)
assert(listSet.size == 5); 

assert(listSet.last == 5);
assert(listSet.head == 1);

Here, we’ve initialized listSet with four integer values. To add a new value, we used the + operator that adds an element to the end.

The complexity of adding an element into a ListSet is O(n).  Thus, if we create a ListSet of n elements, it will take O(n²) time. Therefore, such collections are suitable for only a small number of elements.

Also, we cannot add an existing element to a ListSet. So, from the example above, the number 4 already exists in the listSet, and if we try to add it again in the listSet, it won’t get added:

println("listSet before adding 4: " + listSet)
listSet = listSet + 4; // adding an existing element

println("listSet after adding 4: " + listSet)

Here’s the output of the above statements:

listSet before adding 4: ListSet(1, 2, 3, 4, 5)
listSet after adding 4: ListSet(1, 2, 3, 4, 5)

3.2. Removing an Element

We can use the – operator to remove an element from a ListSet:

var listSet = ListSet(1, 2, 3, 4);
listSet = listSet - 1; // ListSet(2, 3, 4)

assert(listSet.size == 3);
assert(listSet.last == 4);
assert(listSet.head == 2);

Here, we used the – operator to remove element 1 from listSet.

We should keep in mind that if we try to remove an element that’s not present in the ListSet, then it remains unchanged:

var listSet = ListSet(1, 2, 3, 4);
listSet = listSet - 6 // ListSet(1, 2, 3, 4)

assert(listSet.size == 4)
assert(listSet.last == 4)
assert(listSet.head == 1)

In the code snippet above, we’ve tried to remove 6 which is not present in listSet. Therefore, listSet remains unchanged.

Furthermore, we can also remove multiple elements in one go:

var listSet = ListSet(1, 2, 3, 4);
listSet = listSet - (6, 1, 3); // ListSet(2, 4)

assert(listSet.size == 2);
assert(listSet.last == 4);
assert(listSet.head == 2);

Here, as 6 is not present in listSet, only 1 and 3 are removed from it. So, as a result, its size changes to 2, and the head now changes to element 2.

Similar to addition, removing an element from a ListSet takes O(n) time.

3.3. Adding Two ListSets

We can use the ++ operator to add two ListSets:

val listSet1 = ListSet(1, 2, 3, 4);
val listSet2 = ListSet(5, 6, 7, 8);

val listSet3 = listSet1 ++ listSet2;

println(listSet3);

assert(listSet3.size == 8);
assert(listSet3.last == 8);
assert(listSet3.head == 1);

In the above example, listSet3 is formed as a result of the addition of two ListSets. Therefore, the size of listSet3 is 8. Here’s the output of the print statement:

ListSet(1, 2, 3, 4, 5, 6, 7, 8)

3.4. Removing Elements of One ListSet From Another

Similarly, we can use the — operator to get a new ListSet that’s formed after removing all the elements of one ListSet from another:

val listSet1 = ListSet(1, 2, 3, 4);
val listSet2 = ListSet(3, 4, 5, 6);

val listSet3 = listSet1 -- listSet2

println(listSet3);

assert(listSet3.size == 2);
assert(listSet3.last == 2);
assert(listSet3.head == 1);

Here, numbers 5 & 6, which are there in ListSet2, are not present in listSet1. Therefore, only numbers 3 & 4, which are present in both listSet1 and listSet2, are removed from listSet1 . Here’s the output of the print statement:

ListSet(1, 2)

3.5. The head and tail Operations

We use the head method to get the first element of a ListSet. On the other hand, the tail method returns all the elements of a ListSet except the first element. This means that the return type of tail is a ListSet:

val listSet: ListSet[String] = ListSet("Baeldung", "JavaScript", "Scala", "Java", "COBOL")

assert(listSet.head == "Baeldung")
assert(listSet.tail == ListSet("JavaScript", "Scala", "Java", "COBOL"))

Since the elements are stored in the reversed insertion order, the complexity of both head and tail operations is O(n).

4. Conclusion

In this article, we explored ListSet in Scala along with its syntax, and some of the basic operations with examples.

As always, the code for these examples is available over on GitHub.