Lists in scala are sequential, but are NOT flat as Arrays. Internally they are implemented as Linked List. All elements of the list must of the same type, i.e., lists are homogenous.

### Examples of List creations

val l1: List[String] = List("apple", "mango") val l2: List[Int] = List(1,3,4) val l3: List[Nothing] = List() val l4: List[List[Int]] = List (List(2,3), List(1), List(1,3,4)) val l5: List[Int] = 1:: 2:: Nil

where, *Nil* is the empty list.

### Cons operator ( :: )

:: is called the cons operator, and is used to prepend elements to start of list.

x::xs gives a NEW list starting with x followed by remaining elements of xs. E.g

1::2::3::List(4, 5) //Equivalent to List(1,2,3,4,5) 1::2::Nil //Equivalent to List(1,2)

Operators ending with **:** are right associative, i.e., A::B::C is interpreted as A::(B::C) – Operators ending **:** are also different in a way that they are operations on the right operand, i.e., A::B::C::D is equivalent to ((D.::C).::B).::A

### Basic List Operations

Consider two lists xs and ys

- head : gives the first element of the list.
- tail : gives the remaining list excluding the first element of the list
- last : give the last element of the list
- init : gives list excluding the last element of the list.
- isEmpty : true if list is empty , else false.
- (n) : returns the element at ‘n’ position in the list.
- take(n) : returns a list containing only the first ‘n’ elements.
- drop(n) : Returns a list excluding the first ‘n’ elements.
- reverse – returns a list reversed
- updated(n, x) – Updates the list and set value ‘x’ at position ‘n’ of the list
- indexOf(x) – returns index of element ‘x’ in given list. If not found then returns -1.
- contains(x) – Returns true if list contains element ‘x’
- x::xs – add element ‘x’ to the start of list ‘xs’.
- xs ++ ys – Concatenates two lists, xs followed by ys.
- xs ::: ys – Equivalent to xs ++ ys

Some example of list operations

val list = List(1, 3, 5, 7, 9, 11) list.head //1 list.tail //List(3, 5, 7, 9, 11) list.last //11 list.init //List(1, 3, 5, 7, 9) list(3) //7 list.reverse //List(11, 9, 7, 5, 3, 1) list take 2 //List(1, 3) list drop 2 //List(5, 7, 9, 11) list updated (3, 8) //List(1, 3, 5, 8, 9, 11) list indexOf 7 //3 list contains 7 //true 0::list //List(0, 1, 3, 5, 7, 9, 11) List(-3, -1) ++ list //List(-3, -1, 1, 3, 5, 7, 9, 11) List(-3, -1) ::: list //List(-3, -1, 1, 3, 5, 7, 9, 11)

### Pattern matching on lists

Different list patterns are

**Nil** : Matches an empty list.

**List()** : equivalent to empty list,

**x::xs** – matches a list whose starting element is x.

**x::y::ys** – matches a list whose first two elements are x and y.

**List(x)** : A list with single element x

Example : Insertion sort using pattern matching on lists

def isort(xs: List[Int]): List[Int] = xs match { case x::ys => insert(x, isort(ys)) case _ => xs } def insert(x:Int, xs: List[Int]): List[Int] = xs match { case List() => List(x) case y:: ys => if (x > y) y::insert(x, ys) else x::xs }

### Higher order functions on lists

**Map** : Used to transform the elements of the list.

**Filter** : Used to select elements from the list, based on some predicate condition.

**FilterNot** : Used to select elements from the list, that do NOT match the predicate condition.

**Partition** : Same as filter, but creates two lists as results. One that matches predicate and other that does not. Equivalent to (xs filter p, xs filterNot p)

**TakeWhile** : Take elements till the filter matches. Stops at first unmatched element.

**DropWhile** : Drop the elements till filter matches.

**Span** : equivalent to (xs takeWhile p, xs dropWhile p)

Some examples of list higher order functions.

val myList :List[Int] = List(-8, -6, -3, 1, 2, 3, 3, 6, 6, 8, 9) val p: Int => Boolean = x => x%2 == 0

myList filter p //List(-8, -6, 2, 6, 6, 8) myList.filterNot(p) //List(-3, 1, 3, 3, 9) myList.partition(p) //(List(-8, -6, 2, 6, 6, 8), List(-3, 1, 3, 3, 9)) myList.takeWhile(p) //List(-8, -6) myList.dropWhile(p) //List(-3, 1, 2, 3, 3, 6, 6, 8, 9) myList span p //(List(-8, -6), List(-3, 1, 2, 3, 3, 6, 6, 8, 9))

**Reference**