An Auxiliary Array Indexing Approach for Efficient Binary Search in Linked Lists

Year : 2026 | Volume : 04 | Issue : 01 | Page : 21 28
    By

    Rejay Pavunkumar,

  • Royal Rodrigues,

  • Rohini Bagul,

  • Vaishnavi Biradar,

  1. Student, Master of Computer Application, Thakur Institute of Management Studies & Career Development & Research, Kandivali East, Mumbai, Maharashtra, India
  2. Student, Master of Computer Application, Thakur Institute of Management Studies & Career Development & Research, Kandivali East, Mumbai, Maharashtra, India
  3. Student, Master of Computer Application, Thakur Institute of Management Studies & Career Development & Research, Kandivali East, Mumbai, Maharashtra, India
  4. Assistant Professor, Master of Computer Application, Thakur Institute of Management Studies & Career Development & Research, Kandivali East, Mumbai, Maharashtra, India

Abstract

The paper covers an algorithm for searching a linked list structure using binary search. Binary search is a classic example of an algorithm that follows the divide-and-conquer approach. Binary search may be used to find elements in an array. Trying to apply the conventional binary search to a linked list simply does not work out very well; it still has an O(n) time complexity, the same as linear search. This is because in linked lists, you cannot immediately go to a particular element at once; you must go through the entire list, which requires O(n) time to look up. To solve this problem, this paper is going to suggest a method that will be able to carry out binary search in a linked list with a lower time complexity of O(log2n). The approach that has been suggested makes use of an auxiliary array that helps in indexing in the linked list, enabling the access of nodes in constant time (O(1)). As a result, the binary search operation will be much better, and its performance in the linked list implementation will be better.

Keywords: Binary search, linked list, auxiliary array, indexing, array of pointers

[This article belongs to International Journal of Data Structure Studies ]

How to cite this article:
Rejay Pavunkumar, Royal Rodrigues, Rohini Bagul, Vaishnavi Biradar. An Auxiliary Array Indexing Approach for Efficient Binary Search in Linked Lists. International Journal of Data Structure Studies. 2026; 04(01):21-28.
How to cite this URL:
Rejay Pavunkumar, Royal Rodrigues, Rohini Bagul, Vaishnavi Biradar. An Auxiliary Array Indexing Approach for Efficient Binary Search in Linked Lists. International Journal of Data Structure Studies. 2026; 04(01):21-28. Available from: https://journals.stmjournals.com/ijdss/article=2026/view=246371


References

  1. Parmar VP, Kumbharana CK. Comparing linear search and binary search algorithms to search an element from a linear list implemented through static array, dynamic array and linked list. Int J Comput Appl. 2015;121(3):13–17. doi:10.5120/21519-4495.
  2. Sanu K. Binary search in linked list. Int J Recent Technol Eng. 2019;8(4):2684-6. doi:10.35940/ijrte.D7296.118419.
  3. Joseph M, Keshwani P. Comparison between linear search and binary search algorithms. National Conference on Innovative Solutions for Rural Development of Chhattisgarh (NCISRDC), Chhattisgarh, India. 2018 Feb 23–24. p. 63–66. Available from: https://www.ijariit.com/conference-proceedings/15%20CSE%20107.pdf
  4. Datta S, Bhattacharjee P. Implementation of binary search on a singly linked list using dual pointers. Int J Comput Sci Inf Technol. 2014;5(2):1908–1910.
  5. Yadav R, Sreedevi I, Gupta D. Bio-inspired hybrid optimization algorithms for energy efficient wireless sensor networks: a comprehensive review. Electronics. 2022;11(10):1545. doi:10.3390/electronics11101545.
  6. He J, Watson LT, Ramakrishnan N, Shaffer CA, Verstak A, Jiang J, et al. Dynamic data structures for a direct search algorithm. Comput Optim Appl. 2002;23(1):5–25. doi:10.1023/A:1019992822938.
  7. Zhao H, Deep S, Koutris P. Space-time tradeoffs for conjunctive queries with access patterns. 42nd ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS), Seattle, Washington, USA. 2023. p. 59–68. doi:10.1145/3584372.3588675.
  8. Chakraborty S, Sadakane K. Indexing graph search trees and applications [Preprint]. 2019. arXiv:1906.07871. doi:10.48550/arXiv.1906.07871.
  9. Krishan K, Gupta G, Bhathal GS. Query load management: an approach for optimizing database performance. OPSEARCH. 2025:1–8. doi:10.1007/s12597-025-01012-x.
  10. Hong B, Kim G, Ahn JH, Kwon Y, Kim H, Kim J. Accelerating linked-list traversal through near-data processing. 2016 International Conference on Parallel Architectures and Compilation Techniques (PACT), Haifa, Israel. 2016. p. 113–124. doi:10.1145/2967938.2967958.
Regular Issue Subscription Review Article
Volume 04
Issue 01
Received 10/03/2026
Accepted 31/03/2026
Published 07/05/2026
Publication Time 58 Days
4

Login


My IP

PlumX Metrics