Open Data Structures in Java

“Open Data Structures in Java” explores the implementation of various data structures using Java programming language. The document delves into the design and utilization of data structures like arrays, linked lists, trees, graphs, and more. It provides insights into the practical applications of these structures in solving computational problems efficiently. Additionally, the document discusses the importance of understanding data structures for optimizing algorithm performance and enhancing overall software development skills. By leveraging Java’s capabilities, the document aims to equip readers with the knowledge and tools necessary to work with diverse data structures effectively in their programming endeavors.

Visit Open Data Structures in Java

2.7 Discussion and Exercises

Most of the data structures described in this chapter are folklore. They can be found in implementations dating back over 30 years. For example, implementations of stacks, queues, and deques, which ge...

1.8 Discussion and Exercises

Open Data Structures in Java

The List , USet , and SSet interfaces described in Section 1.2 are influenced by the Java Collections Framework [ 54 ]. These are essentially simplified versions of the List , Set , Map , SortedSet , ...

2.6 RootishArrayStack: A Space-Efficient Array Stack

Open Data Structures in Java

One of the drawbacks of all previous data structures in this chapter is that, because they store their data in one or two arrays and they avoid resizing these arrays too often, the arrays frequently a...

1.7 List of Data Structures

Open Data Structures in Java

Tables 1.1 and 1.2 summarize the performance of data structures in this book that implement each of the interfaces, List , USet , and SSet , described in Section 1.2 . Figure 1.6 shows the dependencie...

4.5 Discussion and Exercises

Open Data Structures in Java

Skiplists were introduced by Pugh [ 62 ] who also presented a number of applications and extensions of skiplists [ 61 ]. Since then they have been studied extensively. Several researchers have done ve...

1.6 Code Samples

Open Data Structures in Java

The code samples in this book are written in the Java programming language. However, to make the book accessible to readers not familiar with all of Java's constructs and keywords, the code samples h...

2.5 DualArrayDeque: Building a Deque from Two Stacks

Open Data Structures in Java

Next, we present a data structure, the DualArrayDeque that achieves the same performance bounds as an ArrayDeque by using two ArrayStack s. Although the asymptotic performance of the DualArrayDeque is...

4.4 Analysis of Skiplists

Open Data Structures in Java

In this section, we analyze the expected height, size, and length of the search path in a skiplist. This section requires a background in basic probability. Several proofs are based on the following b...

13.4 Discussion and Exercises

Open Data Structures in Java

The first data structure to provide time , , and operations was proposed by van Emde Boas and has since become known as the van Emde Boas (or stratified ) tree [ 74 ]. The original van Emde Boas struc...

3.4 Discussion and Exercises

Open Data Structures in Java

Both singly-linked and doubly-linked lists are established techniques, having been used in programs for over 40 years. They are discussed, for example, by Knuth [ 46 , Sections 2.2.3-2.2.5]. Even the ...

5.4 Discussion and Exercises

Open Data Structures in Java

Hash tables and hash codes represent an enormous and active field of research that is just touched upon in this chapter. The online Bibliography on Hashing [ 10 ] contains nearly 2000 entries. A varie...

1.5 Correctness, Time Complexity, and Space Complexity

Open Data Structures in Java

When studying the performance of a data structure, there are three things that matter most: Correctness: The data structure should correctly implement its interface. Time complexity: The running times...