Unraveling Linked Lists: Mastering Traversal and Length Calculation in Python

Welcome to our exciting course, "Linked Lists, Stacks, and Queues in Python". Here, we aim to decode and comprehend the fundamentals and advanced concepts of Python's data structures. In this lesson, we delve deeper into applying two basic operations on Linked Lists – traversing through a list and calculating its length. These operations are akin to taking a walk down a street and counting the number of houses you have passed.

First, we define our goal and understand why we perform it. We then have a go at it using a straightforward approach before learning the efficient technique to accomplish it like a pro!

While walking down a street, imagine you had to document each house but in reverse order. This presents a similar scenario, but instead, we are dealing with a linked list. The task is to traverse the list in reverse form and print all the elements.

Problem 1: Application

Traversing a list in a reverse manner is often encountered when you need to know the last state or the most recent actions in a scenario. For instance, in a browser history, the most recent web pages are usually at the top of your browsing history. In such a situation, you would need to traverse the list from the tail to the head.

To traverse a Linked List in reverse, we start from the tail node and move up to the previous node until we reach the head. However, because linked lists are generally singly linked lists and do not provide a direct way to access previous nodes, we must take a different approach. We can push all nodes onto a stack and then pop them out. This will give us the nodes in reverse order.

Unlike a book where you can quickly flip to the previous page, we have to navigate through the 'book' once (in other words, traverse the Linked List from head to tail), but 'mark' every page we visit (push every node on a stack). We then revisit the marked pages in reverse order (pop each node from the stack).

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

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

    def LinkedList_reverseTraversal(self):
        node = self.head
        stack = []
        while node is not None:
            stack.append(node.data)
            node = node.next
        while stack:
            print(stack.pop())

In this Python code, we start at the head of our Linked List and use a while loop to push every node into our stack until we have reached the tail. We then use another while loop to pop each element from the stack until it's empty, effectively printing the data in reverse order.

Note: Both using an array and a stack involve similar space and time complexities (O(n) for both), so the choice between them may depend on specific use cases or preferences.