Concatenation of a linked list in O (1) time

Question

I came across an interesting question, and I am puzzled by the answer provided to me. The question is this:

The concatenation of 2 lists can be performed O(1) time. Which of the following implementation of list should be used? - Singly Linked List - Doubly Linked List - Circular Linked List - Array Implementation Of Linked List 

Initially, I thought the DLL would be the right choice, since concatenation can occur on both sides, however the answer seems to be CLL. I'm confused. Any explanation would be most helpful. Thanks.

Answer 1

You can easily merge two lists O (1) times using either a single linked list or a doubly linked list, provided that you have a pointer to the last node in at least one of the lists. (And, of course, the pointers to the list are headed.)

You cannot do this with an array implementation because you have to allocate more memory and copy a new resulting list into it. Even if memory is already allocated in the array, you still have to copy all the new elements. Thus, it is either O (m + n) or O (n) (where m and n are the lengths of individual lists, respectively).

With a circularly linked list, you can easily combine them O (1) times. It is just a matter of breaking the links in both lists and then combining them. This suggests, of course, that the order of the items is not particularly important.

Answer 2

Answer Circular Double List

To merge a list, you must point the next pointer of the last node of the first list to the first node of the second list. Doing this in an O (1) circular double link list is helpful. You can go to the last node of the first list with head1-> next-> previous. And change this field pointing to head2-> next. And also change head2-> next-> before head1-> next.

If the list of pointers to the last node of any one list is in sinlgy and double linked, you can merge the two lists in O (1).

Answer 3

There seem to be a few correct answers.

You can combine two singly linked lists O (1) times while you are storing pointers to both the first and the last elements of the list. You simply retype the next pointer of the last element of the first list to the first element of the second list. This also works with doubly linked lists.

You can also merge two cyclically linked lists O (1) times using a similar trick.

The only option that doesn't work is an array based list.

Hope this helps!

Answer 4

You don't need last , but you need next

Suppose each list has at least two items.

 void merge( node* first, node* second ) { node * first_next = first->next; node * second_next = second->next; first->next = second_next; second->next = first_next; } 

As Jim Michelle said, any list will work fine.

Answer 5

These two:

• Double list
• Circular list of links

- right answers. Both support O (1) concatenation.