Thread: Linked lists

  1. #1
    Registered User
    Join Date
    Apr 2008
    Posts
    44

    Linked lists

    Is there a header file for linked lists in c++ or do I have to implement one from scratch.

    I Java you can do:
    LinkedList<String> list = new LinkedList<String>();
    list.add("mike");
    .
    .
    .
    Is there something like that in C++, or we implement fuctions etc by ourselves?

  2. #2
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    #include<list>
    and then use std::list is probably what you are looking for.

    --
    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.

  3. #3
    Registered User
    Join Date
    Apr 2008
    Posts
    44
    Hmmm, it seems that I cannot get an element from a list with something like:
    list(2), or list.at(2)....Could not find anything in cpp reference, am I wrong. Do I really have to use iterator all the time???

  4. #4
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by mixalissen View Post
    Hmmm, it seems that I cannot get an element from a list with something like:
    list(2), or list.at(2)....Could not find anything in cpp reference, am I wrong. Do I really have to use iterator all the time???
    That would be list[2] - but no, if you want a random access "list", then you probably should be using vector instead. Unless you are planning to add/remove data in the middle of the list, then vector is fine.

    --
    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
    Registered User
    Join Date
    Apr 2008
    Posts
    44
    I am using lists just for learning purposes, not for something specific. I am now trying to sort a list<int>, but I am having trouble using the iterator, this is what I have so far:
    Code:
        for(int i = 0;(i <= mylist.size()) &&  flag; i++)
        {
                flag = false;
                for(iter = mylist.begin(); iter != mylist.end(); iter++)
                {
                         if(*++iter< *iter)
                         {
                                    *++iter.swap(*iter);================(1)
                                    flag = true;
                         }
                }         
        }  
    
    'struct std::_List_iterator<int>' has no member named 'swap'
    In (1) I want to to say swap the elements thet the iterator is pointing to but I get this error...Any ideas???

  6. #6
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Code:
    if(*++iter< *iter)
    should probably be
    Code:
    if(*iter+1< *iter)
    And likewise in the swap call.

    Edit: I don't know for sure, but the swap probably needs to be like this:
    Code:
    swap(*iter+1, *iter);
    --
    Mats
    Last edited by matsp; 05-15-2008 at 05:27 AM.
    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.

  7. #7
    Registered User
    Join Date
    Apr 2008
    Posts
    44
    Code:
    if(*iter + 1 < *iter) 
                         {
                                    (*iter + 1).swap(*iter);                               
                                    flag = true;
                         }
    34 C:\Dev-Cpp\list.cpp `swap' is not a type 
    34 C:\Dev-Cpp\list.cpp request for member of non-aggregate type before '(' token
    does not work, this is really becoming a challange...The damn pointers make my life difficult...
    all I want to say is swap the element in location iter +1 with the one in location iter...this is going to be a hard one I guess

  8. #8
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    See my edit in the previous post, and perhaps you need *(iter+1) instead of *iter+1 - adding the extra parenthesis will certainly not hurt.

    --
    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.

  9. #9
    Registered User
    Join Date
    Apr 2008
    Posts
    44
    Actually the above code is REALLY wrong...with *iter + 1 or *iter++ you dont move the iterator, you just increment the value of the element by 1. SO WRONG...

    You were posting while I was posting,, yes that is the case...

  10. #10
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    Dev-Cpp is clearly telling you that there is no member such as swap in std::list.
    There is std::swap, however.
    Just swap the current iterator with the next *iter, (*iter + 1).
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  11. #11
    The larch
    Join Date
    May 2006
    Posts
    3,573
    It seems you are trying to use a list for something it is not good for.

    Firstly, the size() operation is probably too slow to call in a loop (it has to traverse the list and count the nodes). (You could use iterators to control the outer loop too.)
    Secondly, lists can often be sorted more efficiently by reordering the node pointers, rather than swapping the data. Therefore list provides a sort() member function.

    If your aim is to learn how to implement bubble-sort, perhaps a random-access container such as vector would put up less resistance.
    If your aim is to learn the usage of lists, perhaps it would be better to familiarize yourself with the member functions that it has.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  12. #12
    Registered User
    Join Date
    Apr 2008
    Posts
    44
    thanx elysia you were very helpful

  13. #13
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    Dev-Cpp is clearly telling you that there is no member such as swap in std::list.
    Uh, no, that's not what it's saying. It's saying that there's no member swap in std::list::iterator. Seeing as there is a member swap in list, it would be quite wrong to say there isn't.

    Oh, and you can't do it+1 for list iterators. They don't support +.


    Seriously, use a std::vector instead of a std::list.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  14. #14
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by CornedBee View Post
    Seriously, use a std::vector instead of a std::list.
    As I stated in post 4:
    ...you probably should be using vector instead...
    --
    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.

  15. #15
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    Yes, but it needed repeating. And stronger words.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Singly Linked Lists: Clarification Needed
    By jedispy in forum C++ Programming
    Replies: 4
    Last Post: 12-14-2006, 05:30 PM
  2. Linked Lists 101
    By The Brain in forum C++ Programming
    Replies: 5
    Last Post: 07-24-2004, 04:32 PM
  3. Map file formats and linked lists
    By Spitball in forum Game Programming
    Replies: 2
    Last Post: 03-04-2004, 11:32 PM
  4. need help w/ linked lists
    By MKashlev in forum C++ Programming
    Replies: 11
    Last Post: 08-05-2002, 08:57 PM
  5. doubly linked lists
    By qwertiop in forum C++ Programming
    Replies: 3
    Last Post: 10-03-2001, 06:25 PM