CODEWITHSUNDEEP
clistdoubly-linked-listcircular-list
nj2237
nj2237

Reputation: 1278

Interpreting the loop condition of custom circular doubly linked list

I have a list inside a structure,

struct A{
    list B;
};

I also have a pointer to this structure like

struct A *a;

Now, assume the list is already implemented, and its elements are of type elem.

Then, I do the following -

(i) I get the head of the list in nodeL (a pointer of elem type)

elem * nodeL = list_get_head(&(a->B));

(ii) I now loop through the list in this way:

while(nodeL != (elem *)(&a->B)){ // did not get this part ----- I
    ; //some code here
    nodeL = list_get_next(&(a->B), nodeL);
}

Assume that list_get_head gets the pointer to head of list, and list_get_next gets the pointer to next element of passed second argument elem, of list.

Now my question is:

  1. What is my loop condition here? Till what of list do I hope to loop? (see I) In other words, if &(a->B) is the address of the start of the list, what is &a->B here?

I thought this should loop till end of list, but it doesn't seem like that's what the while loop condition is doing. Also, this is a circular doubly linked list.

Upvotes: 0

Views: 89

Answers (3)

Aconcagua
Aconcagua

Reputation: 25536

elem* x = list_get_head(&a->B);
elem* y = (elem *)(&a->B);

First at all, how far do x and y differ in your case?

To be valid at all, first member of list must be of type elem* anyway. I personally would assume that this is the head of the list, but then your while loop won't ever be entered, so it must rather be the tail??? But then your first element considered in the loop is the tail...

How is an empty list represented? Null pointer? If so, this is not covered by your code.

while(nodeL != (elem *)(&a->B))

did not get this part

Idea is simple: we start iterating at the head, and as long as the head is not reached again, we are still in the loop... Problem is, though, you have to distinguish two situations:

  1. current node is head at start of the loop
  2. current node is head after all elements have been iterated

I recommend different handling for iterating now:

elem* nodeL = list_get_head(&a->B);
if(nodeL) // based on assumption(!): otherwise, empty list
{
    do
    {
        //some code here
        nodeL = list_get_next(&a->B, nodeL);
    }
    while(nodeL != list_get_head(&a->B));
}

One element is guaranteed to be in the list, so we can use it unconditionally (thus a do-while loop). Then we iterate to the next element, until we reach the beginning again. I replaced the suspicious cast by another call to list_get_head, making the whole matter safer (not relying on assumptions any more either).

Upvotes: 2

Shashank Singh
Shashank Singh

Reputation: 657

Suppose you have a variable and a pointer of the structure:

A var;
A* pntr;

Now to access a data member of the structure we do the following :

var.B    // For a variable use dot 
(*pntr).B or pntr->B    //For a pointer we can use * . or ->

In your code while(nodeL != (elem *)(&a->B)) iterates over the list till the head of the circular list is encountered again.

We can get head by :

A* a;
//SOME INITIAL CODE
A* pntr;
pntr = a;
head = (elem*)&(pntr->B)

So look at the look like:

while( nodeL != (elem *) ( & ( a->B ) ) )

Upvotes: 1

Mohammad Azim
Mohammad Azim

Reputation: 2943

It is not clear if you are talking about std::list. But since you are mentioning unfamiliar list_get_head and list_get_next, I assume this is a non standard implementation.

So the guess is: In a list head is also an element. The condition while(nodeL != (elem *)(&A->B)) looks like it is checking when loop traverses back to the head of the circular list.

However, there are two observations:

  1. Elements of a list are generally allocated from heap or a memory pool. Hence, if B is head, it should have been a pointer. Unless it is typedef elem * list.

  2. The loop may not run because nodeL is already at head.

Upvotes: 1

Related Questions