How to implement the linked-list process using class concepts in systemverilog !!

Question

Hello Folks,

I frequently hear this like, how do you implement the linked-list process using class in SV. I responded back saying we have similar process using queue etc. but still it would be great if someone can share the concept or piece of code implementing the linked-list using SV class process. [This is not from the point availability of process but from the technical talk point of perspective].

Thanks,
Desperado

Answer 1

dave_59

Forum Moderator

10501 posts

August 09, 2015 at 5:32 pm

http://cslibrary.stanford.edu/103/LinkedListBasics.pdf

A queue can pretty much do anything a linked listed can do, and more efficiently. The only case where a linked list might be more efficient is when you need to join two lists together, or insert one list in the middle of another list. A queue is very efficient for adding one element at a time.

— Dave Rich, Verification Architect, Siemens EDA

Answer 2

desperadorocks

Forum Access

170 posts

October 09, 2016 at 12:34 am

Hello All,

I tried this piece of code and I am able to add element to the head, but when I tried to print the complete link list, the last node is not pointing to the null and I am stuck in the while loop. Any comments ?

module link_list;
 
class node_class;
 int la;
 static node_class nc_next; 
endclass: node_class 
 
class list_class;
 int ll;
 static node_class head;
 
 // function new();
 //    head = new();
 // endfunction: new
endclass: list_class
 
 
// function create_list(list_class lc);
function list_class create_list();
  list_class llc;
  llc = new();
  //  lc = llc;
  return llc;
endfunction: create_list
 
function void add_node_at_header(list_class nlc, int val);
 node_class nnc;
 nnc = new();
 
 nnc.la = val;
 if (nlc.head == null) begin 
   $display("nlc.head==null",nlc.head);
   nnc.nc_next = null;
   nlc.head = nnc;
 end
 else begin
 nnc.nc_next = nlc.head;
 nlc.head = nnc;
 $display("add_node_at_header",nlc.head);
 // nnc.nc_next = null; 
 end
 
 $display("nnc.nc_next", nnc.nc_next);
endfunction: add_node_at_header
 
function void print_full_list(list_class plc);
 node_class tmp_next;
 tmp_next = plc.head;
 $display("print_full_list", plc.head, tmp_next, tmp_next.nc_next);
 
 while (tmp_next.nc_next != null) begin
  $display(tmp_next.la);
  $display(tmp_next);
  $display(tmp_next.nc_next);
  tmp_next = tmp_next.nc_next;
 end 
endfunction: print_full_list
 
initial begin
  list_class new_ll;
  $cast(new_ll, create_list());
  $display(new_ll);
  $display(new_ll.head);
 
  new_ll.ll = 5;  
  add_node_at_header(new_ll, 10);  
  $display(new_ll.head.la);
 
  add_node_at_header(new_ll, 20);  
  $display(new_ll.head.la);
 
  $display(new_ll.head);
  print_full_list(new_ll);
end
 
endmodule: link_list

Answer 3

Solution

dave_59

Forum Moderator

10501 posts

October 09, 2016 at 10:06 am

In reply to desperadorocks:
The problem is you declared nc_next as a static class variable. So after you call add_node_at_header() nc_next is no longer null.

A few other comments on your code.

There is no need for a separate list_class. Just declare a node_class head variable. You might have multiple lists, and will want multiple header variables.
You should make your functions as methods of your node class instead of stand alone functions. It will make things easier to manage as you will eventually want to parameterize the data in your linked list.
It helps if a list starts with an empty node. That way your add_node method can your at any position in the list, not just the header. Other method will benefit for that as well.

module link_list;
 
class node_class;
 int la;
 node_class next;
   virtual function void print_node;
      $write(la," ");
   endfunction
   virtual function void print_list();
      print_node();
      if (next != null)
	next.print_list();
      else
	$write("\n");
   endfunction
   virtual function void insert_node(int val);
      node_class node = new;
      node.la = val;
      node.next = next;
      next = node;
   endfunction : insert_node
 
endclass: node_class 
 
initial begin
  node_class head;
   head = new();
   head.la = 0;
   head.print_list();
   head.insert_node(10);
   head.print_list();
   head.insert_node(20);
   head.print_list();
   head.next.insert_node(30);
   head.print_list();
