列表

Linked Lists

A linked list is a data structure that contains a series of nodes, each of which contains the data you want and a pointer to where the next node of the list is.

In our design of linked lists, you can access the first and last nodes, as well as the size of a linked list in $O(1)$.

We can create a new linked list in $O(1)$. We can add elements in $O(1)$: given a new node $N$, tell the last node to point to $N$. Accessing a given element of a linked list is $O(n)$: to get to node $n-1$ for example, you must start at the first node and traverse next, next, next $n-1$ times.

Some benefits of lists are that their size is not fixed, and it doesn't waste nearly any memory. However, in my opinion, $O(n)$ lookup is pretty bad because isn't the whole purpose of data structures to be able to look things up?

Doubly Linked Lists

Another list is a doubly linked list, in which nodes point to the next element and the previous element. This gives us some freedom in navigating the list, but at the cost of the extra memory it takes to store the extra pointer. For example, if the task is to print the elements of the list backwards, we'd use a doubly linked list because it brings the algorithm from $O(n^2)$ to $O(n)$.