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.