James Cutajar [James Cutajar] - Beginning Java Data Structures and Algorithms

In the preceding chapter, we introduced the concept of data structures by looking at arrays, linked lists, queues, and stacks. In this chapter, we will use some of these primitive structures to build more complex ones. We'll start the chapter by looking at hash tables, which are useful data structures for fast key-value lookup. In the second part of the chapter, we will learn about a more complex data structure that supports range queries, called binary trees.

By the end of this chapter, you will be able to:

• Describe how hash tables work
• Implement two main techniques to deal with hash collisions
• Characterize different hashing choices
• Explain the terminology, structure, and operations of binary trees
• Demonstrate various tree traversal techniques
• Define balanced binary search trees

The adjacency list representation of a graph consists of an array of |V| lists, one for each vertex in V . For each vertex u in V , there's a list containing all vertices v so that there is an edge connecting u and v in E . Figure 6.3 shows the adjacency list representation of the directed graph in Figure 6.1:

For undirected graphs, we follow a similar strategy and build the adjacency list as if it were a directed graph with two edges between each pair of vertices u and v , which are (u, v) and (v, u) .

Figure 6.4 shows the adjacency list representation of the undirected graph in Figure 6.2:

If G is a directed graph, the sum of the lengths of all the adjacency lists is |E|, as each edge constitutes a single node in one of the adjacency lists.

If G is an undirected graph, the sum of the lengths of all the adjacency lists is 2*|E|, since each edge (u, v) appears twice, that is, once in u's and once in v's adjacency list.

For both types of graphs, the adjacency list representation has the property of requiring an amount of memory equal to O(V + E).

The following code snippet shows how to create a graph using the adjacency list representation in Java:

It is common for one to have weighted graphs, that is, graphs in which each edge has an associated weight. The adjacency list representation is robust enough to support different graph variants, since we can store different edge representations in the adjacency lists.

Logarithmic complexity algorithms are very fast, and their performance hardly degrades as you increase the problem size. These types of algorithm scale really well. Code that has a runtime complexity of O(log n) is usually recognizable since it systematically divides the input in several steps. Common examples that operate in logarithmic times are database indexes and binary trees. If we want to find an item in a list, we can do it much more efficiently if the input list is sorted in some specific order. We can then use this ordering by jumping to specific positions of our list and skipping over a number of elements.

Snippet 1.7 shows an implementation of the binary search in Java. The method uses three array pointersa start, an end, and a midpoint. The algorithm starts by checking the middle element in the array. If the element is not found and is less than the value at the middle, we choose to search in the lower half; otherwise, we choose the upper half. Figure 1.3 shows the steps involved when doing a binary search. The code snippet is as follows: