Efficiently Sorting Linked Lists

Simplifying Linked Lists

By Tim Kientzle

Normally, you need just one pointer to traverse a linked list. But, if you need to modify the list, the textbooks tell you to keep a second pointer that tracks the previous item. This second pointer allows you to update the "next" field of the previous item. However, this complicates inserting or deleting the first item, since you then must update the list head rather than the next field of some item.

Igor Kolpakov pointed out to me that it's much simpler if the second pointer just tracks the pointer that needs to be updated, rather than the entire previous item. This works whether you need to update the list head or a "next" field.

Listing Three shows how this one slight change removes a lot of conditional logic from the textbook list management code.

DDJ