Linked List

Linked list is the natural counterpart to the array data-structure. In linked list's case we trade more time for less space. A linked list is made up of nodes, and each node has the following information:

• value
• pointer to next node

You can think of a linked list as a chain. If you have a single value, you'll have a linked list of one node. If you require 100 values to store, your linked list will be 100 nodes long. Contrast it to an array, and whether you need to store one value or a 100, you'll need to declare an array of size 100 or the maximum values you intend to eventually store.

Linked list is able to save on memory and be slow in retrieval because it doesn't require contiguous allocation of memory. Nodes of a linked list could be all over the place in a computer's memory. This placement requires us to always remember the first or head node of the linked list. Below is one possible representation of a linked list consisting of three nodes in memory. Note that head is a variable that contains the address of the first node in the linked list. If we lose the head, we lose the linked list. Unlike an array, you can see that the nodes of the linked list can be anywhere.

Given the above representation, it becomes very easy to reason about the various operations in a linked list.

• If we want to retrieve the nth element in the list, we'll need to walk the list from the head all the way to the nth element. In the worst case, we could be asked to retrieve the last element of the list. Therefore, in the worst case, the retrieval would need us to walk to the back of the linked list for a ...