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.
- Hard coding the node class and connect the node one by one
- Coding the node class and insert the next node using the class function
- Using the SystemVerilog built-in list package
This is to build a node class, and connect the link one by one.
//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
I got this idea from a post contributed by Dave Rich on Verification Academy. The link can be found here.
//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
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!
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);
Hi Alok,
Thank you for reading and pointing the typo out. Really appreciated it.