To truly understand linked lists, you need to understand pointers. Before getting to pointers, lets implement a linked list without using pointers.

Let's define an array of tuples (number, index) where number is the number we care about and index is the index of the next element in the array.

This is an array of such tuples. The numbers on the top are the indices into the array - starting from 0. Each array element is a tuple like the above - the first row is the number and the 2nd row is the index of the next element.

Given this, the number after 15 is 20. Because the index associated with 15 is 1 and the number at index 1 at 20.

The number after 20 is 22 because the index associated with 20 is 2 and the number at index 2 is 22.

The sequence of number is hence 15, 20, 22, 23, and 25. The index -1 associated with 25 is invalid and indicates the end of the numbers.

Now, lets remove 20 from this list. In a normal array, deleting 20 would require copying all numbers after 20 forward so that there are no gaps in the array. With this, you dont need to do that - just change the index associated with 15 to 2 like the below.

What's the number after 15? It is 22 since the index associated with 15 is 2 and the number at index 2 is 22.

So, the new sequence is 15, 22, 23, 25. 20 is still in the array, but it doesn't matter.

Now, lets insert 19. But, I want to insert in such a way that when we follow the indices, we get a sorted order. In other words, the sequence should be 15, 19, 22, 23, 25.

This is what I have done:

1. Added 19 at the end of the array (at index 5)
2. Copy the index associated with 15 to the index associated with 15 - i.e. make 19's index = 15's index = 2
3. Changed the index associated with 15 to 19's index, i.e. 15's index = 5

If you look at the algorithm for insertion into a linked list, it would look like the above.

Now, following the list: 15, 19 (element at index 5), 22 (element at index 3), 23, and 25

This is an implementation of a linked list using an array. An element in a linked list is a tuple. It contains:

1. The number that we care about, and
2. A pointer to the next element in the list (we used the index into the array instead of a pointer)

Linked lists make deletion and insertion into sorted lists very efficient. Sorted arrays are very inefficient with deletion and insertion.

In a real implementation, the index we used is replaced by a pointer to the next element.

What's a pointer? A pointer is a reference to computer memory. Like in this example, an index was a reference to an array element, a pointer refers to computer memory.