Linked Lists

A linked list is a data structure that holds a sequence of linked nodes. Each node contains data and a reference, where reference points to its successor node in the Linked List.

The above diagram shows a typical example of a singly linked list. It consists of 3 nodes. The first node consists of a value of 1 and contains a pointer to the next node. The next node in the list has a value of 2 and subsequently consists of a reference to the last node in the list and so on. The last node in a linked list contains a value 3 but it doesn't point to anything. 

When a reference doesn't point to any valid object, programming languages typically have a "NULL" value to represent the missing value. In Javascript, we use "null" for that purpose - and it's called a null reference.

Reference is also sometimes called a pointer. This comes from the C/C++ world where variables can point to memory addresses. In Javascript, we cannot point to memory addresses. Instead we have references to objects.

The first node in the linked list is called Head Node. Head node is our handle to the linked list. We traverse the linked list starting at the head node and then move to the node pointed by the current node. We'll visit the traversal in detail later.

It's a valid question. We already have a built-in type Array that acts as a container similar to a linked list. Turns out that array is not an efficient data structure in all cases. Arrays are implemented in programming languages in a certain way which makes it very efficient for certain cases while they are highly inefficient for other cases.

Given how arrays are stored in memory, it is usually inefficient to insert elements in the middle. 

However, linked list also has drawbacks. You cannot access an element randomly and have to traverse from the first node to the next and so on until you find your desired node. 

If you need to access elements at random positions in the list, don't use a Linked List.