Linked List - Appending node: loop or pointer?

Question

I am writing a linked list datatype and as such I currently have the standard head pointer which references the first item, and then a next pointer for each element that points to the following one such that the final element has next = NULL.

I am just curious what the pros/cons or best practices are for keeping track of the last node. I could have a 'tail' pointer which always points to the last node making it easy to append, or I could loop over the list starting from the head pointer to find the last node when I want to append. Which method is better?

pippin1289 · Accepted Answer · 2013-09-17 16:51:05Z

4

It is usually a good idea to store the tail. If we think about the complexity of adding an item at the end (if this is an operation you commonly do) it will be O(n) time to search for the tail, or O(1) if you store it.

Another option you can consider is to make your list doubly linked. This way when you want to delete the end of the list, by storing tail you can delete nodes in O(1) time. But this will incur an extra pointer to be stored per element of your list (not expensive, but it adds up, and should be a consideration for memory constrained systems).

In the end, it is all about the operations you need to do. If you never add or delete or operate from the end of your list, there is no reason to do this. I recommend analyzing the complexity of your most common operations and base your decision on that.

answered Sep 17, 2013 at 16:51

pippin1289

4,9492 gold badges25 silver badges37 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Mosby Over a year ago

Also consider the added cost of storing redundant pointers. If your list is very long, you could end up with a very large memory footprint.

Dan · Accepted Answer · 2013-09-17 16:53:01Z

Depends on how often you need to find the last node, but in general it is best to have a tail pointer.

There's very little cost to just keeping and updating a tail pointer, but you have to remember to update it! If you can keep it updated, then it will make append operations much faster (O(1) instead of O(n)). So, if you usually add elements to the end of the list, then you should absolutely create and maintain a tail pointer.

If you have a doubly linked list, where every element contains a pointer both to the next and prev elements, then a tail pointer is almost universally used.

On the other hand, if this is a sorted list, then you won't be appending to the end, so the tail pointer would never be used. Still, keeping the pointer around is a good idea, just in case you decide you need it in the future.

Collectives™ on Stack Overflow

Linked List - Appending node: loop or pointer?

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related