Dynamic Data Structures

A dynamic data structure is a set of elements in memory that has the adaptability to expand or shrink. This ability empowers a software engineer to control precisely how much memory is used. Dynamic data structures are used for handling generic data in a key-value store. They can be used in distributed caching and storage management. Dynamic data structures are valuable in many circumstances in which dynamic addition or deletion of elements occur. They are comparable in capacity to a smaller relational database or an in-memory database. These data structures are used in marketing and customer relationship management applications. Dictionaries, TreeSets, and sequences are examples of dynamic data structures.

In this chapter, we will explain what dictionaries, TreeSets, and sequences are and show you how they are implemented with the help of code examples...

Technical requirements

Install Go Version 1.10 from https://golang.org/doc/install for your OS.

The GitHub URL for the code in this chapter is as follows: https://github.com/PacktPublishing/Learn-Data-Structures-and-Algorithms-with-Golang/tree/master/Chapter07.

Dictionaries

A dictionary is a collection of unique key and value pairs. A dictionary is a broadly useful data structure for storing a set of data items. It has a key, and each key has a solitary item associated with it. When given a key, the dictionary will restore the item associated with that key. These keys can be of any type: strings, integers, or objects. Where we need to sort a list, an element value can be retrieved utilizing its key. Add, remove, modify, and lookup operations are allowed in this collection. A dictionary is similar to other data structures, such as hash, map, and HashMap. The key/value store is used in distributed caching and in memory databases. Arrays differ from dictionaries in how the data is accessed. A set has unique items, whereas a dictionary can have duplicate values.

Dictionary data structures are used in the following streams:

• Phone directories...

TreeSets

TreeSets are used in marketing and customer relationship management applications. TreeSet is a set that has a binary tree with unique elements. The elements are sorted in a natural order. In the following code snippet, TreeSet creation, insertion, search, and stringify operations are presented. TreeSet allows only one null value if the set is empty. The elements are sorted and stored as elements. The add, remove, and contains functions cost log(n) on TreeSets:

///main package has examples shown
// in Go Data Structures and algorithms book
package main

// TreeSet class
type TreeSet struct {
  bst *BinarySearchTree
}

We will discuss the different TreeSet methods in the following sections.

InsertTreeNode method

The InsertTreeNode...

Sequences

A sequence is a set of numbers that are grouped in a particular order. The number of elements in the stream can be infinite, and these sequences are called streams. A subsequence is a sequence that's created from another sequence. The relative positions of the elements in a subsequence will remain the same after deleting some of the elements in a sequence.

In the following sections, we will take a look at different sequences such as the Farey sequence, Fibonacci sequence, look-and-say, and Thue–Morse.

Farey sequence

A Farey sequence consists of reduced fractions with values between zero and one. The denominators of the fractions are less than or equal to m, and organized in ascending order. This sequence...

Summary

This chapter covered the contains, put, remove, find, reset, NumberOfElements, getKeys, and getValues methods of the dictionary data structure. The InsertTreeNode, Delete, Search, and stringify TreeSet operations have been explained in detail, and code examples were provided. The BinarySearchTree structure has been presented in code, along with the InsertElement, InOrderTraversal, PreOrderTraverseTree, SearchNode, and RemoveNode functions.

The next chapter covers algorithms such as sorting, searching, recursion, and hashing.

Questions

1. How do you ensure a BinarySearchTree is synchronized?
2. Which method is called to postpone the invocation of a function?
3. How do you define dictionary keys and values with custom types?
4. How do you find the length of a map?
5. What keyword is used to traverse a list of treeNodes in a tree?
6. In a Farey sequence, what are the real numbers in the series called?
7. What is a Fibonacci number?
8. How do you convert an integer into a string?
9. What method is used to convert a byte into a string?
10. What method is called to add elements to a dictionary?

Further reading

The following books are recommended if you want to learn more about dynamic data structures:

• Design Patterns, by Erich Gamma, Richard Helm, Ralph Johnson, and John Vlissides
• Introduction to Algorithms – Third Edition, by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein
• Data structures and Algorithms: An Easy Introduction, by Rudolph Russell