end
 
endmodule: link_list

— Dave Rich, Verification Architect, Siemens EDA

Answer 4

desperadorocks

Forum Access

170 posts

October 09, 2016 at 12:18 pm

Thanks a lot Dave for the clarification and idea. I just tried appending some more code this for adding node at the end and inserting node in-between.

module link_list;
 
class node_class;
 int la;
 static int node_count=0;
 
 node_class next;
   virtual function void print_node;
      $write(la," ");
   endfunction
   virtual function void print_list();
      print_node();
      if (next != null)
	next.print_list();
      else
	$write("\n");
   endfunction
 
   virtual function void insert_node(int val);
      node_class node = new;
      node.la = val;
      node.next = next;
      next = node;
      node_count++;
   endfunction : insert_node
 
   virtual function void insert_node_end(int val);
     node_class tmp;
 
     node_class node = new;
     node.la = val;
 
     tmp = next;
 
     if (tmp == null) begin
      node.next = next;
      next = node;
     end 
     else begin
      while (tmp.next != null) begin
       tmp = tmp.next;
      end
      node.next = tmp.next;
      tmp.next = node;
     end
     node_count++;
   endfunction: insert_node_end
 
   virtual function void insert_node_index(int index, int val);
     int node_count_tmp=1;
     node_class tmp;
 
     node_class node = new;
     node.la = val;
 
     tmp = next;
 
     if (index > node_count) $write("Index %0d Is Beyound Node Count. Insert Proper Index Value\n", index);
     else begin
       while (node_count_tmp != index) begin
         node_count_tmp++;
         tmp = tmp.next;
       end
       node.next = tmp.next;
       tmp.next = node;
     end
   endfunction: insert_node_index 
 
endclass: node_class 
 
initial begin
  node_class head;
   head = new();
   head.la = 0;
   head.print_list();
   head.insert_node(10);
   head.print_list();
   head.insert_node(20);
   head.print_list();
   head.next.insert_node(30);
   head.print_list();
   head.insert_node_end(40);
   head.print_list();
 
   head.insert_node_index(1, 50); 
   head.print_list();
end
 
endmodule: link_list

Answer 5

DhavalP

Full Access

17 posts

August 18, 2020 at 7:13 pm

In reply to dave_59:

Hi Dave,

Can you please explain me the concept of taking handle of class in the same class?

node_class next;

Answer 6

dave_59

Forum Moderator

10501 posts

August 18, 2020 at 11:49 pm

In reply to DhavalP:

You might want to take a look on my class on classes.

— Dave Rich, Verification Architect, Siemens EDA

Answer 7

egorman44

Forum Access

8 posts

October 03, 2020 at 6:42 am

In reply to dave_59:
Hi Dave, have a question regarding the expresion in insert_node():

node.next = next; // What is the purpose?!

As I understand the current node has a NULL in the next variable and you just assign this NULL to the created node via this assignment. Is it not easier to assign directly NULL here:

node.next = NULL;

Or maybe there is another hidden meaning?

Answer 8

dave_59

Forum Moderator

10501 posts

October 03, 2020 at 10:47 am

In reply to egorman44:

Only the last node in the linked list will have next set to null.

Think about a line of people with their right hand pointing to the next person in line. If someone wants to cut into the line where you are standing, that person will now have to point to the person you were pointing to, and now you point to the new person, that person is the node just constructed.

— Dave Rich, Verification Architect, Siemens EDA

Languages & Standards

Methodologies

Techniques & Tools

Universal Verification Methodology (UVM)

Featured Courses

Additional Courses

Formal-Based Techniques

Analog/Mixed Signal

UVM Forum

SystemVerilog Forum

Coverage Forum

Additional Forums

Implementation Patterns

Specification Patterns

Pattern Resources

UVM Cookbook

Coding Guidelines & Deployment

Coverage Cookbook

Featured & On-Demand

On-Demand Library

Recording Archive

Conferences & WRG

Siemens EDA Learning Center

Blog & News

Verification Horizons Publication

About Us

Training

Solution

Portfolio

Explore

Siemens

Contact