Kartik Srivastava
- Student Indian Institute of Technology, Kanpur Uttar Pradesh India
Abstract
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: Hybrid memory allocation, insertion, DS table
[This article belongs to International Journal of Data Structure Studies(ijdss)]
Browse Figures
References
1. Lokeshwar B, Zaid MM, Naveen S, Venkatesh J, Sravya L. Analysis of Time and Space Complexity of Array, Linked List and Linked Array (hybrid) in Linear Search Operation. In 2022 IEEE International Conference on Data Science, Agents & Artificial Intelligence (ICDSAAI). 2022 Dec 8; 1: 1–6.
2. Sanders P, Mehlhorn K, Dietzfelbinger M, Dementiev R, Sanders P, Mehlhorn K, Dietzfelbinger M, Dementiev R. Representing Sequences by Arrays and Linked Lists. In: Sequential and Parallel Algorithms and Data Structures: The Basic Toolbox. Cham: Springer; 2019; 81–116.
3. Wen F, Qin M, Gratz PV, Reddy AN. Hardware memory management for future mobile hybrid memory systems. IEEE Trans Computer-Aided Design Integr Circuits Syst. 2020 Oct 2; 39(11): 3627–37.
4. Jin H, Li Z, Liu H, Liao X, Zhang Y. Hotspot-aware hybrid memory management for in-memory key-value stores. IEEE Trans Parallel Distrib Syst. 2019 Oct 4; 31(4): 779–92.
5. Cook V, Peterson C, Painter Z, Dechev D. Quantifiability: Concurrent correctness from first principles. arXiv preprint arXiv:1905.06421. 2019 May 15.
6. Java T Point. (2021). Contiguous and Non-Contiguous Memory Allocation in Operating System. [Online]. Available from: https://www.javatpoint.com/contiguous-and-non-contiguous-memory-allocation-in-operating-system.
7. Rahama M. Data Structures and Algorithms. GRIN Verlag; 2013 Jan 7.
8. Utkarsh Pandey. Time Complexity and Space Complexity. [Online]. Geeks for Geeks. Available from: https://www.geeksforgeeks.org/time-complexity-and-space-complexity/
9. A Novel Counting Sort for Real Numbers with Linear Time Complexity. In 2022 IEEE International Conference on Computational Intelligence and Sustainable Engineering Solutions (CISES). 2022 May 20; 60–64.
10. Susanne Windfeld Pedersen. (2022). Insert, Modify, Modify All, Delete, and Delete All Methods – Business Central. [Online]. Microsoft.com. Available from: https://learn.microsoft.com/en-us/dynamics365/business-central/dev-itpro/developer/devenv-insert-modify-modifyall-delete-and-deleteall-methods
| Volume | 01 |
| Issue | 01 |
| Received | July 5, 2023 |
| Accepted | July 12, 2023 |
| Published | September 4, 2023 |