Linked List Implementation in ASIC – ANSI C

In Linked List Implementation in ASIC, overview of dynamic memory allocation in ASIC was presented. This article further explains the need for Linked List and provides foundation for software implementations for Linked List. Also, a migration path from very dynamic linked list implementation to some-what static implementations of Linked List is explained. A typical pointer based Link List implementation in ANSI C is described and later, an array based link list software implementation is explained.

One of the most common data structures used in C is the single linked list. The single linked list is a convenient way to store an unknown amount of data array. The disadvantage of the linked list is that data can only be accessed sequentially and not in random order and also there can be significant overhead. Lets start with following problem statement:

There is random number generator and for an arbitrary application, we need to calculate random numbers which are divisible by 2, 3, & 5 and store them in respective queue. It is already known that there is data set of 50K intergers.

Now if we want to implement above using Arrays, we have to define 3 arrays, one for storing numbers divisible by 2 and so on… Size of each array has to be 50K each as it is not known that how numbers are going to be distributed across all three arrays. Since all numbers can go into one queue in worst case, Memory required is 150K (=3*50K).

By using linked list, we can reduce above requirement to 100K because all combined queues will have 50K data and for each data, there is a link pointer overhead so total memory is 2*50K.  For an application, which requires many lists and/or big record size, above difference can be more significant. A great tutorial on Linked List is available on Stanford Univ. as well and can be read here.

A linked list usually consists of a root or start node, allocated on the stack (an ordinary C variable) and one or more records (or node), allocated on the heap (by calling malloc). The record has two parts, the link or pointer field to the subsequent record and the data field[s] containing the information you want stored in the linked list. The end of the linked list can be indicated by setting the link field to NULL.

 

linklist00

 

A structure is defined to represent each node in Linked List. A Linked List node definition consists of  two parts, one is the information itself and another is pointer to next node (in this case, next record is of same structure type).

 typedef struct node_def { 
 			int number;  
 			struct node_def *next; 

                    } node;

// Start Pointer

node* startPtr; 

Because the new datatype is needed to define the link's datatype before the definition is complete, it is necessary to define the structure first. Since each structure can be accessed by next pointer of previous structure (or start pointer of Linked List), each record must be allocated on the heap by using malloc. When this structure/record is not needed, the memory that held it must be freed for performance reasons. To free a memory, ANSI C provides a function, called free. (See  Dynamic Memory Allocation Performance for added details on malloc/free and related performance considerations) 

Leave a Reply

Your email address will not be published. Required fields are marked *