# Linked List

A Linked List is a linear data structure, which consists of nodes which point from one to the next to the next.

## Variations

- A singly linked list has nodes which only point forward to the next node.
- A doubly linked list has nodes which also point back to the previous node.
- A cyclical linked list is one in which the last node's "next" points to the first node.

## Operations and their time complexity (big-o)

There doesn't seem to be consistent terminology accross languages for these operations, so I'm using the names I find most intuitive.

- Prepend:
- Adds an item to the beginning of the list
- O(1): Constant time

- RemoveFirst:
- Removes the first item from the list, and makes the second (if any) the first
- O(1): Constant time

- Append:
- Adds an item to the end of the list
- O(n) in a naive version which traverses the entire list to reach the end
- O(1) in an optimized version which maintains a reference to the last item

- RemoveLast:
- Removes the last item from the list
- O(n) in a naive version which traverses the entire list to reach the end
- O(1) in an optimized version which maintains a reference to the last item

- Reverse:
- Reverses the older of the items in the list
- O(n) because it must traverse the entire list once to reverse it