One of the biggest advantages of linked lists over arrays is that inserting an element at any location takes only O( 1) time. However, it takes O( n) to search for an element in a linked list.
There is a simple variation of the singly linked list called unrolled linked lists.
An unrolled linked list stores multiple elements in each node (let us call it a block for our convenience). In each block, a circular linked list is used to connect all nodes.
There is a simple variation of the singly linked list called unrolled linked lists.
An unrolled linked list stores multiple elements in each node (let us call it a block for our convenience). In each block, a circular linked list is used to connect all nodes.
Assume that there will be no more than n elements in the unrolled linked list at any time. To simplify this problem, all blocks, except the last one, should contain exactly
elements.
elements.
Thus, there will be no more than blocks at any time.
blocks at any time.
In unrolled linked lists, we can find the kth element in O():
):
K
No comments:
Post a Comment