patternModerate
Advantages of linked lists over arrays?
Viewed 0 times
arraysadvantageslistslinkedover
Problem
Are there other advantages to linked lists over arrays other than constant time removals of the first element?
Solution
Linked lists can work well even if memory is fragmented. Arrays usually require a continuous piece of memory. For large piece of data finding this large continuous piece of memory might be hard.
Most of benefits of linked lists requires to remember more links than just the head. For example. If you are doing some sequential checks and deletions or insertions, you can keep this link of the last checked element. Then all of this insertions or deletions are O(1), you have all the data needed, and memory required for insert is small. In other words linked lists are good for local operations. Like text. If you would try to implement a text editor and rewrite the whole array when user adds another letter in the middle, it will be slower than with a linked list, if linked list remembers last edit points and most edits are a bit further than it. Upgrade to this idea are skip list and rope.
Another useful feature of links is atomicity of small edits. With an array you could achieve atomicity by replacing the link to the array itself, but only after making a whole new copy. But with linked list you can build another subchain, and then replace the link to it, changing the small portion of the linked list this way, keeping all the data consistent and not spending lots of memory on another copy.
Most of benefits of linked lists requires to remember more links than just the head. For example. If you are doing some sequential checks and deletions or insertions, you can keep this link of the last checked element. Then all of this insertions or deletions are O(1), you have all the data needed, and memory required for insert is small. In other words linked lists are good for local operations. Like text. If you would try to implement a text editor and rewrite the whole array when user adds another letter in the middle, it will be slower than with a linked list, if linked list remembers last edit points and most edits are a bit further than it. Upgrade to this idea are skip list and rope.
Another useful feature of links is atomicity of small edits. With an array you could achieve atomicity by replacing the link to the array itself, but only after making a whole new copy. But with linked list you can build another subchain, and then replace the link to it, changing the small portion of the linked list this way, keeping all the data consistent and not spending lots of memory on another copy.
Context
StackExchange Computer Science Q#151505, answer score: 19
Revisions (0)
No revisions yet.