217k views
1 vote
Consider the efficiency of locating the kth element in a singly-linked list. How does that compare to locating the kth element in a doubly-linked list

User Jennine
by
6.8k points

1 Answer

4 votes

Answer:

Finding kth element is more efficient in a doubly-linked list when compared to a singly-linked list

Step-by-step explanation:

Assuming that both lists have firs_t and last_ pointers.

For a singly-linked list ; when locating a kth element, you have iterate through a number of k-1 elements which means that locating an element will be done only in one ( 1 ) direction

For a Doubly-linked list : To locate the Kth element can be done from two ( directions ) i.e. if the Kth element can found either by traversing the number of elements before it or after it . This makes finding the Kth element faster because the shortest route can be taken.

Finding kth element is more efficient in a doubly-linked list when compared to a singly-linked list

User Chanthu
by
5.2k points