Working with the concepts we've studied can actually be quite enjoyable once we understand them. And there's nothing quite as satisfying as feeling confident in our knowledge. So, why not let our minds dive into LinkedList and see what we can accomplish?

What is a LinkedList?

A linked list is a linear data structure comprised of a group of objects, with each object referred to as a node. These nodes contain a value and a memory address for the next node in the sequence.

In a linked list, the elements are not stored next to each other in memory like in a standard list or array. Instead, each node has the memory address of the next node, and to access an item, you need to walk through each node one by one. If there is no next node, then the value is set to null.

Creating a Linked List

The underlying type is a Node and a linked list contains a collection of them, let's define a Node type first

class Node:
    def __init__(self, val):
        self.val = val
        self.next = None

    def set_next(self, node):
        self.next = node

    # printing a node will provide it's value
    def __repr__(self):
        return self.val

def main():
    first_name = Node("spike")
    last_name = Node("speigel")
    first_name.set_next(last_name)

    print(first_name)
    print(last_name)

    # print full name
    print(f"{first_name} {last_name}")


main()

Output:

spike
speigel
spike speigel

Now that we have a Node type, let's create a linked list and iterate through to print the values of it

yield keyword

While we are iterating through the list we need to print the value of each node, that happens when we return the node, but using return would break the loop

And that's when the yield keyword comes in, it resumes the function call where it left off after returning the value

let's see that in action

class LinkedList:
    def __init__(self):
        self.head = None

    def __iter__(self):
        node = self.head

    # my method first version
        #while node.next != None:
        #    yield node
        #    node = node.next
        #    if node.next == None:
        #        yield node
        #        return

    # optimized method        
        while node != None:
            yield node
            node = node.next

    # setting the list head to the node linked to other node and so on
    def add_to_tail(self, node):
        self.head = node

    def __repr__(self):
        values = []
# underlying implementation of this loop is the __iter__ method of linkedlist class
        for node in self:
            values.append(node.val)
        return " -> ".join(values)

class Node:
    def __init__(self, val):
        self.val = val
        self.next = None

    def set_next(self, node):
        self.next = node

    # printing a node will provide it's value
    def __repr__(self):
        return self.val


def main():
    node0 = Node("spike")
    node1 = Node("julia")
    node2 = Node("vicious")
    node3 = Node("faye")
    node0.set_next(node1)
    node1.set_next(node2)
    node2.set_next(node3)
    linked_list = LinkedList()
    linked_list.add_to_tail(node0)
    print(linked_list)

main()

output:
spike -> julia -> vicious -> faye

The first solution I came up with for iterating through a linked list wasn't the most optimized one, I was checking the next node's value while being on the current node and I didn't have to since the value of the node is being set to its next one on current iteration itself

And at the next iteration, the condition will be checked, if the node is null the loop breaks, I hope that clears it

Adding a new tail to the linked list

Previously, we created a linked list where it's add_to_tail the method takes a node that already represents a linked list and the nodes are linearly set using the set_next method

But the optimal way to do so is to add a new node to the existing data structure and not present a pre-set version

So we iterate through the linked list if we have a node whose next value is null then we set it to the new node

class LinkedList:
    def add_to_tail(self, node):
        if self.head == None:
            self.head = node
            return
        current_node = self.head
        while True:
            if current_node.next == None:
                current_node.set_next(node)
                return
        current_node = current_node.next

def main():
    node0 = Node("spike")
    node1 = Node("julia")
    node2 = Node("vicious")
    node3 = Node("faye")
    node0.set_next(node1)
    node1.set_next(node2)
    node2.set_next(node3)
    linked_list = LinkedList()
    linked_list.add_to_tail(node0)
    print(linked_list)
    linked_list.add_to_tail(Node("jet"))
    print(linked_list)
    linked_list.add_to_tail(Node("ed"))
    print(linked_list)

main()

# Output:
spike -> julia -> vicious -> faye
spike -> julia -> vicious -> faye -> jet
spike -> julia -> vicious -> faye -> jet -> ed

Adding a new head to the linked list

Let's see how we can do this, and why we are pushing elements to the end and beginning of linked lists will make more sense shortly

add_to_head takes a node as input and sets the next value to the current head and the current head will be set to the new node

def add_to_head(self, node):
    if self.head == None:
        self.head = node
    # node.next = self.head or
    node.set_next(self.head)
    self.head = node

def main():
    node0 = Node("spike")
    node1 = Node("julia")
    node2 = Node("vicious")
    node3 = Node("faye")
    node0.set_next(node1)
    node1.set_next(node2)
    node2.set_next(node3)
    linked_list = LinkedList()
    linked_list.add_to_tail(node0)
    print(linked_list)
    linked_list.add_to_tail(Node("jet"))
    print(linked_list)
    linked_list.add_to_head(Node("akira"))
    print(linked_list)

main()

# Output:
spike -> julia -> vicious -> faye
spike -> julia -> vicious -> faye -> jet
akira -> spike -> julia -> vicious -> faye -> jet

Linked List is better suited for implementing queue(FIFO - first in first out) data structure, for the reason, the nodes of it are spread across memory and one just needs to swap around pointers to add/remove and has constant time O(1)

While adding/removing an element at the beginning or at the end of the list has constant time O(1), performing the same operation at a specific position requires shifting the elements of the list on either side

as the position nears the beginning or end since elements of a list are stored as a contiguous sequence in the memory, the time complexity of its execution also nears O(n)

One still needs to traverse the linked list to get to a specific element but it has constant time to add/remove an element at any position in the list for that reason in some cases it's preferred over the normal list like implementing stack and queues

O(1) pushes to a linked list

So far, the current linked list can have O(1) pushes and pops at the head, we need to do that for the tail, as of now we traverse through the linked list to get to the end of it instead, we can keep track of it each time a new node is added by setting the tail pointer to the new node, that way we know where the last node exists in the linked list

# creating a new data member in the class constructor self.tail and setting it to None
class LinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

    def add_to_head(self, node):
        if self.head == None:
            self.head = node
# initially both will point to same object, tail's value will be changed as the new ones are added
            self.tail = node
        node.set_next(self.head)
        self.head = node

    def add_to_tail(self, node):
        if self.head == None:
            self.head = node
            self.tail = node
            return
# the current node the tail is pointing to its next value is Null/None
# we set that to new node
        self.tail.next = node
# now we change the tail pointer to the new node, this way we don't have to iterate as we are keeping track of the last element with the help of tail data member
        self.tail = node

# Note that this a small part of the code where the changes are made, you can find full code on previous code snippets
def main():
    node0 = Node("spike")
    node1 = Node("julia")
    node2 = Node("vicious")
    node3 = Node("faye")
    nodes = [node0, node1, node2, node3]
    linked_list = LinkedList()
    for node in nodes:
        linked_list.add_to_tail(node)
    print(linked_list)

main()

# Output:
spike -> julia -> vicious -> faye

End thoughts

I'm really glad we had the chance to go through this together. Hopefully, you now have a firm understanding of how to implement basic applications using linked lists.

Also, this is something I learned from boot.dev, I'd recommend you to check that out, it's good.

Happy Learning and I'll see you in the next one