What is a linked list?
A linked list is a data structure that utilizes nodes to create an array. Many young high school coders and introductory coders may be familiar with the idea of an array. It is something that is commonly seen in a majority of languages (Ruby, JavaScript, Python, etc…). For those who may be unfamiliar with the concept, an array is a sequenced list of data. A linked list uses nodes that hold data as its head and a tail that points to the next node. Once the last node has been reached, its tail will point to a value of null.
Why use a linked list?
Though creating a linked list may seem like more work from a programmers standpoint, as opposed to using predefined container objects, a linked list when used properly can have its benefits.
The first benefit is the size of a linked list is potentially limitless. In languages such as Java, the container object often used in place of an array is a list in which the length of the list must be predefined. If one wanted to add something to the list, a whole new list would have to be created to be able to hold the additional data.
The second benefit is addition and deletion of data at any point in the list. If you have worked with arrays in JavaScript, you may know how tedious this can be. In order to insert or delete at any point in the array, a for loop must be run to manually push elements in the array to their new indexes. Not only from a programmer’s perspective is this inefficient but also from the processor’s perspective. Without getting into too much detail about Big O, in essence, for loops cause programs to run slightly slower than code without for loops. When nested for loops or multiple instances of for loops occur, this causes a larger run time for the program. Linked lists eliminate this issue because when a new node is added to a certain index, its tail can point to the next data value. The tail of the node previous to the inserted node should now point to the inserted node. Deleting a node is even easier. Just change the tail of the node preceding the deleted node to now point to the node after the deleted node.
In summary linked lists are a sequence of nodes containing a head and tail. They are most effectively implemented when you want to use a list that only needs to add more elements or delete elements.
