1

I often hear people say that a blockchain is essentially a linked list (i.e. https://www.quora.com/Is-a-blockchain-essentially-a-linked-list)

A block stores the hash of the previous block for validation/consensus. This is similar to how a node in a linked list references the address of the previous node, but it's not quite the same.

In a block, the previous hash is stored by value, not by reference, so you can't really access the previous node by traversing the chain. Whereas in a linked list, you store the address which is a reference to the previous node. You can access any block in constant time where as in a linked list, it's linear time.

On top of this, many implementation that I've seen of a blockchain is an array/slice of blocks. I tried briefly looking at bitcoin's source code (disclaimer: I don't know C++). It looks like the implementation of the chain of blocks in memory uses std::vector which is basically a dynamic array.

Isn't a blockchain more similar to an array than it is to a linked list?

2

I assume the linked list analogy just arises because of the reference to the previous block as you say. It's less about how to find that block, and more just about identifying it. The actual data structure used to store the Blockchain isn't what is being described.

  • Thank you for the clarification. I was confused by diagrams where one block references previous block and thought you had to traverse the chain in reverse until I started digging into it some more. – Huy Oct 22 '18 at 19:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.