Fast concatenating of lists

In my program I calculate very much concatenations of lists with single items (i. e. I often perform "concatenate(someList, <single-sized list containing one item>)" operations). How to make thos开发者_运维技巧e concatenations and iterating through resultant lists as fast as possible?

I have considered two implementations but may be there is faster one:

• Naive implementation of concatenation by copying all items to resultant list. That results in O(n) time cost of iterating but also O(n) performance of concatenating.
• Wrapping result of concatenation into new class, ListsConcatenation (which also has interface of List), which keeps references to all original lists and forwards all calls to corresponding one. That will result in O(1) time cost of concatenating but time cost of iterating will become O(n*log(n)).

---

Usually this requirement pops up when populating a list in left-to-right order. If so, then the question is not how to insert a single element in O(1) time, but how to insert n elements in O(n) time, and the simple answer is to build the list back-to-front and reverse it at the end.

I am, of course, assuming some functional language that provides immutable data types. If your data types are mutable, then you could simply remember the last node, and append a new element by assigning to its next pointer.

---

Write a Linked List that has a pointer to the end node as well as a pointer to the head. To concatenate a list in O(1), dereference the "end" pointer of the list that you want to go first, and make that node's "next" pointer point to the head of the list you want to append. Remember to update the end point to point to the node referenced by the appended list's "end" pointer...