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

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

 

2. Coding the node class and insert the next node using the class function

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

 

3. Using the SystemVerilog built-in list package

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!