Linked list length

This is a discussion on Linked list length within the C++ Programming forums, part of the General Programming Boards category; I am continuing to put together this project and was a little confused on getting the length of my list. ...

  1. #1
    Registered User
    Join Date
    Jul 2008
    Posts
    80

    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

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    22,274
    I thought u had to traverse a list and then count how many times it goes through.
    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.

    At the moment your length() member function does not appear to be doing anything related to computing the length of the list.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Registered User
    Join Date
    Jul 2008
    Posts
    80
    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.

  4. #4
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    When posting code, perhaps you could make an attempt to compile the code first. What's 5 got to do with things? If you already know how many items there is in the list, then you can just return 5, can't you? Perhaps you can find a different loop setup that works better for counting things in a linked list. Also, "I" is a different variable from "i".


    The new code is indeed somewhat closer, but broken in the above two (three?) aspects.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  5. #5
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    22,274
    Let's see: you have a singly linked list where you keep track of both the head and the tail of the list. So, just create a pointer that points to the head of the list, advance it until you reach the tail of the list, while counting how many times it advances to pointer to the next item.

    By the way, why do you also have member pointers named first and second, and why do you have a member variable named s?
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  6. #6
    Registered User
    Join Date
    Jul 2008
    Posts
    80
    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.

  7. #7
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    22,274
    Post the smallest and simplest compilable code that demonstrates the problem.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  8. #8
    Registered User
    Join Date
    Dec 2006
    Location
    Canada
    Posts
    3,183
    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.

  9. #9
    Registered User Kernel Sanders's Avatar
    Join Date
    Aug 2008
    Posts
    61
    Quote Originally Posted by cyberfish View Post
    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)?

  10. #10
    Registered User
    Join Date
    Dec 2006
    Location
    Canada
    Posts
    3,183
    because there is no way to know the length of the two segments after splitting, except counting them.

  11. #11
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,762
    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

  12. #12
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    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.

  13. #13
    Registered User
    Join Date
    Dec 2006
    Location
    Canada
    Posts
    3,183
    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.

  14. #14
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Unknown memory leak with linked lists...
    By RaDeuX in forum C Programming
    Replies: 6
    Last Post: 12-07-2008, 04:09 AM
  2. linked list question
    By mikeman in forum C Programming
    Replies: 1
    Last Post: 11-30-2008, 01:56 PM
  3. Sorting linked list please help with CODE
    By scarlet00014 in forum C Programming
    Replies: 3
    Last Post: 09-28-2008, 12:24 AM
  4. linked list inside array of structs- Syntax question
    By rasmith1955 in forum C Programming
    Replies: 14
    Last Post: 02-28-2005, 05:16 PM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 11:21 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21