Skip to main content

Linked List

Introduction​

Linked list structures leverage the EUTXO model to enhancing scalability and throughput significantly. By linking multiple UTXOs together through a series of minting policies and validators, it can improve the user experience interacting with smart contract concurrently.

info

The github repository introducing these data structures can be found here.

Documentation​

Linked List​

The Plutarch Linked List is an on-chain, sorted linked list solution designed for blockchain environments, specifically utilizing NFTs (Non-Fungible Tokens) and datums. It provides a structured and efficient way to store and manipulate a list of key/value pairs on-chain.

linked-list

Entry Structure​

Each entry in the list comprises:

  • NFT: A unique identifier for each entry.
  • EntryDatum: A data structure containing the key/value pair, a reference to the entry's NFT, and a pointer to the next NFT in the list.

EntryDatum Definition​

data EntryDatum = EntryDatum {
  key :: BuiltinByteString,
  value :: Maybe SomeValue,
  nft :: NFT,
  next :: Maybe NFT
}
  • key: A unique identifier for the entry.
  • value: The value associated with the key. It can be Nothing for the head entry.
  • nft: The NFT representing the entry.
  • next: The NFT of the next entry in the list, or Nothing for the last entry.

Operations​

Inserting an Entry​

insert entry

Insertion involves:

  • Inputs: Two adjacent list entries.
  • Outputs:
    • The first input entry, modified to point to the new entry.
    • The newly inserted entry, pointing to the second input entry.
    • The second input entry, unchanged.

Validation Rules

  • Keys must maintain the order: a < b < c, where a is the lowest, b is the new key, and c is the highest.
  • The pointers must be correctly updated to maintain list integrity.
Removing an Entry​

remove entry

To remove an entry:

  • Inputs: The entry to remove and its preceding entry.
  • Output: The preceding entry is modified to point to what the removed entry was pointing to.

Utilizing NFTs as Pointers​

NFTs serve as robust and unique pointers within the list. Their uniqueness is ensured by a specific minting policy related to the list's head NFT.

Key Considerations​

  • Efficiency: As on-chain lookups are inefficient, off-chain structures are recommended for this purpose.
  • Datum Hashes: Not suitable for pointers due to the complexity of updates and security concerns.
  • Security: The integrity of the list is maintained through careful minting policies and entry validation.

Advanced Features​

  • Forwarding Minting Policy: A feature of Plutus to control NFT minting dynamically.
  • List Head: Utilizes an empty head entry for validating insertions at the start of the list.
  • End-of-List Insertions: Handled by ensuring the last entry points to Nothing.

Plutarch Linked List implementation​

The Plutarch Linked List implementation provides several functions to create and manipulate Linked List. Below is a brief overview of each function:

  • pInit: Constructs the Linked List head
  • pDeinit: Destructs the Linked List
  • pInsert: Inserts a node into the linked list
  • pRemove: Removes a node from the linked list