Linked List System Verilog

The List package implements a classic list data-structure, and is analogous to the STL (Standard Template Library) List container that is popular with C++ programmers. The container is defined as a parameterized class, meaning that it can be customized to hold data of any type. The List package supports lists of any arbitrary predefined type, such as integer, string, or class object. First declare the Linked list type and then take instances of it. SystemVerilog has many methods to operate on these instances.

A double linked list is a chain of data structures called nodes. Each node has 3 members, one points to the next item or points to a null value if it is last node, one points to the previous item or points to a null value if it is first node and other has the data.

1-10

The disadvantage of the linked list is that data can only be accessed sequentially and not in random order. To read the 1000th element of a linked list, you must read the 999 elements that precede it.

List Definitions:

list :- A list is a doubly linked list, where every element has a predecessor and successor. It is a sequence that supports both forward and backward traversal, as well as amortized constant time insertion and removal of elements at the beginning, end, or middle.

container :- A container is a collection of objects of the same type .Containers are objects that contain and manage other objects and provide iterators that allow the contained objects (elements) to be addressed. A container has methods for accessing its elements. Every container has an associated iterator type that can be used to iterate through the container´s elements.

iterator :- Iterators provide the interface to containers. They also provide a means to traverse the container elements. Iterators are pointers to nodes within a list. If an iterator points to an object in a range of objects and the iterator is incremented, the iterator then points to the next object in the range.

Procedure To Create And Use List:

1. include the generic List class declaration

`include <List.vh>

2. Declare list variable

List#(integer) il; // Object il is a list of integer

3. Declaring list iterator

List_Iterator#(integer) itor; //Object s is a list-of-integer iterator 

List_iterator Methods:

  • The List_Iterator class provides methods to iterate over the elements of lists.
  • The next() method changes the iterator so that it refers to the next element in the list.
  • The prev() method changes the iterator so that it refers to the previous element in the list.
  • The eq() method compares two iterators and returns 1 if both iterators refer to the same list element.
  • The neq() method is the negation of eq().
  • The data() method returns the data stored in the element at the given iterator location.

List Methods:

The List class provides methods to query the size of the list; obtain iterators to the head or tail of the list;
retrieve the data stored in the list; and methods to add, remove, and reorder the elements of the list.

  • The size() method returns the number of elements stored in the list.
  • The empty() method returns 1 if the number elements stored in the list is zero and 0 otherwise.
  • The push_front() method inserts the specified value at the front of the list.
  • The push_back() method inserts the specified value at the end of the list.
  • The front() method returns the data stored in the first element of the list.
  • The back() method returns the data stored in the last element of the list.
  • The pop_front() method removes the first element of the list.
  • The pop_back() method removes the last element of the list.
  • The start() method returns an iterator to the position of the first element in the list.
  • The finish() method returns an iterator to a position just past the last element in the list.
  • The insert() method inserts the given data into the list at the position specified by the iterator.
  • The insert_range() method inserts the elements contained in the list range specified by the iterators first and last at the specified list position.
  • The erase() method removes from the list the element at the specified position.
  • The erase_range() method removes from a list the range of elements specified by the first and last iterators.
  • The set() method assigns to the list object the elements that lie in the range specified by the first and last iterators.
  • The swap() method exchanges the contents of two equal-size lists.
  • The clear() method removes all the elements from a list, but not the list itself.
  • The purge() method removes all the list elements (as in clear) and the list itself.

EXAMPLE:

module lists();
List#(integer) List1;
List_Iterator#(integer) itor;
initial begin
List1 = new();
$display (" size of list is %d \n",List1.size());
List1.push_back(10);
List1.push_front(22);
$display (" size of list is %d \n",List1.size());
$display (" poping from list : %d \n",List1.front());
$display (" poping from list : %d \n",List1.front());
List1.pop_front();
List1.pop_front();
$display (" size of list is %d \n",List1.size());
List1.push_back(5);
List1.push_back(55);
List1.push_back(555);
List1.push_back(5555);
$display (" size of list is %d \n",List1.size());
itor = List1.start();
$display (" startn of list %d \n",itor.data());
itor.next();
$display (" second element of list is %d \n",itor.data());
itor.next();
$display (" third element of list is %d \n",itor.data());
itor.next();
$display (" fourth element of list is %d \n",itor.data());
itor = List1.erase(itor);
$display (" after erasing element,the itor element of list is %d \n",itor.data());
itor.prev();
$display(" prevoious element is %d \n",itor.data());
end
endmodule

RESULT:
size of list is 0
size of list is 2
poping from list : 22
poping from list : 22
size of list is 0
size of list is 4
startn of list 5
second element of list is 55
third element of list is 555
fourth element of list is 5555
after erasing element,the itor element of list is x
prevoious element is 555