Linked lists are exactly what they sound like, a list of elements where each element is linked to the one after it, sort of like a necklace chain. Each ring is its own separate element until someone comes a long and links them together to form a chain. A linked list can contain any kind of data, sorted or unsorted, with duplicate or unique elements.
You may be asking, what is the difference between an array and a linked list? One difference is how they are stored. An array has to be stored in order from left to right on your computer, where as a linked list does not. As mentioned above, each element in a linked lists need to know who’s behind them but the elements themselves can be disbursed throughout your computers storage.
Also unlike an array, a linked list needs to run through the entire list to find an element. For example, if you wanted to pull the third element out of an array you would simply write the following line of code.
With a linked list, you would build the following method and call this method to run through the list until it gets to the third element.
If you would like to insert an element to the top of the list or head, that’s pretty easy and can be done in constant time, with the following method. To insert an element into the first index or index 0 of an array, the entire array may need to move, depending on whats before it in storage.
To insert an element, not on the head of the list, you will need to run through the entire list and add your new element to the last element on the list or tail. You can use this method to insert your element anywhere in the linked list.
However to delete you will not need to run through the list. As you can see in the method below, all we need to do is call the element before the element that needs to be deleted. Our method deletes the next element and links the element we called to the element behind our deleted element.
Now that we have gone over how to add, remove, and delete data from a linked list, allow me to introduce: a doubly linked list.
This is just like a regular linked list but in addition to the all the elements having a link to the next element, they also link to the previous element. For certain operations, this can really come in handy. For example can be used in navigation systems where both front and back navigation is required. It is also used by browsers to implement backward and forward navigation of visited web pages i.e. back and forward button.
