List copy semantics efficiency

This is a discussion on List copy semantics efficiency within the C++ Programming forums, part of the General Programming Boards category; This never dawned on me before: Typically ( as far as I know ) people handle linked-list copying by iterating ...

  1. #1
    Use this: dudeomanodude's Avatar
    Join Date
    Jan 2008
    Location
    Hampton, VA
    Posts
    391

    List copy semantics efficiency

    This never dawned on me before:

    Typically ( as far as I know ) people handle linked-list copying by iterating the list, and pushing back the current dereferenced iterator ( at least that's how I've always done it ).

    1) But doesn't that become O(logN)?

    2) Wouldn't iterating the list once and pushing the front, then reversing the order be more efficient ( because isnt' that O( 2 * N )? )

    3) Any other ways you can handle this more efficiently?

    Thanks in advance,

    theDude
    Ubuntu Desktop
    GCC/G++
    Geany (for quick projects)
    Anjuta (for larger things)

  2. #2
    Use this: dudeomanodude's Avatar
    Join Date
    Jan 2008
    Location
    Hampton, VA
    Posts
    391
    I'll also throw out there:

    Starting at the end(), iterating to the begin(), pushing_front as we go along ( granted we have a doubly linked list ).

    That should be O(N) which is the best we can expect from a linked-list, right?
    Ubuntu Desktop
    GCC/G++
    Geany (for quick projects)
    Anjuta (for larger things)

  3. #3
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    It would always be no better than O(n) - you can of course make it less efficient for example by reversing the list or some such.

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

  4. #4
    Use this: dudeomanodude's Avatar
    Join Date
    Jan 2008
    Location
    Hampton, VA
    Posts
    391
    Quote Originally Posted by matsp View Post
    It would always be no better than O(n) - you can of course make it less efficient for example by reversing the list or some such.

    --
    Mats
    But what if you have a singly linked list? I can't figure out how to get better than O( 2N ) on a singly linked list...

    ...I'm guessing that's why ( among other reasons ), the STL provides a doubly-linked list.
    Ubuntu Desktop
    GCC/G++
    Geany (for quick projects)
    Anjuta (for larger things)

  5. #5
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,794
    But what if you have a singly linked list? I can't figure out how to get better than O( 2N ) on a singly linked list...
    Maintain two iterators: one to the previous element, another to the current element. Once you have instantiated the current element, create the link, then push back the previous iterator.
    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
    Apr 2008
    Posts
    890
    Quote Originally Posted by dudeomanodude View Post
    1) But doesn't that become O(logN)?

    2) Wouldn't iterating the list once and pushing the front, then reversing the order be more efficient ( because isnt' that O( 2 * N )? )
    O(log N) scales better than O(N)...

  7. #7
    Use this: dudeomanodude's Avatar
    Join Date
    Jan 2008
    Location
    Hampton, VA
    Posts
    391
    O(log N) scales better than O(N)...
    Oh yea, what i meant to say was O( N^2 ) -much worse
    Ubuntu Desktop
    GCC/G++
    Geany (for quick projects)
    Anjuta (for larger things)

  8. #8
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,246
    1) But doesn't that become O(logN)?
    No -- it's O(N^2)

    2) Wouldn't iterating the list once and pushing the front, then reversing the order be more efficient ( because isnt' that O( 2 * N )? )
    It's just O(N). O(2*N) is the same as O(N).

    Anyway, you're assuming that pushing at the back of the list is inefficient. This only requires a list traversal if you do it naively. If instead, you maintain a pointer/iterator to the end of the list, you can insert each element in O(1) time, avoiding O(N^2) and also getting rid of the 2x constant.

    In theory, a specialization of std::back_insert_iterator<std::list<T> > could be made to do this. Such a specialization may already exist.

  9. #9
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,893
    What for? std::list is a doubly linked list and maintains a reference to the back already. Its push_back() is O(1).

    std::forward_list (coming in C++09) does not provide push_back, though. That's because of the design principle that there's zero overhead compared to a hand-written singly linked list, and a pointer to the last element would incur such overhead.
    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

  10. #10
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,307
    Quote Originally Posted by CornedBee View Post
    What for? std::list is a doubly linked list and maintains a reference to the back already. Its push_back() is O(1).

    std::forward_list (coming in C++09) does not provide push_back, though. That's because of the design principle that there's zero overhead compared to a hand-written singly linked list, and a pointer to the last element would incur such overhead.
    I'd say that it's more likely that it doesn't hold a pointer to the last element because it takes O(n) time to update it when you delete the last item.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  11. #11
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,893
    It takes O(n) time to delete the last item in the first place, and in the course of that you can adjust the pointer at no additional complexity cost. So no, that's not it.
    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

  12. #12
    Banned
    Join Date
    Nov 2007
    Posts
    678
    I do not have time and the code is missing now, after reinstallation of XP, but adding to a singly linked list can be achieved in O(1). Instead of iterating over the list from start to end, to find where to append new node, just keep the last added node saved.

  13. #13
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by manav View Post
    I do not have time and the code is missing now, after reinstallation of XP, but adding to a singly linked list can be achieved in O(1). Instead of iterating over the list from start to end, to find where to append new node, just keep the last added node saved.
    Yes, the debate is about deleting the last node, which requires traipsing through the list to find the previous to last node.

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

  14. #14
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,307
    Quote Originally Posted by CornedBee View Post
    It takes O(n) time to delete the last item in the first place, and in the course of that you can adjust the pointer at no additional complexity cost. So no, that's not it.
    Sure, if you pretend there are no such things as iterators.

    If you have an iterator pointing to the last element then you could not delete the item it points to AND correctly update the ltail pointer in anything less than O(n) time. That's on top of the fact that iterating through the list is also O(n). Therefore if you were to iterate over the list backwards, deleting as you go, it would be O(n*n).
    I'm pretty sure this would be the main reason why there is no tail pointer.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  15. #15
    Confused Magos's Avatar
    Join Date
    Sep 2001
    Location
    Sweden
    Posts
    3,145
    If you complain about bad efficiency when trying to remove the last element of a singly linked list, then that's your problem
    I'd use a doubly linked list, and live happily ever after!
    MagosX.com

    Give a man a fish and you feed him for a day.
    Teach a man to fish and you feed him for a lifetime.

Page 1 of 3 123 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. SO new to C++
    By black_spot1984 in forum C++ Programming
    Replies: 5
    Last Post: 09-30-2008, 01:32 AM
  2. deleting a node in linked list
    By BoneXXX in forum C Programming
    Replies: 18
    Last Post: 12-17-2007, 11:30 AM
  3. urgent help please...
    By peter_hii in forum C++ Programming
    Replies: 11
    Last Post: 10-30-2006, 05:37 AM
  4. Replies: 3
    Last Post: 03-04-2005, 01:46 PM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM

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