Thread: Linked list length

I am continuing to put together this project and was a little confused on getting the length of my list. I thought u had to traverse a list and then count how many times it goes through.

length() is the one i was trying to use to count the things in the list (head->item)

header file

Code:

struct node
{
       char item;
       node *next;
};


class Newstring
{
      public:
      char display() const;
      
      int pointers();
      
      int length();
      
      private:
      char s;
      node *head;
      node *first;
      node *second;
      node *last;
      
      };

Code:

#include "4dot6.cpp"



char Newstring::display()const
{
     char s='s';
     cout << s << endl;
     return s;
     }


int Newstring::length()
{
    head->item='a';
   first->item='v';
   second->item='e';
   last->item='d';  
     
   head->next=first;
   first->next=second;
   second->next=last;
   last->next=NULL;
   
   while(head->next!=NULL)
   { 
   cout << head->item << endl;
   head=head->next;
}
   }


int main()
{
    
    Newstring a;
   a.display(); 
   a.length();
    
    system("pause");
    return 0;
    
}

the

the things i have tried in the code above and stuff that i havent included hasnt been working. It just makes the dos screen flicker a quick second and thats it.

I have tried for length()

Code:

for (int i=0 ; i <5 ; head->next != NULL)
{
   head=head->next;
  I++;
}

I am looking for it to do something like starting from head, then make head= head->next (first) then head=head->next (making it second) and so on. and each time that it goes thru it will count until head-> next=NULL. Is there something I am not seeing? I tried a while statement and it does the same thing.

this one just flashes the dos prompt really quick and thats it.

Code:

while(head->next!=NULL)
   { 
   cout << head->item << endl;
   head=head->next;
cout << "something" << endl;

my intentions are
while head->next is no NULL make the current head = to heads next (first) and move on in the list.

or is it needed to make head==head->next?
even trying to print out the somethings to see how many are in the list doesnt work.

That is one option. Another option would be to keep a running count of the number of elements in the list as they are added and removed.

Just to add on to that -
Keeping a count of number of elements incrementally makes the length() function O(1), however, it makes the "split" (split a list into two) function O(n).

Without keeping a count, length() function will be O(n), while the "split" function will be O(1).

Which approach is better is dependent on usage pattern.

Originally Posted by cyberfish

Just to add on to that -
Keeping a count of number of elements incrementally makes the length() function O(1), however, it makes the "split" (split a list into two) function O(n).

Without keeping a count, length() function will be O(n), while the "split" function will be O(1).

Which approach is better is dependent on usage pattern.

Why would a counter bump split up to O(n)?

because there is no way to know the length of the two segments after splitting, except counting them.

Er, well that would be true in any case, but because split would need to update the new count variables in the shorter lists, it executes an O(n) operation. If you were to instead calculate length exactly when you need it, it's easier to amortize it.

Just being explicit cyberfish

I don't see how you are going to be able to split a link list in O(1) as you have to transverse the array to the split point in order to do the split.

Yeap, I was referring to the need to initialize those count variables for the two segments. Thanks for clarifying. Like citizen pointed out, I think it would be a better solution to delay the counting to the moment it's actually needed. Perhaps reserve a special value for "count" that means "unknown" for lists that don't start with a length of 0? And it can be given a value when the list is first counted, then updated incrementally.

I don't see how you are going to be able to split a link list in O(1) as you have to transverse the array to the split point in order to do the split.

What I had in mind is splitting given a pointer to an element.

Even given that you still need to go to the previous element to properly end it. And from what I glanced at before it seems we are talking about a single linked list.

The length issue is one reason I don't work on the link list itself but instead go through a container object that contains the list and all other important information about it.