2D array implementation of sorted lists

ABSTRACT

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.

REFERENCES

• 1: Nell B. Dale , Daniel T. Joyce , Chip Weems, Data Structures in Java, Jones and Bartlett Publishers, Inc., 2002
• 2: Michael Main, Data Structures and Other Objects Using Java (3rd Edition), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2005
• 3: Timothy Budd, Classic Data Structures in Java: A Visual and Explorational Approach, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2000

INDEX TERMS

Primary Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Arrays

Additional Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Lists, stacks, and queues

General Terms:
Algorithms, Design, Theory

Keywords:
2D array implementation, sorted list