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

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

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.

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 


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

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

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;

In reply to DhavalP:

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

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?

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.