Array-Linked Data Structure: Introducing a Hybrid Model of Memory Management and Faster and Easier Insertion and Reallocation Procedures - Kartik Srivastava (International Journal of Data Structure Studies, 2023)
Here, I have introduced a new data structure titled “Array-Linked Data Structure”. It incorporates a hybrid model of memory allocation, introducing a new insertion procedure in an existing data structure which is faster than that for arrays. It also offers O(c) access time where c is a constant. The access time is worse than O(1) for an array but still better than that for a linked list since the index of data could be directly supplied to the access procedure here. The data structure also maintains a DS table for each allocated block of memory which keeps track of auxiliary data structures in the main block. Insert call of the structure offers a complexity of O(t*log(t)) where t is the number of auxiliary data chains in the main block where insertion is supposed to happen. Rest of the procedures are discussed in detail with proofs. The main element of the structure is that it offers a faster insertion procedure and easier reallocation procedure, while maintaining a hybrid model of contiguous memory allocation.
Keywords: DS table; Hybrid memory allocation; insertion