Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

Semi-relevant side note: Within some constraints its possible to remove an element in a singly linked list without walking the list. The purpose of walking the list is not to find the element (which you already have) but to find it's previous element so you can fix the "next" pointer on the previous element. What you can do instead is to copy the data from the next element onto the one to delete, making it a "copy" of the next one. And then delete the next one after fixing the pointers. Hard to say in english but here's the idea:

    remove_list_entry(entry)
    {
        next = entry->next;
        entry->data = next->data;
        entry->next = next->next;
        free(next);
    }
You do need to handle the case of deleting the last element in the list. That can be done by keeping an EOL element at the end just for this purpose. The real caveat is that it breaks external references to list elements. If you are managing the list yourself however and can deal with these issues you can avoid list traversal (or save a pointer on every list element vs a doubly linked list). Just something to keep in your bag of tricks.


Neat idea, but yeah like you say you break referential integrity pretty hard with this solution. And tbh I feel like everyone prefers tons of local links in their data, and since we have memory to spare with wasteful representations, we pick the convenient, link heavy one, a world in which this algorithm variant does not apply.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: