2D array implementation of sorted lists
Chenglie Hu · ACM SIGCSE Bulletin · 2005
The ideas and key algorithms of a sorted list data structure based on a 2-dimensional (2D) array container are presented. It is shown that with an appropriately chosen number of rows, the efficiency of insertion and deletion is much improved compared to traditional approaches of using 1D arrays or linked structures. Yet, the binary search capability is retained. While such a data structure may deserve further exploration for its practical merit, its real value may well be in data structure classes, where the implementations and related issues provide sources for challenging projects. In addition, the implementation also provides a good example in understanding 2D arrays implemented as array of arrays in an object-oriented language.