The week's pick
Reseach Article
Speeding Up Search in Singly Linked List
| International Journal of Computer Applications |
| Foundation of Computer Science (FCS), NY, USA |
| Volume 182 - Number 18 |
| Year of Publication: 2018 |
| Authors: Sarvesh Rakesh Bhatnagar |
10.5120/ijca2018917892
|
Sarvesh Rakesh Bhatnagar . Speeding Up Search in Singly Linked List. International Journal of Computer Applications. 182, 18 ( Sep 2018), 19-24. DOI=10.5120/ijca2018917892
Abstract
Different Search techniques were developed over the period, each of them having certain advantages and disadvantages. Improving the search techniques result in better performance thus better efficiency. Data Structures can be improved by some minor tweaks leading to improving the quality of data structure. In Linked List, searching is slow due to sequential search requirement, which can be improved by properly indexing the list thus improving speed. There are various indexing methods such as uniform indexing, Tree based indexing, dense indexing, clustered indexing, etc. This paper focuses on the indexed based searching using an additional lane linked list and equips a method to incorporate different series such as squared series and cubic series which further leads to speed enhancement as compared with traditional indexing counterparts due to their nature of increasing gaps between sequential indexes, which reduces the dependency on the main linked list and increasing the dependency on the lane linked list thus using the nature of series more efficiently as the list size increases.
References
- Cormen, Thomas H.; Charles E. Leiserson; Ronald L. Rivest; Clifford Stein(2003). Introduction to Algorithms. MIT Press. pp. 205-213 & 501-505. ISBN 0-262-03293-7.
- H. Sahni and A. Freed, Fundamentals of Data Structures in C 2nd edition, ch. 4, pp 190-195.
- “Defination of a linked list”. National Institute of Standards and Technology.
- Antonakos, James L.; Mansfield, Kenneth C., Jr. (1999). Practical Data Structures Using C/C++. Prentice-Hall. pp. 165–190. ISBN 0-13-280843-9.
- Knuth, Donald (1977). “Section 6.1: Sequential Searching,". Sorting and Searching. The Art of Computer Programming. 3 (3rd ed.). Addison-Wesley. pp. 396–408. ISBN 0-201-89685-0.
- David R. Richardson (2002), The Book on Data Structures. iUniverse, 112 pages. ISBN 0-595-24039-9, ISBN 978-0-595-24039-5.
- Conway, J. H. and Guy, R. K. The Book of Numbers. New York: Springer-Verlag, pp. 30-32, 1996. ISBN 0-387-97993-X
- Sipser, Michael (2006). Introduction to the Theory of Computation. Course Technology Inc. ISBN 0-619-21764-2.
- Sedgewick, R. and Wayne K(2011). Algorithms 4th ed. p.186. Pearson Education, Inc.
Index Terms
Keywords