Pseudocode of an algorithm for doing a breadth-first (level) traversal of a linked list of linked lists

Breadth-First (Level) Traversal of a Linked List of Linked Lists
(Algorithm in Pseudocode)

Node Structures

Example

// parent
struct PNode
{
CNode* data;
PNode* link;
};

// child
struct CNode
{
int data;
CNode* link;
};

Pseudocode (Print Value at Each Node):

if (head == 0) return
create queue q of CNode*
while (head != 0)
   if (head->data != 0)
      q.push(head->data)
   head = head->link;
while ( ! q.empty() )
   cursor = q.front()
   q.pop()
   display cursor->data
   if ( cursor->link != 0 )
      q.push( cursor->link )

Image showing an example linked list of linked lists

Why queue? (What's FIFO about the problem?)

For each level, the child-list nodes involved must be processed in the order in which the respective child lists are encountered in the parent list, i.e., first encountered first to be processed.

Additional clarifications:

■

Initial buffering of the child-list head pointers as they are encountered (while traversing the parent list from beginning to end) in a queue ensures the prescibed processing order for the child-list nodes of the first level.

■

Subsequent buffering (in the same queue) of the child-list head pointers as they are encountered (while processing the nodes pointed to by the head pointers previously buffered) ensures the prescibed processing order for the child-list nodes of the remaining levels.

● Note that the pointer in the link field of node n in an N-node linked list is effectively a head pointer, namely the head pointer of the smaller list consisting of node n+1, node n+2, ... and node N. (This applies also for the case of node N, the null pointer in whose link field is the head pointer of the empty list.)