Published: , Last updated: Jan 14th, 2022

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/Questa 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/Questa 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.

      18 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
      4. Hi Jonas,

        Is the Root ptr not required to be initialized to null (as added, below, to your example), so that the list is empty upon creation?

        Since your example didn’t include initialization, does this mean that the VHDL standard specifies that the initial value of an access types is to be null? Or is this simulator dependent?

              -- Root of the linked list
              variable Root : Ptr := null;
        
        Posted on February 21, 2022 at 2:13 pm
        1. It should be null initially in any simulator, but it doesn’t hurt to be explicit. 🙂 Not everybody knows that the VHDL language reference manual says that: “The null
          value of an access type is the default initial value of the type.”

          Posted on February 21, 2022 at 4:08 pm
      5. Nice post, liked it a lot.

        In the example, Data is always integer.

        If I would need several linked lists for several data types, I would haveto rewrite several times the same code but changing the Data integer to a different one.

        Is there any way to have a linked list code that would work for any type, not only integer?

        Posted on March 1, 2022 at 11:38 pm
        1. Yes, you can use package generics to store any data type in the list. The package declaration would look something like this:

          package generic_list is
          
            generic(type data_type);
          
            type generic_list is protected
                ...
            end protected;
          end package;
          

          But you can’t use this list directly in your testbench because the data_type generic must be given a specific value. You can do that by creating a new VHDL package for each type you want to store.

          For example, create an integer_list.vhd file with this content:

          package integer_list is new work.generic_list
            generic map(integer);
          

          Then you can import the new integer list package in your main testbench and create an object from it:

          use work.integer_list.all;
          
          entity my_tb is
          end my_tb;
          
          architecture sim of my_tb is
          
            shared variable list : generic_list;
          

          Read more in the Generic list – User manual.pdf which you can download from here:
          VHDL package: Generic list of protected type

          Posted on March 2, 2022 at 7:49 am
      6. Hello Jonas,

        Thanks very much for all your succinct VHDL posts. Learning a lot. I am new to OOP. Mainly a Verilog/SystemVerilog/Assertions/VHDL design engineer. Hence, my questions are very basic and hope they make sense.

        In the push procedure or pop function, what is “Node”? Which part of linked list is Node?

        Also,
        In the push procedure, if Root is null, then Root points to the same address where NewItem is pointing to “Root := NewItem;” . Pointer address is copied, not the data at the pointer. Correct? If Root is not null, then we do “Node := Root”. So, now the Node pointer is pointing to where the Root is pointing to (I consider this assignment as copy of the pointer and not the data pointed to). In that case, why can’t you have (since Node and Root are pointing to the same address location).

                    while Root.NextItem /= null loop
                       Root:= Root.NextItem;
                    end loop;
         
                    Root.NextItem := NewItem;
        

        Also, could you please explain the pop function? I don’t understand Root := Root.NextItem; Pop pops an Item from the end of the list. So, don’t understand this Root assignment. Also, what if Root is null when you try to pop?

        Bear with me if my terminology/explanation does not make sense. Very new to OOP.

        Thanks very much.
        Ashok
        p.s. Maybe you can create a paid advanced post on OOP aspects of VHDL. Access Type, Protected Types, Linked List etc. There isn’t much on web when it comes to OOP and VHDL.

        Posted on March 12, 2022 at 10:44 pm
        1. Hello Ashok,

          It’s nice to hear that you found my blog post to be interesting! Now, let me try to answer your questions.

          In the push procedure or pop function, what is “Node”? Which part of linked list is Node?

          The Node variable is a pointer to an Item record stored in the simulator’s dynamic memory (created at run-time). Below you can see the declaration of the record and Ptr pointer, which is the Node variable’s type.

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

          We use the Node variable in the procedures to traverse the linked list.

          “Root := NewItem;” . Pointer address is copied, not the data at the pointer. Correct?

          Yes, Root and NewItem are now pointing to the same location in the simulator’s dynamic memory.

          why can’t you have (since Node and Root are pointing to the same address location).


          while Root.NextItem /= null loop
          Root:= Root.NextItem;
          end loop;

          Root.NextItem := NewItem;

          We can’t do that because then we overwrite the pointer to the start of the list. Yes, we can insert the new item as the last position, but then Root is pointing to the last item, and we cannot access the first element. Root is always supposed to point to the oldest element in the list.

          Also, what if Root is null when you try to pop?

          If you try to pop when Root is null you get a null pointer error in the simulator. The user of the list should always call the IsEmpty function before popping.

          If you want to make it even more verbose, you can add an assertion at the beginning of the Pop function. Something like this:

          assert Root /= null
            report "Pop attempt while the list is empty"
            severity failure;
          
          Posted on March 13, 2022 at 1:05 pm
          1. Hi Jonas,

            Thanks very much for the explanation. Fog is clearing.

            Last question though. In the Pop function, you have

            [vhdl]
            Node := Root;
            Root := Root.NextItem;

            RetVal := Node.Data;
            [\vhdl]

            As I understand, you are assigning Node := Root meaning Node is now pointing to the start of the list and Root is assigned to the next (second) item in the list. Then when you call Pop again, Root points to the second item which is assigned to Node and Node extracts value from the second item. My question is, this looks like we are popping values from the start of the list. I had thought that we should be popping from the end of the list (FIFO).

            Thanks again for your help.
            Ashok

            Posted on March 13, 2022 at 4:56 pm
            1. Hello Ashok,

              Yes, you can pop from any side of the list. As long as you insert at the other end it will behave as a FIFO. If you push to and pop from the same end, it will be a stack.

              It comes down to personal preference if you want the oldest element to be at the root or not.

              Posted on March 20, 2022 at 4:58 am
      7. Hi Jonas.

        How would you write a function for the protected type to return a pointer to the root of list for the purpose of “copying” the list?

        If a PTR type is returned from such a function, this means that the PTR type has to be defined in the declarative part of the protective type, which isn’t allowed.

        Posted on April 7, 2022 at 7:55 am
        1. Hello Paul,

          That wouldn’t work because you can’t return an access type (pointer) from a protected type method.

          Posted on April 13, 2022 at 6:06 am
          1. OK, thanks Jonas.

            Posted on April 13, 2022 at 12:54 pm