Call for Paper - August 2020 Edition
IJCA solicits original research papers for the August 2020 Edition. Last date of manuscript submission is July 20, 2020. Read More

Speeding Up Search in Singly Linked List

Print
PDF
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
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):19-24, September 2018. BibTeX

@article{10.5120/ijca2018917892,
	author = {Sarvesh Rakesh Bhatnagar},
	title = {Speeding Up Search in Singly Linked List},
	journal = {International Journal of Computer Applications},
	issue_date = {September 2018},
	volume = {182},
	number = {18},
	month = {Sep},
	year = {2018},
	issn = {0975-8887},
	pages = {19-24},
	numpages = {6},
	url = {http://www.ijcaonline.org/archives/volume182/number18/29977-2018917892},
	doi = {10.5120/ijca2018917892},
	publisher = {Foundation of Computer Science (FCS), NY, USA},
	address = {New York, USA}
}

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

  1. 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.
  2. H. Sahni and A. Freed, Fundamentals of Data Structures in C 2nd edition, ch. 4, pp 190-195.
  3. “Defination of a linked list”. National Institute of Standards and Technology.
  4. Antonakos, James L.; Mansfield, Kenneth C., Jr. (1999). Practical Data Structures Using C/C++. Prentice-Hall. pp. 165–190. ISBN 0-13-280843-9.
  5. 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.
  6. David R. Richardson (2002), The Book on Data Structures. iUniverse, 112 pages. ISBN 0-595-24039-9, ISBN 978-0-595-24039-5.
  7. Conway, J. H. and Guy, R. K. The Book of Numbers. New York: Springer-Verlag, pp. 30-32, 1996. ISBN 0-387-97993-X
  8. Sipser, Michael (2006). Introduction to the Theory of Computation. Course Technology Inc. ISBN 0-619-21764-2.
  9. Sedgewick, R. and Wayne K(2011). Algorithms 4th ed. p.186. Pearson Education, Inc.

Keywords

Speeding Up Linked List, Improvising Speed of Linked List, Search techniques, Indexing in Linked List, Indexing techniques.