The linked list is a dynamic data structure. A linked list can be used when the total number of elements is not known in advance. It grows and shrinks in memory, relative to the number of items it contains.

Linked lists are most conveniently implemented using classes in an object-oriented programming language. VHDL has some object-oriented features which can be used for abstracting away the complexity of the implementation from the user.

In this article we are going to use access types, records, and protected types to implement a linked list in VHDL. We are going to create a new VHDL package where we will write all of our linked list code.

Package

The first thing we will do is to declare a package which will contain our code. A VHDL package is a collection of types, objects, or subprograms that can be imported into another VHDL file. Most VHDL modules import the std_logic_1164 package from the IEEE library. We are creating our own package, much like it.

The contents of our new DataStructures.vhd file:

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

Even though the package only will contain the linked list implementation, we will future-proof it by naming it DataStructures. One could easily imagine that someone would want to add other data structures like trees or hash maps to it later.

A package consists of two parts; a declarative region, and a body. The declarative region is where you put everything that should be visible to the users of the package. The body is privately scoped, and not accessible from the outside.

Need the ModelSim project files?

Let me send you a Zip with everything you need to get started in 30 seconds

How does it work?

Tested on Windows and Linux Loading Gif.. How it works

    Unsubscribe at any time

    Protected type

    Protected types are class-like constructs in VHDL. They can contain subprograms, type declarations, and variables. A protected type consists of a public declaration and a private body. We will add the declaration to the package declaration, and the body to the package body.

    Our DataStructures.vhd file after adding the protected type:

    package DataStructures is
    
       type LinkedList is protected
    
          -- Prototypes of subprograms
          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;
    

    We named the protected type LinkedList because it will contain everything related to the linked list. If we were to add another kind of data structure to the package, that would mean another protected type.

    Within the declarative region of the protected type, we have declared three subprograms. There is no implementation yet, we will come to that later. For the subprograms to be visible outside of the protected type, they have to be declared here.

    The three subprograms are the standard linked list methods: Push, Pop, and IsEmpty. Push adds a new element to the start of the list. Pop removes an element from the end of the list. IsEmpty is a utility function that returns true if the list is empty.

    Record

    A record is a composite type that may contain multiple member types. It works kind of like a struct in the C programming language. When a signal or variable is created from the record type, the data members can be referenced by using the “.” notation. For instance MyItem.Data.

    Our record declaration within the body of the protected type:

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

    We have declared the record type in the body of the protected type. The declarative region of a protected type cannot contain other type or signal declarations, so we have to declare them in the protected type body.

    That’s not a problem for us because Item is an internally used type. It doesn’t need to be visible from the outside. The user of the linked list should access it only through the three publicly declared subprograms.

    Our record contains two data members; Data and NextItem. While Data is of type integer, NextItem is of the, for now, mysterious Ptr type.

    Access type

    Access types are VHDL pointers. By using them, we can dynamically create objects during run-time. We will declare a new access type named Ptr that will point to a dynamically created object of the Item type.

    The package body with the new access type added:

    package body DataStructures is
    
       type LinkedList is protected body
    
          -- Declaration of incomplete Item type
          type Item;
    
          -- Declaration of pointer type to the Item type
          type Ptr is access Item;
    
          -- Full declaration of the Item type
          type Item is record
             Data : integer;
             NextItem : Ptr; -- Pointer to the next Item
          end record;
    
          -- Root of the linked list
          variable Root : Ptr;
    
    end package body DataStructures;
    

    A linked list node needs to contain a reference to the next node in the list. We have implemented this in the Item record with the NextItem member. It is of type Ptr, which in turn is a pointer back to the Item type. To avoid this chicken/egg problem, we first declare Item as an incomplete type. Then, we declare the Ptr type as a pointer to the incomplete type. Finally, we specify the full declaration of the Item type.

    The last thing we did was to declare a new variable named Root of type Ptr. This will be the root of the linked list. If the list is empty, the value of Root will be null. Otherwise, it will point to the first item in the list.

    Linked list methods

    It is now time to implement the subprograms that we declared in the declarative region of the protected type. They were the Push procedure, and the two impure functions: Pop and IsEmpty.

    We will place the implementation of the subprograms within the body of the protected type.

    Push

    Push is the only one of the subprograms which is a procedure. Functions in VHDL require a return value that cannot be omitted. To avoid using a dummy return value, a procedure is preferable.

    The Push procedure:

    procedure Push(Data : in integer) is
       variable NewItem : Ptr;
       variable Node : Ptr;
    begin
       -- Dynamically allocate a new item
       NewItem := new Item;
       NewItem.Data := Data;
    
       -- If the list is empty, this becomes the root node
       if Root = null then
          Root := NewItem;
    
       else
          -- Start searching from the root node
          Node := Root;
    
          -- Find the last node
          while Node.NextItem /= null loop
             Node := Node.NextItem;
          end loop;
    
          -- Append the new item at the end of the list
          Node.NextItem := NewItem;
       end if;
    end;
    

    The first thing that happens is that a new object of type Item is dynamically allocated. This is done by using the new keyword. Every time the new keyword is used, dynamic memory is consumed by the simulator.

    The rest of the code is just a standard linked list algorithm. The new item is appended to the end of the list, or it becomes the Root item if the list is empty. Read up on linked lists on Wikipedia if you need more background.

    Pop

    Pop removes the oldest element from the list and returns it to the caller. If we just remove the reference to the popped element and return it, there will be memory loss in the simulator. After the function call finishes, the reference to the dynamically created object is lost forever.

    There is no garbage collection in VHDL prior to VHDL-2017 (also referred to as VHDL-2018 or VHDL-2019). And VHDL-2017 is unsupported by most simulators. Therefore, we must call deallocate before returning from the function.

    The deallocate operator frees the memory used by a dynamically allocated object. For every call to new, there should be a call to deallocate before the reference to an object is deleted.

    The Pop function:

    impure function Pop return integer is
       variable Node : Ptr;
       variable RetVal : integer;
    begin
       Node := Root;
       Root := Root.NextItem;
    
       -- Copy and free the dynamic object before returning
       RetVal := Node.Data;
       deallocate(Node);
    
       return RetVal;
    end;
    

    After we have called deallocate, we cannot reference the data pointed to by the Node variable. It has been free’d by the simulator. The solution is to copy the data to a local variable before freeing, and then return the value of the variable.

    IsEmpty

    Checking if the list is empty or not can simply be accomplished by checking if the root node points to something other than null:

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

    Testbench

    To run our code, we will need to create a testbench. Actually, the linked list can only be used in testbenches. Access types are not synthesizable, but they are very useful for verification purposes.

    Using a library package

    In the testbench, we first import the work library. This is the default library in VHDL, and this is where our DataStructures package resides. After that, we can import the LinkedList protected type like this:

    library work;
    use work.DataStructures.LinkedList;
    

    Shared variable

    A shared variable is a variable that can be access by several processes. Unlike regular variables which can only be declared within a single process, shared variables can be declared in the declarative region of the architecture. Thus, they have the same scope as signals.

    We have to use a shared variable because it isn’t possible to declare a signal of protected type. If we tried, ModelSim would complain: (vcom-1464) Illegal declaration of signal “List” of type work.DataStructures.LinkedList (type is a protected type).

    We declare the shared variable of type LinkedList in the declarative region of the testbench:

    architecture sim of LinkedListTb is
    
       shared variable List : LinkedList;
    
    begin
    

    The final code for the testbench

    To test our three utility functions, we create a new process. In the process, we add a For-loop that pushes five integers to the linked list. Finally, we empty the linked list in a While-loop that runs until our IsEmpty function returns true:

    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;
    

    The final code for the DataStructures package

    After writing all of the code that we previously talked about in this article, the DataStructures package should look like this:

    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;
    

    Need the ModelSim project files?

    Let me send you a Zip with everything you need to get started in 30 seconds

    How does it work?

    Tested on Windows and Linux Loading Gif.. How it works

      Unsubscribe at any time

      The result

      The output to the simulator console when we press the run button in ModelSim:

      VSIM 10> run
      # ** Note: Pushing 1
      #    Time: 0 ns  Iteration: 0  Instance: /linkedlisttb
      # ** Note: Pushing 2
      #    Time: 0 ns  Iteration: 0  Instance: /linkedlisttb
      # ** Note: Pushing 3
      #    Time: 0 ns  Iteration: 0  Instance: /linkedlisttb
      # ** Note: Pushing 4
      #    Time: 0 ns  Iteration: 0  Instance: /linkedlisttb
      # ** Note: Pushing 5
      #    Time: 0 ns  Iteration: 0  Instance: /linkedlisttb
      # ** Note: Popping 1
      #    Time: 0 ns  Iteration: 0  Instance: /linkedlisttb
      # ** Note: Popping 2
      #    Time: 0 ns  Iteration: 0  Instance: /linkedlisttb
      # ** Note: Popping 3
      #    Time: 0 ns  Iteration: 0  Instance: /linkedlisttb
      # ** Note: Popping 4
      #    Time: 0 ns  Iteration: 0  Instance: /linkedlisttb
      # ** Note: Popping 5
      #    Time: 0 ns  Iteration: 0  Instance: /linkedlisttb
      

      As we can see from the printout, five integers are pushed to the linked list. Then, the While-loop in the testbench pops them from the list in the order that they were inserted.

      Author: Jonas Julian Jensen

      I’m from Norway, but I live in Bangkok, Thailand. Before I started VHDLwhiz, I worked as an FPGA engineer in the defense industry. I earned my master’s degree in informatics at the University of Oslo.

      Leave a Reply

      Your email address will not be published. Required fields are marked *

      This site uses Akismet to reduce spam. Learn how your comment data is processed.

      7 thoughts on “How to create a Linked List in VHDL

      1. Your implementation of Pop() does not match your definition:
        “Pop removes the last element from the list and returns it to the caller.”

        The implementation returns the current root which results in the popped values being in pushed order rather than in reverse.

        Posted on January 18, 2019 at 10:19 pm
        1. You are quite right. I changed the text to “Pop removes the oldest element from the list and returns it to the caller”

          Posted on January 19, 2019 at 6:51 am
      2. Hi Jonas,

        This tutorial has been most helpful in my understanding of a linked list in VHDL.

        For my own implementation in a testbench I would like to use an array of linked lists. However, I cannot get my head around how to write the VHDL for this. I tried to declare a new type as an array of the LinkedList type.

         type ListArray is array (0 to 7) of LinkedList;
         

        This causes an error in the ModelSim compiler: ” An element of a protected type (LinkedList) is not allowed in a composite type”

        Do you have any suggestions on how to create an array of linked lists?

        Posted on November 2, 2020 at 12:52 pm
        1. Hello Filip,

          Arrays of protected type are only possible in VHDL-2019. See the Composites of protected types section in my article about what’s new in VHDL-2019.

          But you can emulate it by creating another protected type in a package. I will make a blog post about that later, but I’m afraid it may be too late for your application.

          Posted on November 8, 2020 at 12:22 pm
          1. Hi Jonas,

            Thanks for your reply.

            I inherited a project where a linked list was created within the architecture of the testbench and not using a package. In this way it seems also possible to create an array of these linked lists. However, readability and maintainability of this code is ‘not optimal’.

            As I was not familiar with linked lists in VHDL at all I did a search on the web which led me to your very helpful site.

            For future projects I’m still very interested in that new blog post!

            Posted on November 24, 2020 at 10:43 am
            1. Hello Filip,

              I investigated this further, and I found it impossible to create an array of protected types.

              The problem is that you can’t create a composite type (like an array or record) containing a protected type. And the object pointed to by an access type cannot be of a protected type.

              Therefore, there’s no way that we can dynamically store a collection of protected type objects. The only way is to explicitly declare N shared variables, as shown below.

              package body protected_t_arr is
              
                shared variable item1 : LinkedList;
                shared variable item2 : LinkedList;
                shared variable item3 : LinkedList;
                -- And so on..
              
                type protected_t_arr is protected body
              

              If you need an array of linked lists, you can modify the original linked list code. You can’t use it as elements in another dynamic list for the reasons I mentioned.

              You can solve it by adding another level of records and pointers, as shown below. You will have to invent some subprograms to manage the new data structure.

              type LinkedListItem;
              type LinkedListPtr is access LinkedListItem;
              type LinkedListItem is record
                 Data : integer;
                 NextItem : LinkedListPtr;
              end record;
              
              type ArrayItem;
              type ArrayPtr is access ArrayItem;
              type ArrayItem is record
                 Data : LinkedListItem;
                 NextItem : ArrayPtr;
              end record;
              
              Posted on December 5, 2020 at 9:43 am
      3. Is there a way to declare data as a void pointer like *void in c? This will allow more flexibility in the data structure.

        Posted on April 22, 2021 at 9:41 pm