Just keep a pointer to the head and tail of the list. You can then append to either end of the list in O(1). When you put a new node at the tail end, use the ta

Just keep a pointer to the head and tail of the list. You can then append to either end of the list in O(1). When you put a new node at the tail end, use the tail pointer to get to the tail node instead of walking the whole list. Of course, you need to make sure the head/tail pointers are always updated to point to the current head/tail of the list.