The TREE LIST – Introducing a Data Structure
Sibin James1, Pranav Prakash2, R Nandakumar3
1Sibin James, Department of Computer Science and IT, Amrita School of Arts & Sciences, Kochi, Amrita Vishwa Vidyapeetham, (Tamil Nadu), India.
2Pranav Prakash, Department of Computer Science and IT, Amrita School of Arts & Sciences, Kochi, Amrita Vishwa Vidyapeetham, (Tamil Nadu), India.
3R Nandakumar, Department of Computer Science and IT, Amrita School of Arts & Sciences, Kochi, Amrita Vishwa Vidyapeetham, (Tamil Nadu), India.
Manuscript received on 23 March 2019 | Revised Manuscript received on 30 March 2019 | Manuscript published on 30 March 2019 | PP: 1093-1096 | Volume-7 Issue-6, March 2019 | Retrieval Number: F2443037619/19©BEIESP
Open Access | Ethics and Policies | Cite | Mendeley | Indexing and Abstracting
© The Authors. Blue Eyes Intelligence Engineering and Sciences Publication (BEIESP). This is an open access article under the CC-BY-NC-ND license (http://creativecommons.org/licenses/by-nc-nd/4.0/)
Abstract: The array and the linked list are two classic data structures. The array allows constant time random access (achieved in C language with the [] operator) but suffers from its fixed size and relative inflexibility (the latter becomes an issue while performing deletions). The linked list, on the other hand allows dynamic allocation of memory leading to greater flexibility (manifested in easy insertions and deletions) but suffers from slow search speed – O(N) . We describe a complete binary tree-based data structure which we call TREE LIST. It allows dynamic allocation of memory (hence free from many of the fixed size issues of the array) and provides random access with O(log N) complexity – which is an improvement over the linked list although not as fast as the array. We also discuss some other aspects of this data structure – in particular how it supports some of the classic sorting algorithms.
Keywords: Tree list, Linked list, Array, Algorithm, Binary tree, Complexity.
Scope of the Article: Data Analytics