Practice/Google/Implement a Special Type of Linked List

Implement a Special Type of Linked List

Object Oriented DesignMust

Problem

Design and implement a blockchain-inspired linked list data structure. Each node in this list contains three pieces of information: a numerical value, a hash that is derived from the previous node's value, and a reference to the next node. This structure mimics simplified blockchain behavior where each block cryptographically links to its predecessor.

Your implementation should support adding new values to the chain and validating that the entire chain maintains its integrity (i.e., each node's hash correctly corresponds to the previous node's value).

Requirements

1. Create a BlockNode class with the following attributes:

   • value: an integer representing the node's data
   • hash: a string computed from the previous node's value (for the first node, use "0" as the previous hash)
   • next: a reference to the next node in the chain

2. Create a BlockchainList class with the following methods:

   • append(value): adds a new node to the end of the chain with the given value
   • validate_chain(): returns True if the chain is valid (each node's hash matches the expected hash based on the previous node's value), False otherwise
   • get_values(): returns a list of all values in the chain

3. The hash for each node should be computed as: "hash_" + str(previous_node_value)

   • For the first node (head), the hash should be "hash_0" since there's no previous value

4. Each new node must correctly link its hash to the actual value of the previous node

Constraints

• Node values are integers in the range [-10^6, 10^6]
• The chain can contain 0 to 10,000 nodes
• All operations should be efficient: O(1) for append, O(n) for validation and getting values

Examples

Example 1:

` chain = BlockchainList() chain.append(42) chain.append(17) chain.append(99)

chain.get_values() # Returns: [42, 17, 99] chain.validate_chain() # Returns: True

Explanation:

• Node 1: value=42, hash="hash_0", next=Node2
• Node 2: value=17, hash="hash_42", next=Node3
• Node 3: value=99, hash="hash_17", next=None Each hash correctly references the previous node's value. `

Example 2:

` chain = BlockchainList() chain.append(100)

chain.get_values() # Returns: [100] chain.validate_chain() # Returns: True

Explanation: A single-node chain is always valid. `

Example 3:

` chain = BlockchainList() chain.validate_chain() # Returns: True

Explanation: An empty chain is considered valid. `