CODEWITHSUNDEEP
c++
pigthatatepens
pigthatatepens

Reputation: 31

How to count number of elements in a doubly-linked list?

This is how the list is laid out: 

struct Node {
    Node *next;
    Node *prev;
    T datum;
};

Node *first;   // points to first Node in list, or 0 if list is empty  
Node *last;    // points to last Node in list, or 0 if list is empty

I have tried: 

int i =0;  
while(first->next)
{  
    i++;  
}

but this does not seem right.

Upvotes: 0

Views: 3445

Answers (3)

pwilmot
pwilmot

Reputation: 596

your function needs to loop over the list while updating the pointer to the current node. Something like this : 

function getLen(head) {
    var curNode = head;
    var len = 0;

    while (curNode)
        len++;
        curNode = curNode.next;
    }
    return len;
}

Upvotes: 1

Blastfurnace
Blastfurnace

Reputation: 18652

You can solve this by walking a pointer from node to node until the pointer is NULL. Count the number of times the pointer is non-NULL. The code required is very simple:

int list_size(const Node *ptr)
{
    int size = 0;
    while (ptr) {
        size++;
        ptr = ptr->next;
    }
    return size;
}

Use it like so:

int size = list_size(first);

This code doesn't use the prev pointer so it would also work for a singly-linked list.

Upvotes: 1

Dániel Sándor
Dániel Sándor

Reputation: 1294

Try this.

int i=0;
if(first!=0){
    ++i;
    while(first!=last){
        first=first->next;
        ++i;
    }
}
std::cout<<i<<std::endl;

Upvotes: 0

Related Questions