+ 1

What are the advantages of linked list over list in Python

Can anyone tell me what are the advantages of a linked list over a list in Python? I think the Insertion and deletion operation of list can be done using a function with no need to traverse from the beginning like the linked list. Eg: l = [1,2,3,5] l.insert(3,4)#Insertion of 4 into list at 4th position print(*l)#Output 1,2,3,4,5 del l[0]#deleting element at oth index print(l)

14th Nov 2020, 2:13 AM
Varshith
Varshith - avatar
3 Respuestas
+ 3
The difference is not in the functions, but in the complexity of operations (time it requires to perform an operation) For python list the indexing operation (take i-th element if a list) is constant time (independent on list size), but insertion and deletion are linear time in list size (even if they can, and should be done with a single function call, the function still needs to move the elements of the list). Linked list, on the other hand has linear time indexing (you have to walk over all the previous element to get the i-th one), but has constant time deletion and insertion. So if you have a structure that has large number of elements, rarely requires accessing an element by its index, but often needs insertion/deletion of an element in the middle (preserving the order of other elements), or has highly varying size than you should consider using a linked list. Otherwise python list is a good default choice.
14th Nov 2020, 5:08 AM
Volodymyr Chelnokov
Volodymyr Chelnokov - avatar
+ 6
This should explain most everything you need/want to know. https://dbader.org/blog/JUMP_LINK__&&__python__&&__JUMP_LINK-linked-list
14th Nov 2020, 2:21 AM
ChaoticDawg
ChaoticDawg - avatar
+ 6
Linked list is the base of more complex data structures like queues , stacks , trees , graphs etc.
14th Nov 2020, 2:23 AM
Arsenic
Arsenic - avatar