Gain insights into array-based and linked list-based data structures, explore advanced structures like skiplists and hashing, and discover template-based collections for efficient data storage and retrieval.

java.tar.gz

Data structures and algorithms are essential in computer science since they play a crucial role in efficient information retrieval and processing, dealing with files, storing contacts on phones, social networks and web searches.

In this course, you’ll learn about the array-based implementation of various linear data structures, stack, and queues. You’ll also learn about linked list-based implementation. Next, you’ll explore advanced data structures like skiplists and hashing. You’ll learn how to implement a variety of trees and graphs, and data structures related to bits of an integer. Toward the end of the course, you’ll learn the implementation of structures based on external storage.

After completing this course, you’ll be able to create reusable programs with template-based collections that can efficiently analyze how to optimize the storage and retrieval of very large amounts of data. Overall, this course will enhance your productivity and performance as a software developer.

Data Structures with Generic Types in Python

# Additional notes
Skiplists were introduced by #key# Pugh: W. Pugh. Skip lists: A probabilistic alternative to balanced trees. Communications of the ACM, 33(6):668–676, 1990. #key# who also presented a number of applications and #key# extensions of skiplists: W. Pugh. A skip list cookbook. Technical report, Institute for Advanced Computer Studies, Department of Computer Science, University of Maryland, College Park, 1989. #key#. Since then they have been studied extensively. Several researchers have done very precise #key# analyses: P. Kirschenhofer, C. Martinez, and H. Prodinger. Analysis of an optimized search algorithm for skip lists. Theoretical Computer Science, 144:199–220, 1995. #key# of the expected length and variance of the length of the #key# search path: P. Kirschenhofer and H. Prodinger. The path length of random skip lists. Acta Informatica, 31:775–792, 1994. #key# for the $i$th element in a #key# skiplist: T. Papadakis, J. I. Munro, and P. V. Poblete. Average search and update costs in skip lists. BIT, 32:316–332, 1992. #key#. #key# Deterministic versions: J. I. Munro, T. Papadakis, and R. Sedgewick. Deterministic skip lists. In Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms (SODA’92), pages 367–375, Philadelphia, PA, USA, 1992. Society for Industrial and Applied Mathematics. #key#, #key# biased: A.Bagchi,A.L.Buchsbaum,andM.T.Goodrich.Biasedskiplists.In P. Bose and P. Morin, editors, Algorithms and Computation, 13th Inter- national Symposium, ISAAC 2002 Vancouver, BC, Canada, November 21–23, 2002, Proceedings, volume 2518 of Lecture Notes in Computer Science, pages 1–13. Springer, 2002. #key# #key# versions: F. Ergun, S. C. Sahinalp, J. Sharp, and R. Sinha. Biased dictionaries with fast insert/deletes. In Proceedings of the thirty-third annual ACM symposium on Theory of computing, pages 483–491, New York, NY, USA, 2001. ACM. #key#, and #key# self-adjusting versions: P. Bose, K. Dou ̈ıeb, and S. Langerman. Dynamic optimality for skip lists and b-trees. In S.-H. Teng, editor, Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2008, San Francisco, California, USA, January 20–22, 2008, pages 1106– 1114. SIAM, 2008. #key# of skiplists have all been developed. Skiplist implementations have been written for various languages and frameworks and have been used in #key# open-source database systems: Redis. URL: http://redis.io/ [cited 2011-07-20]. #key#. A variant of skiplists is used in the #key# HP-UX: HP-UX process management white paper, version 1.3, 1997. #key# operating system kernel’s process management structures.

Discover more aspects regarding skiplists.

Overview

Array-Based Lists

Linked Lists

Skiplists

Hash Tables

Binary Trees

Random Binary Search Trees

Scapegoat Trees

Red-Black Trees

Heaps

Sorting Algorithms

Graphs

Data Structures for Integers

External Memory Searching

Wrap Up

Discussion on Skiplists

Additional notes