Linked list

Arrays are great for storing data. We have also seen that any element of an array can be read in O(1) time. But arrays are fixed in size. Changing the size of an array means creating a new array and copying all the elements to the original array. The simplest recourse to the resizing problem is to store each element in a different object and then hold a reference in each element to the next element. This way, the process of adding a new element will just involve creating the element and attaching it at the end of the last element of the original linked list. In another variation, the new element can be added to the beginning of the existing linked list:

Figure 3: An example of a linked list

Figure 3 shows an example of a linked list. The arrows represent a reference. Each element is stored in a wrapper object that also holds a reference to the next element wrapper. There are two additional references to the first and last elements, which are required for any operation to start...