Thread: Linked Lists and Classes

  1. #1
    Registered User
    Join Date
    Mar 2007
    Posts
    6

    Linked Lists and Classes

    Hi, I've found this example of a linked list on the web:

    http://www.dreamincode.net/code/snippet82.htm

    ..and my question is this: in the example the author has a structure within the class called 'node' and within that is the usual linked list things, but why not just place these things right in the class itself? Instead of creating new 'nodes' you would create new 'myLinkedListClasses'. I guess what I'm really wondering is if one approach is better(more efficient) than the other or if they're really just the same in the end(as they do both work fine).

    Thanks,
    Roger

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    A linked list is a collection of nodes, so the linked list class models that. If you just have nodes linked together, then you still have a linked list, but there is less encapsulation.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Registered User
    Join Date
    Mar 2007
    Posts
    6
    OK, so my next question would be: would implementing the linked list without this encapsulation(the 'node' struct) be less efficient in terms of memory usage or even performance?

    Thanks laserlight for your fast reply

  4. #4
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Probably no difference at all - you still need an item of data and link to the next item in the list in some way, and the struct is just there to simplify the processing of those bits.

    --
    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
    28,413
    OK, so my next question would be: would implementing the linked list without this encapsulation(the 'node' struct) be less efficient in terms of memory usage or even performance?
    I think that it depends on the implementation. Logically, there would be very little difference, since it is not a matter of doing away with the node struct, but doing away with the linked list class as a container. Your suggestion is not "instead of creating new 'nodes' you would create new 'myLinkedListClasses'", but "instead of creating a linked list object you would create new 'nodes'".
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  6. #6
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    Intrusive lists are typically slightly faster in real-world usage. However, they require you to change the class you want to put into the list. Non-intrusive lists are more generic and preferable unless you've proven that the intrusive list is worth the hassle.
    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

  7. #7
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,613
    What do you mean by "intrusive" CornedBee?

  8. #8
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    Intrusive lists are where the links are members of the data class.
    Non-intrusive lists are where the data class is a member or pointee of a node class.
    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. Doubly Linked Lists
    By Swerve in forum C++ Programming
    Replies: 6
    Last Post: 03-23-2009, 12:51 PM
  2. Linked Lists 101
    By The Brain in forum C++ Programming
    Replies: 5
    Last Post: 07-24-2004, 04:32 PM
  3. Radix Sort, Strings, and Linked Lists
    By dark paladin in forum C++ Programming
    Replies: 2
    Last Post: 04-24-2003, 03:24 PM
  4. Linked Lists and Inheritance
    By mattyneedshelp! in forum C++ Programming
    Replies: 6
    Last Post: 02-01-2003, 07:47 PM
  5. Replies: 2
    Last Post: 01-18-2003, 01:32 AM