Learning Objectives – after this chapter you will be able to:
- Explain what a data structure is and why the choice of data structure matters.
- Describe how a linked list connects its nodes using pointers.
- Explain how a blockchain links blocks using hash pointers instead of memory addresses.
- Compare a blockchain with a linked list on reference, editing, copies, control and security.
Data Structure?
- A data structure is a way of organising, managing and storing data in a computer so that it can be accessed and modified efficiently.
- Every data structure is a trade-off: one structure may make searching fast, another may make inserting or deleting fast. Choosing the right one directly affects the speed and memory use of a program.
- Data structures are commonly divided into:
- Linear – elements are arranged in a sequence: arrays, linked lists, stacks and queues.
- Non-linear – elements form a hierarchy or network: trees, graphs and hash tables.
- Examples :
Linked List in Data Structure
- A linked list is a linear collection of nodes. Each node holds two things: the data and a pointer (reference) to the next node.
- The first node is called the head; the last node points to
NULL, which marks the end of the list. - Unlike an array, a linked list does not need a fixed size or a continuous block of memory. Nodes can be added or removed by simply changing pointers.
- Main types: singly linked list (pointer to next), doubly linked list (pointers to next and previous) and circular linked list (last node points back to the head).
- Examples :
BLOCK-CHAIN
A NEW FORM OF DATA STRUCTURE
- A blockchain is a data structure used to build a decentralized ledger (log-book). It is made of blocks arranged one after another in a fixed order.
- Each block contains a batch of records (usually transactions) and a header. The header stores the hash of the previous block, which acts as the link in the chain.
- This link is called a hash pointer: it tells you where the previous block is and also what it contained, because any change to the previous block changes its hash.
- The first block of a chain is called the genesis block. It is the only block that has no previous block.
- A blockchain is append-only: new blocks are added at the end; old blocks are never edited or deleted.
- Examples :
How a hash pointer protects the chain
Block 1 (Genesis)Prev: 0000…
Data: Tx…
Hash: A1F3…
Data: Tx…
Hash: A1F3…
Block 2Prev: A1F3…
Data: Tx…
Hash: 7C2B…
Data: Tx…
Hash: 7C2B…
Block 3Prev: 7C2B…
Data: Tx…
Hash: 9E40…
Data: Tx…
Hash: 9E40…
If someone changes a record in Block 1, its hash changes (for example from A1F3… to 55D9…). Block 2 still stores A1F3…, so the link breaks and the tampering is immediately visible. To hide the change, the attacker would have to recompute every later block and convince the rest of the network to accept the altered copy – which consensus rules make practically impossible. (Hash values shown are shortened illustrations.)
Difference between Linked List and Blockchain
| Sno | Basis | Blockchain | LinkedList |
|---|---|---|---|
| 1 | Reference | A block refers to another block by its cryptographic hash. | A node refers to another node by its memory address (pointer). |
| 2 | Reference Direction | Each block points backwards to the previous block. | Each node usually points forwards to the next node. |
| 3 | Adding Data | A new block is validated by the network (consensus) and then appended to every node’s copy of the chain. | A node is inserted directly by the program, anywhere in the list, without any validation. |
| 4 | Copies | Many identical copies exist, one on every full node of the network. | Usually a single copy exists in the memory of one program. |
| 5 | Data Editing | Confirmed data is immutable; changing it breaks the hash links and is rejected by the network. | Any node can be changed or deleted simply by updating its value or pointers. |
| 6 | Purpose | A tamper-evident, shared digital ledger of transactions or records. | A general-purpose sequential collection of data inside a program. |
| 7 | Control Structure | No central owner; control is shared by the participants of the network. | Controlled entirely by the program (and person) that owns it. |
| 8 | Block Content | A block can contain transactions that deploy or call smart contracts (code executed by every node). | A node stores whatever data the program places in it; there is no shared execution. |
| 9 | Security | Uses hashing and digital signatures to prove integrity and authorship. | Has no built-in integrity check or authentication. |
| 10 | Speed | Slower, because every block must be verified and agreed upon by many nodes. | Very fast, because operations happen in local memory. |
| 11 | Complexity | Complex to implement: networking, cryptography and consensus are required. | Simple to implement in any programming language. |
Key Takeaways
- A blockchain can be viewed as a linked list of blocks that uses hash pointers instead of memory pointers.
- Hash pointers make the structure tamper-evident: changing any old block breaks every link after it.
- Unlike a linked list, a blockchain is replicated on many computers and grows only through consensus.
Question / Answer (15 questions)
Answer : A data structure is a way of organising and storing data so that it can be accessed and changed efficiently. The choice matters because each structure favours different operations – for example, arrays give fast access by index while linked lists give cheap insertion and deletion – so the right choice improves speed and memory use.
Answer : In a linear data structure the elements form a single sequence, e.g. arrays, linked lists, stacks and queues. In a non-linear data structure elements are connected in a hierarchy or network, e.g. trees and graphs.
Answer : A node contains (1) the data value and (2) a pointer (reference) holding the address of the next node. The last node’s pointer is NULL, which marks the end of the list.
Answer : Singly linked list – each node points only to the next node. Doubly linked list – each node points to both the next and the previous node. Circular linked list – the last node points back to the first node instead of NULL.
Answer : A hash pointer stores both the location of a piece of data and the cryptographic hash of that data. It lets you find the data and also verify that it has not been changed, because any change produces a different hash.
Answer : Like a linked list, a blockchain is a sequence of elements (blocks) where each element references another. The difference is that each block references the previous block through its hash, not a memory address, which makes the sequence tamper-evident.
Answer : The genesis block is the first block of a blockchain. It is the only block that has no previous block, so its “previous hash” field is empty or set to zeros. Bitcoin’s genesis block was created on 3 January 2009.
Answer : Changing data in a block changes that block’s hash. The next block still stores the old hash, so the link no longer matches. Every following block would also need to be recomputed, and the altered chain would still be rejected by the honest nodes that hold the original copy.
Answer : In a blockchain each block points backwards to the previous block. In a typical singly linked list each node points forwards to the next node.
Answer : Every full node keeps its own copy so that there is no single point of failure and no single owner. Nodes can independently verify the chain and compare copies, which provides availability and resistance to tampering.
Answer : Append-only means new data can only be added as new blocks at the end of the chain. Existing blocks are never edited or deleted; corrections are made by adding new transactions that record the change.
Answer : A linked list operation happens instantly in local memory. Adding data to a blockchain requires broadcasting transactions, validating signatures, building a block and reaching consensus among many nodes, all of which take time.
Answer : Every blockchain transaction is digitally signed with the sender’s private key, and nodes verify the signature with the public key. A linked list has no built-in way to prove who added or changed a node.
Answer : Yes. On smart-contract platforms such as Ethereum, transactions in a block can deploy contract code or call existing contract functions. Every node executes that code in the same way, so the results become part of the shared state.
Answer : A linked list is controlled by the single program (and person) that owns it. A public blockchain has no central owner; it is maintained jointly by its participants according to the protocol’s consensus rules.
MCQ Test : Check Your Understanding (5 questions)
Select an option and press Check Answer, or answer all questions and press Submit Test to see your score. Each answer comes with an explanation.
Bibliography/References
The notes, questions and MCQs on this page are original explanations written for this course. The works listed below were consulted and are cited for attribution and further reading. Product names, logos and trademarks belong to their respective owners. Short quotations, where used, are marked and attributed.
- GeeksforGeeks. (n.d.). How is Blockchain different from a Linked List? https://www.geeksforgeeks.org/how-is-blockchain-different-from-a-linked-list/
- Narayanan, A., Bonneau, J., Felten, E., Miller, A., & Goldfeder, S. (2016). Bitcoin and Cryptocurrency Technologies: A Comprehensive Introduction. Princeton University Press. ISBN 978-0-691-17169-2.
- Nakamoto, S. (2008). Bitcoin: A Peer-to-Peer Electronic Cash System. https://bitcoin.org/bitcoin.pdf
- Haber, S., & Stornetta, W. S. (1991). How to time-stamp a digital document. Journal of Cryptology, 3(2), 99–111. https://doi.org/10.1007/BF00196791
- Yaga, D., Mell, P., Roby, N., & Scarfone, K. (2018). Blockchain Technology Overview (NISTIR 8202). National Institute of Standards and Technology. https://doi.org/10.6028/NIST.IR.8202