CODEWITHSUNDEEP
c++linked-list
Salar
Salar

Reputation: 269

size of linked list in c++ function

Can someone please tell what is the code for checking the size of a linked list(number of nodes).This is what my code is(inserting nd deleting head + printing info of all nodes)

struct node 
{
    int info;
    node *nextptr;
};

class list
{
private:
    node *L,*tail;
     int count;

public:
    list()
    {
        L=tail=NULL;
        count=0;
    }

    void InsertHead(int info);
    int RemoveHead();
    void Print();
};

Upvotes: 0

Views: 45374

Answers (5)

Greg Domjan
Greg Domjan

Reputation: 14095

Try this:

int size() { return count; }

Upvotes: 0

SingleNegationElimination
SingleNegationElimination

Reputation: 156148

There are two ways to manage the size of a linked list, both have shortcomings. The simplest is to manage a count variable, your class has such a variable, and you increment it every time you add a node to the list, and decrement it every time you remove a node.

In this case, you can get the size of the linked list in constant time. The downside is that a useful operation, splice, where you take a list and cut it into two smaller lists somewhere in the middle, becomes linear complexity, because now you have to count how many nodes are in the sublists.

If you want splice to be constant, then you can't track the size of the lists. So any time you want to get the size of the list, you have to count how many nodes are there.

Upvotes: 7

AndersK
AndersK

Reputation: 36082

Well the simplest would beto add in the function InsertHead add ++count and in the RemoveHead do --count

Otherwise you could use a loop to go through the list

e.g.

node* p = L; 
while (p != NULL) 
{ 
  ++count; 
  p = p->nextptr; 
}

Upvotes: 6

Andrew Cooper
Andrew Cooper

Reputation: 32576

Something like:

int Count()
{
    return count;
}

Upvotes: 0

dutt
dutt

Reputation: 8209

You need to create a counter and then loop through your list increasing the counter

pseudocode:

count = 0
iterator = head
while(iterator != 0)
    count++
    iterator = iterator.next

Upvotes: 1

Related Questions