Thread: Linked list implementation question

  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
    Chappell Hill, Texas
    Posts
    2,332
    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.
    Mainframe assembler programmer by trade. C coder when I can.

  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
    Chappell Hill, Texas
    Posts
    2,332
    They don't care about performance?
    Mainframe assembler programmer by trade. C coder when I can.

  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, 04:05 PM
  2. Unknown memory leak with linked lists...
    By RaDeuX in forum C Programming
    Replies: 6
    Last Post: 12-07-2008, 04: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, 10:33 PM
  5. How to use Linked List?
    By MKashlev in forum C++ Programming
    Replies: 4
    Last Post: 08-06-2002, 07:11 AM