Theoretical CS

2.1 Linear Structures

You’ve seen a very common example of a linear structure already: Arrays! There are some other linear structures that you should know; however, Lists are used much more common compared to Stacks and Queues.


A stack is a mutable data structure with Last In, First Out access.

⊕ peek, push, pop, top


A queue is a mutable data structure with First In, First Out access.

⊕ peek, enqueue, dequeue, front, back


A list is an immutable data structure. It is recursive; we will get a taste of recursion now while we are working with lists, but we will go more in depth later in the course!

You will be working with lists very often in Scala. Some techniques that will be useful to learn are higher order functions and pattern matching.

Nil, cons (::), concat (:::)
⊕ map, filter
⊕ match, case

<< 1.2 Taste of Scala 2.2 Associative Structures >>