3 Ways to Build a Linked List Using SystemVerilog

Hi! It has been a while. Darn holiday seasons. I lost all my little productivity in the past two months. It’s time to get some work done. Today I want to talk about how to build a linked list using SystemVerilog. Linked lists are widely used in programming. However, it’s less commonly seen in HDLs like SystemVerilog. I would like to introduce 3 ways to implement it in SystemVerilog, which are all I can think of. Coding the node class and connecting and nodes, coding the node class and inserting the following node, and using the SystemVerilog built-in linked list package. Let me know if you can come up with other methods to implement a linked list.

 

  1. Hard coding the node class and connect the node one by one
  2. This is to build a node class, and connect the link one by one.

    program linked_list;

     //Construct the node class
     class Node;
       int data;
       Node next;

       virtual function set_data(int data);
         this.data = data;
       endfunction

       virtual function print_data();
         $dispaly("the data is %d", data);
       endfunction

       virtual function link_node(Node next);
         this.next = next;
       endfunction

     endclass

     initial begin

       //create new nodes
       Node NodeA = new();
       Node NodeB = new();
       Node NodeC = new();

       //Set data value for the nodes
       NodeA.set_data(1);
       NodeB.set_data(2);
       NodeC.set_data(3);

       //Link the nodes
       NodeA.link_node(NodeB);
       NodeB.link_node(NodeC);

       //Print out each node's value using the next link
       NodeA.print_data();
       NodeA.next.print_data();
       NodeA.next.next.print_data();

     end
     
    endprogram

     

  3. Coding the node class and insert the next node using the class function
  4. I got this idea from a post contributed by Dave Rich on Verification Academy. The link can be found here.

    program linked_list;

     //Construct the node class
      class Node;
        int data;
        Node next;

        virtual function print_node();
          $write(data, " ");
        endfunction

        virtual function insert_node(int data);
          Node node = new();
          node.data = data;
          node.next = next;
          next = node;
        endfunction

        virtual function print_list();
          print_node();
          if(next != null)
            next.print_list();
          else $write("\n");
        endfunction

      endclass

      initial begin
        Node = head new();
        head.data = 0;
        head.print_list();
        head.insert_node(1);
        head.next.insert_node(2);
        head.print_list();
      end

    endprogram

     

  5. Using the SystemVerilog built-in list package
  6. This is a doubly linked list package, which was first introduced in IEEE 1800-2005, Annex D. You need to include <List.vh> when you plan to use this package. The list and its operators have lots of built-in methods. However, from IEEE1800-2009. the built-in linked list package has been deprecated. A queue is a superior data structure to use, which also comes with lots of built-in methods. 

    I was trying to use the built-in list package, however, the simulator I used doesn’t support this function anymore. 

That’s all for this post. All in all, I rarely build a linked list at work. It’s nice to take a look at this data structure from this angle. Leave me a comment if you have any questions. 

 

Edited on Feb 6th, 2020 to fix a typo in the first approach’s code. Thank Alok for pointing it out!

2 thoughts on “3 Ways to Build a Linked List Using SystemVerilog

  1. hi ,

    in your 1st approach of hard coding node class, the second assignment in link class was supposed to be –
    NodeB.link_node(NodeC);

    instead of your:
    NodeB.link_node(NodeB);

Leave a Reply

Your email address will not be published.