List implementations

One of the most common implementations of the list data structure is the array-based list. Generally speaking, an array-based list is simply a contiguous list of array positions, each holding a pointer to a list element. Since the list is based on an array, its functionality and performance are very similar to that of an array.

As seen in the previous examples, another common implementation is the linked list. A linked list is also a sequence of elements, except most implementations refer to the elements as nodes. In a linked list, the pointers to the elements are not contained in an array structure, but rather a pointer exists in memory to identify the first node. Then each node contains a link to the subsequent node in the list.

Finally, there is the doubly linked list. In a doubly linked list, each node contains a link to both the subsequent node in the list and the previous node in the list. A doubly linked list makes traversing the list bidirectionally a much simpler...