Linked list implementation question

This is a discussion on Linked list implementation question within the C++ Programming forums, part of the General Programming Boards category; I am preparing for job interviews and was going over the implementation of a linked list. specifically appending to the ...

  1. #1
    Registered User
    Join Date
    Dec 2009
    Posts
    41

    Linked list implementation question

    I am preparing for job interviews and was going over the implementation of a linked list. specifically appending to the end of the list.

    when I initially wrote it out I had a public variables that held a pointer to the first node, and the last. so adding was simple, take the last node->next = newNode and the last node = newNode.

    badabing bada boom.

    i was looking up other peoples implementations, and every single one's(including wikipedia, which as we all know is always right) did not have a last node variable, but instead looped through the list until the tempNode->next ==NULL, and then that is your last one.

    Logically the latter implementation makes sense but I cant see a reason for doing it. the small space the last pointer takes up, and the extra code to read and write to it, is still far less than having to loop through a list of 1000+ elements.

    So, I figure I'm misunderstanding something. any help is appreciated.

  2. #2
    Jack of many languages Dino's Avatar
    Join Date
    Nov 2007
    Location
    Katy, Texas
    Posts
    2,309
    Like you, I subscribe to the "also keep the last pointer" camp, if entries are to indeed be entered at the end. Otherwise, I just keep the anchor and add to the front.

    badabing, bada boom.
    Mac and Windows cross platform programmer. Ruby lover.

    Quote of the Day
    12/20: Mario F.:I never was, am not, and never will be, one to shut up in the face of something I think is fundamentally wrong.

    Amen brother!

  3. #3
    Registered User
    Join Date
    Dec 2009
    Posts
    41
    It seems like the most logical approach.. but I have seen to many loop through the whole list approaches to disregard it. any idea why they do it?

  4. #4
    Jack of many languages Dino's Avatar
    Join Date
    Nov 2007
    Location
    Katy, Texas
    Posts
    2,309
    They don't care about performance?
    Mac and Windows cross platform programmer. Ruby lover.

    Quote of the Day
    12/20: Mario F.:I never was, am not, and never will be, one to shut up in the face of something I think is fundamentally wrong.

    Amen brother!

  5. #5
    Registered User
    Join Date
    Mar 2010
    Posts
    18
    What kind of job interview are you going to that you worry about linked lists?!?
    Anyways, in C++, the standard says that for any container you have access to the end() in amortized constant time. So if you implement it in C++, do everyone a favor and use the readily-available stl version. And if you implement your own container, adhere to the parts of the standard which are applicable. This way, the pain you do to your fellow programmers when using your code will be minimized (argh. libxml++ implemented size() in O(n). Bastards. I spent two days looking for that "bug".)

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. linked list question
    By brb9412 in forum C Programming
    Replies: 16
    Last Post: 01-04-2009, 03:05 PM
  2. Unknown memory leak with linked lists...
    By RaDeuX in forum C Programming
    Replies: 6
    Last Post: 12-07-2008, 03:09 AM
  3. singly linked circular list
    By DarkDot in forum C++ Programming
    Replies: 0
    Last Post: 04-24-2007, 08:55 PM
  4. Linked List Help
    By CJ7Mudrover in forum C Programming
    Replies: 9
    Last Post: 03-10-2004, 09:33 PM
  5. How to use Linked List?
    By MKashlev in forum C++ Programming
    Replies: 4
    Last Post: 08-06-2002, 07:11 AM

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