Benefits of linked list over array

Question

I really don't see how linked lists are better than array , the insertion and deletion complexities are same , eg. , In array the insertion at rear is O(1) while for linked lists the insertion at head is O(1) , and simillarly insertion in arrays at front is O(n) but for the later it is O(n) to insert at the rear end.

Apart from the only fact that linked lists are dynamic in nature ,I dont see any benefits of linked lists over arrays. Moreover , I can use a dynamic array to counter that problem.

Again Array also have better results when we want to access an element.

So can anybody please tell me why are linked lists better than array? And if they are not better , then why do we use it?

"Apart from the only fact that linked lists are dynamic in nature" there you have it. — Federico klez Culloca, Apr 14 '22 at 11:25
please pick one language. `LinkedList` and `std::list` are rather different (also arrays are different in C++ vs Java) — 463035818_is_not_an_ai, Apr 14 '22 at 11:25
i removed the C++ tag, because in C++ you cannot insert into an array — 463035818_is_not_an_ai, Apr 14 '22 at 11:27
You need to really define the implementation - `std::vector` vs `std::array` and single-,double- linked lists are vastly different — Quimby, Apr 14 '22 at 11:28

eerorika · Answer 1 · 2022-04-14T12:29:14.263

No data structure is universally better than another data structure. There are benefits and drawbacks and which is better depends on what benefits and drawbacks are more important for your use case.

the insertion and deletion complexities are same

Firstly, it isn't possible to insert or delete elements of arrays at all. Their size remains constant. But I'll assume that you meant "dynamic array" data structure i.e. std::vector and java.util.ArrayList (not to be confused with dynamically allocated array which is also called "dynamic array").

The insertion and deletion complexities between linked lists and dynamic array are not the same.

but for the later it is O(n) to insert at the rear end.

Given a an iterator to a linked linked list, you can insert after the pointed element in constant time. Hence, if you maintain an iterator to the end of the list, you can insert there in constant time.

An important advantage of linked list over the dynamic array, besides the complexity, is that the elements remain stable in memory. In vector, if adding an element exceeds the capacity, then all iterators and references to existing elements are invalidated. Iterators as well as references to linked list elements remain valid until the element is erased. If you need this property, then using a dynamic array is not an option.

score 0 · Answer 2 · answered Apr 14 '22 at 13:11

Linked lists, as independent data structures, are rarely used.

Quite often, however, objects are linked into a list by incorporating next and maybe prev pointers directly into the objects themselves. As a data structure, that is often referred to as an "intrusive" linked list.

Sometimes this is used to add features to existing data structures. In Java you can see this in LinkedHashMap, which links the map entries together into a list, preserving their insertion or access order and allowing you to use it as an LRU cache. Similarly, leaf nodes in a B+tree are often linked onto a list to simplify traversal. There are many examples.

Benefits of linked list over array

2 Answers2