CODEWITHSUNDEEP
arraylistdata-structureslinked-listtime-complexitycircular-buffer
compsci3289294
compsci3289294

Reputation: 29

Appropriate Data structure for Sequential access but Random Insertion/Deletion

If i'm writing an algorithm that requires storage of data that will be sequentially accessed from the first item in the list to the last item in the list. And that Data will regularly need to be inserted or deleted at random locations anywhere in the list.

Would I be correct in saying that LinkedList would be more appropriate then ArrayList, Binary Tree and Circular Buffer?

ArrayLists are Random accesss so it's not them, Binary Trees aren't a linear data structure so it's not them as they can't be sequentially accessed in a single run, It can't be a circular buffer as Data needs to be inserted or deleted at random locations but they just enqueue and dequeue at 2 select positions only.

Upvotes: 0

Views: 292

Answers (1)

trincot
trincot

Reputation: 351029

If all you got is the head of a linked list, and the index ("location") where an insertion must be made, then a linked list is not very handy: you'll have to traverse from the head of the list to the desired location and that takes O(𝑘) time, where 𝑘 is the desired location. As 𝑘 can in principle be anything between 0 and 𝑛 (where 𝑛 is the current number of nodes in the list), this means the worst and average time complexity is O(𝑛).

A better structure will be a self-balancing binary search tree (such as AVL, red-black, B-tree, ...), where each node is "augmented" with a property that gives the number of values in the subtree it roots. This allows the values to be stored and traversed (inorder traversal) according to their index. Insertion and deletion then have O(log𝑛) time complexity. A particular handy tree data structure for traversal is the B+-tree.

Another one that is as efficient is the skip list. This is a linked list that is augmented with several layers of linked lists, so to allow O(log𝑛) access to any index.

If however with "location" it is meant that you get a node reference in a linked list, where the new node must be inserted, then a linked list is fine. But then the question is: how did you get that location? In the end, that is a node reference that must be retrieved somehow, and there is not much else you can do than traverse a list from its head to get such node references... so then we're back to the start of my answer.

Upvotes: 0

Related Questions