LinkedLists

A linked list is a recursive data structure that is a collection of nodes. A linked list has the option of either being an empty list, or a node that stores data and refers to another linked list. The empty list case is represented with None while the other case splits the node into two parts: the head and the tail. The head is where the value of the node is stored while the tail is where the node references to another linked list. This means that the node may refer to an empty list, or another node like itself. As one can see, recursion plays a big part in linked list structures due to multiple referencing to other linked lists.

Linked lists are similar to lists in the aspect that information can be stored and modified. Some of the operations that they share are adding an element, deleting an element, reversing the list, and finding the element according to the index of the element. However, there is a slight difference because linked lists depend on referencing to another object instead of being one whole object like lists. In linked lists, the operations require the changing of the head's value and the tail's reference. For example, to prepend a value to the front of the linked list, the head of the list must be equal to the new value, but the tail must refer to the previous head of the linked list. Because linked lists use this referencing, infinite loops can cause issues for most of these methods and operations, which end up crashing the program.

As with many computer science structures, there is more than one way to implement linked lists. The first one is the one I've been talking about so far with the use of a head and a tail. The other way to implement linked list is to use linked list as a wrapper class for a class that defines a single node. The node class saves the value and the referenced node while the linked list wrapper class manipulates the nodes with operations. Both implementations essentially do the same thing, but in some cases the other one is more preferable due to the conditions of the problem. Linked list is another way for computer scientists to store and manipulate information, but in a slightly different approach than storing in one object such as list.