Hi,
I couldn't find an O(1) operation that concatenates two lists. Something like this:
proc concat[T](a: var SinglyLinkedList[T], b: SinglyLinkedList[T]) =
## Concatenates (adds to the end) `b` to `a`. Efficiency: O(1).
## Note that the two lists share structure after the operation.
if a.tail != nil:
a.tail.next = b.head
a.tail = b.tail
if a.head == nil:
a.head = b.head
Since one of the merits of the linked list representation is constant-time concatenation, I would have thought this basic enough to include in the standard library. Or did I miss something? (Quite probable, as I'm new to Nim...)
Thanks for the tip! There is one possible problem: the head of linked lists is defined as <//>(ref SinglyLinkedNodeObj[T]), which seems to mean that the memory pointed by head is owned, whatever that means.
After the proposed operation, the two lists would share structure, could this cause any memory problems (in any of the many supported GC schemes)?