Jis*_*han 5 linked-list time-complexity data-structures
我遇到了一个有趣的问题,我对提供给我的答案感到困惑.问题如下:
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
我最初认为DLL是正确的选择,因为连接可以从双方发生,但答案似乎是CLL.我很迷惑.任何解释都将是最有帮助的.谢谢.
如果您有一个指向至少一个列表中最后一个节点的指针,则可以使用单个链表或双向链表轻松地在O(1)时间内连接两个列表.(当然,指向列表的指针.)
您不能使用数组实现,因为您最终必须分配更多内存并将新结果列表复制到它.即使数组已经分配了内存,您仍然需要将所有新项目复制到它.所以它是O(m + n)或O(n)(其中m和n分别是各个列表的长度).
使用循环链接列表,您可以在O(1)时间内轻松连接它们.这只是打破两个列表中的链接,然后将它们连接在一起的问题.当然,这假设物品的顺序并不是特别重要.