Implementing a Dynamic Linked List in VHDL with Protected Types and Access Pointers

A linked list is a dynamic data structure that expands and contracts as elements are added or removed. VHDL’s object‑oriented features—access types, records, and protected types—make it possible to implement this structure cleanly and efficiently.

Creating the DataStructures Package

We’ll encapsulate all of the linked‑list logic in a dedicated VHDL package called DataStructures. This future‑proof name allows easy extension to other structures such as trees or hash maps later on.

package DataStructures is
   -- Public declarations go here
end package DataStructures;

package body DataStructures is
   -- Private declarations and implementations go here
end package body DataStructures;

A VHDL package consists of a declarative region (public interface) and a body (private implementation). The declarative region is visible to users; the body remains internal.

Defining a Protected Type

Protected types act like lightweight classes in VHDL. They can contain subprograms, type declarations, and variables. We’ll define a protected type called LinkedList that exposes three operations: Push, Pop, and IsEmpty.

package DataStructures is

   type LinkedList is protected
      procedure Push(constant Data : in integer);
      impure function Pop return integer;
      impure function IsEmpty return boolean;
   end protected;

end package DataStructures;

package body DataStructures is

   type LinkedList is protected body
   end protected body;

end package body DataStructures;

Introducing the Item Record

Inside the protected body we declare a record that represents a node. The record contains the data payload and a pointer to the next node.

type LinkedList is protected body

   type Item is record
      Data : integer;
      NextItem : Ptr;
   end record;

end protected body;

Because protected types cannot declare new types in the declarative region, the Item record is defined inside the body.

Handling Pointers with Access Types

We use an access type Ptr to reference Item instances dynamically. This two‑step declaration avoids circular dependencies.

type Item;
   type Ptr is access Item;
   type Item is record
      Data : integer;
      NextItem : Ptr;
   end record;

A root pointer tracks the first node. When the list is empty, Root is null.

variable Root : Ptr;

Implementing Linked‑List Operations

Push Procedure

Appending a new element is straightforward: allocate a new Item, populate it, and link it at the end.

procedure Push(Data : in integer) is
   variable NewItem : Ptr;
   variable Node : Ptr;
begin
   NewItem := new Item;
   NewItem.Data := Data;

   if Root = null then
      Root := NewItem;
   else
      Node := Root;
      while Node.NextItem /= null loop
         Node := Node.NextItem;
      end loop;
      Node.NextItem := NewItem;
   end if;
end;

Pop Function

Removing the first element requires careful memory management. Since VHDL lacks garbage collection (pre‑2017), we explicitly deallocate the removed node.

impure function Pop return integer is
   variable Node : Ptr;
   variable RetVal : integer;
begin
   Node := Root;
   Root := Root.NextItem;

   RetVal := Node.Data;
   deallocate(Node);

   return RetVal;
end;

IsEmpty Function

impure function IsEmpty return boolean is
begin
   return Root = null;
end;

Testing the Linked List

Although access types are not synthesizable, they are ideal for verification. A testbench demonstrates the linked list’s behavior.

Importing the Package

library work;
use work.DataStructures.LinkedList;

Using a Shared Variable

Signals cannot be of protected type, so we use a shared variable to allow multiple processes to interact with the list.

architecture sim of LinkedListTb is
   shared variable List : LinkedList;
begin
   -- Test process
end architecture;

Complete Testbench

library work;
use work.DataStructures.LinkedList;

entity LinkedListTb is
end entity;

architecture sim of LinkedListTb is
   shared variable List : LinkedList;
begin
   process is
   begin
      for i in 1 to 5 loop
         report "Pushing " & integer'image(i);
         List.Push(i);
      end loop;

      while not List.IsEmpty loop
         report "Popping " & integer'image(List.Pop);
      end loop;

      wait;
   end process;
end architecture;

Full DataStructures Package

package DataStructures is
   type LinkedList is protected
      procedure Push(constant Data : in integer);
      impure function Pop return integer;
      impure function IsEmpty return boolean;
   end protected;
end package DataStructures;

package body DataStructures is
   type LinkedList is protected body
      type Item;
      type Ptr is access Item;
      type Item is record
         Data : integer;
         NextItem : Ptr;
      end record;

      variable Root : Ptr;

      procedure Push(Data : in integer) is
         variable NewItem : Ptr;
         variable Node : Ptr;
      begin
         NewItem := new Item;
         NewItem.Data := Data;

         if Root = null then
            Root := NewItem;
         else
            Node := Root;
            while Node.NextItem /= null loop
               Node := Node.NextItem;
            end loop;
            Node.NextItem := NewItem;
         end if;
      end;

      impure function Pop return integer is
         variable Node : Ptr;
         variable RetVal : integer;
      begin
         Node := Root;
         Root := Root.NextItem;

         RetVal := Node.Data;
         deallocate(Node);

         return RetVal;
      end;

      impure function IsEmpty return boolean is
      begin
         return Root = null;
      end;
   end protected body;
end package body DataStructures;

Running the Test

When executed in ModelSim, the console displays:

# ** Note: Pushing 1
# ** Note: Pushing 2
# ** Note: Pushing 3
# ** Note: Pushing 4
# ** Note: Pushing 5
# ** Note: Popping 1
# ** Note: Popping 2
# ** Note: Popping 3
# ** Note: Popping 4
# ** Note: Popping 5

The output confirms that the list correctly stores and retrieves values in FIFO order.