Linked Lists

Perhaps Linked Lists is one of the simplest data structures that someone could think. They are similar with the treasure hunt game. You can imagine it like in each location there are two kind of information, one is some stored value and one is the direction for the next location. Unfortunately, this could remind some people the process that some offices have to get official documents from the government.

The first Python object that we have to build for implementing this data structure is a node. This will be the location that will contain the next location and the value that we want to store.

class Node(object):
    def __init__(self, value=None, next_node=None):
        self.value = value
        self.next_node = next_node

Now that we have the Node object the Linked List data structure is easy to implement, we just need to remember the first node of the list. We can also add the functionality of adding a new node as the starting node of a given Linked List.

class LinkedList(object):

    def __init__(self, head=None):
        self.head = head

    def add_starting_node(self, new_head):
        temp = self.head
        self.head = new_head
        self.head.next_node = temp

Note that someone could thing of another approach to create a link list. A normal Python list could be used to create Linked Lists, however, this would not be a correct approach as a feature of Linked Lists is that there is no limit on the number of nodes, however, normal lists do have such a limit. Another inconsistency is that in a normal list there is no need to keep track of the location of the next element.

Even if the Linked List data structure is conceptual simple, there are some interesting problems involving Linked Lists. Most of these problems can be solved by keeping track of two locations of the Linked List. Keep this in mind as you try to think about the problems about Linked Lists.