Another Linked List

This is a discussion on Another Linked List within the C++ Programming forums, part of the General Programming Boards category; Originally Posted by siavoshkc They have notable performance impact. Justify this claim or stop making it....

  1. #16
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,274
    Quote Originally Posted by siavoshkc View Post
    They have notable performance impact.
    Justify this claim or stop making it.

  2. #17
    System Novice siavoshkc's Avatar
    Join Date
    Jan 2006
    Location
    Tehran
    Posts
    1,236
    Though condition performance impact is not something new, I opened a new thread for it as it not relevant to list.
    Learn C++ (C++ Books, C Books, FAQ, Forum Search)
    Code painter latest version on sourceforge DOWNLOAD NOW!
    Download FSB Data Integrity Tester.
    Siavosh K C

  3. #18
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    Nice usage of the Node constructor!

    I consider the function PopBack and the [] operator for this class fundamentally wrong.
    If the purpose of this class is speed, as evidenced by not wanting a branch statement, providing O(n) operations is far worse than a single if statement.
    These two things conflict and contradict in a major way. There's a reason that the standard C++ library doesn't provide an [] operator for a list container.
    Furthurmore, where a [] operator is supplied (and it shouldn't be here), it really needs to have a const and non-const version.

    You could say that insertion and deletion from the middle are perhaps a necessary O(n) evil, when it comes to a singly-linked list. But I would perhaps still discourage the user of your class from doing such things by forcing them to have to implement these themselves if they so insist.

    Conditional statements don't impact performance in the way you seem to think they do.
    They have notable performance impact. I think 4 byte of memory costs less than their impact.
    Firstly, it's not 4 bytes, it's the size of a node which is the size of a pointer plus the size of an int. 8 bytes on a standard PC.
    Secondly, this is not a straight out "trade and in statement for 8 bytes" here because using an if-statement prevents users from screwing up the list via one too many pops, but the extra node does not.
    Thirdly, in a number of circumstances, the lack of this saftey 'if statment' will cause the code using the class to need to implement this 'if statement' instead. At the very least that's a little unnecessary code bloat for something that should be only in one place.

    I know you're having fun with this and are learning a lot, but be careful not to make the mistake many people make in assuming that they can design and write a better linked-list than a committee of experts can.
    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"

  4. #19
    System Novice siavoshkc's Avatar
    Join Date
    Jan 2006
    Location
    Tehran
    Posts
    1,236
    This list is only for practice. It may not be used anywhere. We consider that code using the class is carefully written and will not Pop more than its Push or at least has checks where it is needed. So it is not a important case for me. Of course for a practical program I would use standard library. But that 8 byte of dummy Node (4 of it is completely wasted) is the thing that bothers me.
    I consider the function PopBack and the [] operator for this class fundamentally wrong.
    When user needs random access she/he should not use linked list. OK. But I am not sure if I should implement the code for it or not. If I do user can decide whether to use them or not. We can note the O(n) in header file.
    Last edited by siavoshkc; 07-19-2007 at 07:42 AM.
    Learn C++ (C++ Books, C Books, FAQ, Forum Search)
    Code painter latest version on sourceforge DOWNLOAD NOW!
    Download FSB Data Integrity Tester.
    Siavosh K C

Page 2 of 2 FirstFirst 12
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. C++ Linked list program need help !!!
    By dcoll025 in forum C++ Programming
    Replies: 1
    Last Post: 04-20-2009, 11:03 AM
  2. Following CTools
    By EstateMatt in forum C Programming
    Replies: 5
    Last Post: 06-26-2008, 11:10 AM
  3. Reverse function for linked list
    By Brigs76 in forum C++ Programming
    Replies: 1
    Last Post: 10-25-2006, 11:01 AM
  4. Template Class for Linked List
    By pecymanski in forum C++ Programming
    Replies: 2
    Last Post: 12-04-2001, 09:07 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