find the standard deviation of all nodes in a linked list in python

To find the standard deviation of all nodes in a linked list, we can follow these steps:

  1. Traverse the linked list and store all the node values in an array or list.
  2. Compute the mean of all the values in the list using the mean function from the statistics module.
  3. Compute the standard deviation using the stdev function from the statistics module or by computing it manually using the formula sqrt(sum([(x - mean)**2 for x in list])/len(list)).
  4. Return the computed standard deviation.

Here is the implementation:

main.py
import math
import statistics

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

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

    def add_node(self, data):
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node

    def standard_deviation(self):
        values = []
        current_node = self.head
        while current_node:
            values.append(current_node.data)
            current_node = current_node.next
        
        mean = statistics.mean(values)
        # Using statistics module
        stdev = statistics.stdev(values)
        # Manually computing standard deviation
        # stdev = math.sqrt(sum([(x - mean)**2 for x in values])/len(values))
        
        return stdev

# Example usage
linked_list = LinkedList()
linked_list.add_node(1)
linked_list.add_node(2)
linked_list.add_node(3)
linked_list.add_node(4)
linked_list.add_node(5)

print(linked_list.standard_deviation()) # Output: 1.5811388300841898
1039 chars
42 lines

In this implementation, we store the values of all nodes in the values list and then compute the mean and standard deviation using the mean and stdev functions from the statistics module. Alternatively, we can compute the standard deviation manually using the formula and the sqrt function from the math module. This implementation has a time complexity of O(n) since we need to traverse the linked list once, where n is the number of nodes in the list.

gistlibby LogSnag