Lists

There are multiple types of lists including linked lists, doubly linked lists, multiple linked lists, circular linked lists, queues, and stacks.

In this section, we will present a simple linked list that is one of the simplest and most popular data structures in imperative programming languages.

A linked list is a linear collection of data elements called nodes pointing to the next node using pointers. Linked lists contain their data in a linear and sequential manner. Simply put, each node is composed of data and a reference to the next node in the sequence, as shown in the following figure:

Let's start with a simple version:

enum LinkedList<Element: Equatable> { 
    case end 
    indirect case node(data: Element, next: LinkedList<Element>) 
} 

Our approach is similar to our BST implementation approach. The difference resides in the node case that has a data element and a pointer to its next element, which is also a LinkedList.

Empty LinkedList

Our LinkedList needs a method to...