Linked Lists and Classes

This is a discussion on Linked Lists and Classes within the C++ Programming forums, part of the General Programming Boards category; 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 ...

  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
    21,727
    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.
    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
    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
    21,727
    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'".
    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
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,893
    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
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,704
    What do you mean by "intrusive" CornedBee?

  8. #8
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,893
    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, 06:47 PM
  5. Replies: 2
    Last Post: 01-18-2003, 12:32 AM

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