Dictionaries linear list representation in data structures

Dictionary Data Structure

Dictionary is one of the important Data Structures that is usually used to store data in the key-value format. Each element presents in a dictionary data structure compulsorily have a key and some value is associated with that particular key. In other words, we can also say that Dictionary data structure is used to store the data in key-value pairs. Other names for the Dictionary data structure are associative array, map, symbol table but broadly it is referred to as Dictionary.

A dictionary or associative array is a general-purpose data structure that is used for the storage of a group of objects.

Many popular languages add Dictionary or associative array as a primitive data type in their languages while other languages which don't consider Dictionary or associative array as a primitive data type have included Dictionary or associative array in their software libraries. A direct form of hardware-level support for the Dictionary or associative array is Content-addressable memory.

In Dictionary or associative array, the relation or association between the key and the value is known as the mapping. We can say that each value in the dictionary is mapped to a particular key present in the dictionary or vice-versa.

The various operations that are performed on a Dictionary or associative array are:

• Add or Insert: In the Add or Insert operation, a new pair of keys and values is added in the Dictionary or associative array object.
• Replace or reassign: In the Replace or reassign operation, the already existing value that is associated with a key is changed or modified. In other words, a new value is mapped to an already existing key.
• Delete or remove: In the Delete or remove operation, the already present element is unmapped from the Dictionary or associative array object.
• Find or Lookup: In the Find or Lookup operation, the value associated with a key is searched by passing the key as a search argument.

Now, let us see the usage of the dictionary data structure in different programming languages.

Python:

A sample python code to perform all the basic four operations like create, update, delete and update.

Code:

Output:

Enter the jersey number to be entered 45 Enter the player name to be entered Rohit Sharma {45: 'Rohit Sharma'} Enter the jersey number to be entered 18 Enter the player name to be entered Virat Kholi Enter the jersey number to be entered 7 Enter the player name to be entered Mahendra Singh Dhoni Enter the jersey number to be entered 42 Enter the player name to be entered Shikar Dhawan {45: 'Rohit Sharma', 18: 'Virat Kholi', 7: 'Mahendra Singh Dhoni', 42: 'Shikar Dhawan'} Enter the key whose value you want to update 42 Enter the new value that you want to assign to the key entered Shikhar Dhawan The dictionary after updating the values is: {45: 'Rohit Sharma', 18: 'Virat Kholi', 7: 'Mahendra Singh Dhoni', 42: 'Shikhar Dhawan'} Enter the key that you want to delete or remove from the dictionary object 18 The dictionary after deleting the values is: {45: 'Rohit Sharma', 7: 'Mahendra Singh Dhoni', 42: 'Shikhar Dhawan'}

In this code, we have created a dictionary object named players having key as integer and value as

Strings. We have also created functions to implement all the basic four functionalities of the dictionary that are create, delete, update, etc.

As we can see in the output of the above code, we have 4 elements as input to our dictionary object created and then update one value in the dictionary and then we deleted one value in the dictionary and in the last we have printed the final dictionary object.

Java

A sample java code to perform all the basic operations like create, delete and update.

Code:

Output:

Enter the key for the Dictionary Object name Enter the value for the Dictionary Object Nirnay Khajuria Enter the key for the Dictionary Object age Enter the value for the Dictionary Object 23 {age=23, name=Nirnay Khajuria} Enter the key of the element that you want to remove or delete age Dictionary after removing the element(s) {name=Nirnay Khajuria} Enter the key of the element that you want to search or find name The value of the key name is Nirnay Khajuria

In this code, we have created a dictionary object named dictObject having key as string and value as

Strings. We have also created functions to implement all the basic four functionalities of the dictionary that are the create, delete, update, search, etc.

As we can see in the output of the above code, we have two elements as input to our dictionary object created and then update one value in the dictionary and then we searched one value in the dictionary and in the last we have printed the final dictionary object that we have created.

CPP:

Now let us write a C++ code that will give us an idea about how to use Dictionary or associative array and their basic functionalities in C++.

Code:

Output:

1. To insert data into the Dictionary. 2. To print data from the Dictionary. 3. To delete data from the Dictionary. 4. To search data from the Dictionary. 5. To update data from the Dictionary. 0. To exit the code. Enter your choice:1 Enter the name of the country : India Enter the capital of India : Delhi 1. To insert data into the Dictionary. 2. To print data from the Dictionary. 3. To delete data from the Dictionary. 4. To search data from the Dictionary. 5. To update data from the Dictionary. 0. To exit the code. Enter your choice:1 Enter the name of the country : Dominica Enter the capital of Dominica : Roseau 1. To insert data into the Dictionary. 2. To print data from the Dictionary. 3. To delete data from the Dictionary. 4. To search data from the Dictionary. 5. To update data from the Dictionary. 0. To exit the code. Enter your choice:1 Enter the name of the country : Haiti Enter the capital of Haiti : Port-au-prince 1. To insert data into the Dictionary. 2. To print data from the Dictionary. 3. To delete data from the Dictionary. 4. To search data from the Dictionary. 5. To update data from the Dictionary. 0. To exit the code. Enter your choice:1 Enter the name of the country : USA Enter the capital of USA : Washington 1. To insert data into the Dictionary. 2. To print data from the Dictionary. 3. To delete data from the Dictionary. 4. To search data from the Dictionary. 5. To update data from the Dictionary. 0. To exit the code. Enter your choice:2 Contents of the Dictionary are : Name of the country Dominica: Name of the capital Roseau Name of the country Haiti: Name of the capital Port-au-prince Name of the country India: Name of the capital Delhi Name of the country USA: Name of the capital Washington 1. To insert data into the Dictionary. 2. To print data from the Dictionary. 3. To delete data from the Dictionary. 4. To search data from the Dictionary. 5. To update data from the Dictionary. 0. To exit the code. Enter your choice:3 Enter the name of the country that you want to delete : Haiti Element deleted successfully. 1. To insert data into the Dictionary. 2. To print data from the Dictionary. 3. To delete data from the Dictionary. 4. To search data from the Dictionary. 5. To update data from the Dictionary. 0. To exit the code. Enter your choice:2 Contents of the Dictionary are : Name of the country Dominica: Name of the capital Roseau Name of the country India: Name of the capital Delhi Name of the country USA: Name of the capital Washington 1. To insert data into the Dictionary. 2. To print data from the Dictionary. 3. To delete data from the Dictionary. 4. To search data from the Dictionary. 5. To update data from the Dictionary. 0. To exit the code. Enter your choice:4 Result of the search in the dictionary is : Enter the name of the country that you want to search : USA Capital of USA is Washington 1. To insert data into the Dictionary. 2. To print data from the Dictionary. 3. To delete data from the Dictionary. 4. To search data from the Dictionary. 5. To update data from the Dictionary. 0. To exit the code. Enter your choice:5 Enter the name of the country whose capital you want to update : India Enter the name of new capital : New-Delhi Contents of the Dictionary updated sucessfully. 1. To insert data into the Dictionary. 2. To print data from the Dictionary. 3. To delete data from the Dictionary. 4. To search data from the Dictionary. 5. To update data from the Dictionary. 0. To exit the code. Enter your choice:2 Contents of the Dictionary are : Name of the country Dominica: Name of the capital Roseau Name of the country India: Name of the capital New-Delhi Name of the country USA: Name of the capital Washington 1. To insert data into the Dictionary. 2. To print data from the Dictionary. 3. To delete data from the Dictionary. 4. To search data from the Dictionary. 5. To update data from the Dictionary. 0. To exit the code. Enter your choice:0

As we can see in the above code, we have successfully implemented all the basic operations that are search, update, insert, delete and print an object of dictionary named capitals that we have created to store the name of the countries and their respective capitals.

Different functions are created for all of the operations that are mentioned above. First, we created a dictionary and added elements to this created object. Once the insertion of the data is completed in the object, we displayed the added data. After displaying, we deleted already existing data from the dictionary object. After deletion, a searching and updation operations are performed on the dictionary object storing the name of the countries and their respective capitals that are searched and updated various elements from the dictionary object respectively.

So, this article explains the Dictionary Data Structure and what are the basic functions or operations that we can perform on a Dictionary Data Structure object. We also understood the usage of the Dictionary Data Structure in various programming languages like Java, Python, and C++ along with their functionalities that are required to perform the basic operations on this Data Structure. Other than these examples, there are various scenarios where we can use the Dictionary Data Structure. The most ideal scenario for using the Dictionary Data Structure where we need to store our data in key-value pairs.

Next TopicStructured Data and Unstructured Data

← prev next →

Data Structures

##Dictionaries A set of n records, each identified by one or more key fields.

Problem: Efficiently locate, insert and delete the record associated with any query key q.

Data structures include hash tables, skip lists and balanced/unbalanced binary search trees.

###Representations

• Unsorted arrays: for small data sets for easier maintanence. However, linear search will kill you with larger dictionaries.
• Sorted arrays: Fast binary search. Appropriate iff there are not many insertions or deletions.
• Hash tables: Great for applications with large keys (say 100-10mil).
  • A Hash function is used to map keys to integers between 0 and n - 1.
  • Maintain an array of n buckets, each typically implemented using an unsorted linked list.
  • Must deal with collisions. Open addressing can have better cache perfomance than bucketing.
  • Hash functions for strings include Horner's rule, computed in O(n).
• Binary search trees: Supports fast inserations, deletions and queries at O(log n). Balanced BSTs use local rotation operations to restructure search trees - red-black trees, AVL, 2/3 trees. B-trees for large datasets.

##Priority Queues A set of n records with ordered keys

Problem: Provide quick access to the smallest or largest key in the set.

Priority queues are great useful in simulations for maintaining a set of future events ordered by time. Enables you to retrive items not by insertion time (as in a stack or queue), nor by a key match (as in a dictionary), but by which itme has the highest priority of retrieval.

###Representations

• Sorted array or list: Efficient to identify the smallest element and deleting it by decrementing the top index. Slow insertion to maintain the order.
• Binary heaps: Supports insertion and extractMin in O(log n) time.
• Binary search trees: Effective since the smallest element is always the leftmost leaf and largest is the rightmost leaf. The min and max is found in O(log n) by tracing down the left or right pointers until the next pointer is null.

##Graphs

Graph G with n nodes/vertices and m edges
Hypergraphs are generalized graphs where each edge may link subsets of more than two vertices.

###Representations

• Adjacency matrices - n2 space:
  • Best to use a bit vector for dense graphs.
  • Frequent lookups to answer "Is (i,j) in G?"
• Adjacency lists - n + m space:
  • Suited for DFS-algorithms, sparse graphs, planar graphs (maps of countries).
  • For static graphs (no edge insertions or deletions), each edge list can be replaced by a packed array of vertex identifiers. This eliminates pointers and saves space.

###Graph Traversals: BFS, DFS

• BFS: Queue - FIFO exploring the oldest unexplored vertices first. Thus, exploration radiates out slowly from the starting vertex.
• DFS: Stack - LIFO exploring the vertices by going down a path, visiting a new neighbour if available and back-tracking when we are surrounded by previously discovered vertices. Thus, explorations quickly wander away from our starting point.

##Sets

A set is an unordered collection of unique items from a universal set.
Multi-sets permit items to have more than one occurrence.
A universe of items U = {u1, ..., un} on which is defined a collection of subsets S = {s1, ..., sn}

Problem:
(1) Test whether item in universe is an element of the subset. ui ∈ Sj
(2) Compute the union or intersection of Si and Sj
(3) Insert or delete members of S

Keeping the set sorted turns the problem of finding the union or intersection to O(n) running-time instead of O(n2). Just sweep from left to right to see what you are missing.

Note the differences from dictionaries and strings.
A collection of items not drawn from a fixed-sized universal set is a dictionary. Strings are structures where order matters - i.e, {A, B} is not the same as {B, A}.

###Representations

• Bit vectors - n space: value 1 or 0 to indicate whether element i is in S. Space efficient and fast insertion and deletion by flipping the bit. Poor performance for sparse subsets - O(n) to identify all members.
• Linked list, array or dictionaries: Contain exactly the elements in the subset. For sparse subsets, dictionaries can be more space and time efficient than bit vectors. Keep the subsets sorted for efficient union and intersection, so a linear-time traversal through both subsets identifies all duplicates.
• Boom filters: Emulate a bit vector in the absence of a fixed universal set. Hash each subset element to an integer from 0 to n and setting the corresponding bit. More space efficient for static subset applications that can torelate a small probability of error.

##Trees Red-black trees are used internally by the Standard Library as a basis for the associative container classes. A red-black tree is a balanced binary search tree with one extra attribute for each node: the colour, which is either red or black. It has the following red-black properties:

• Every node is either red or black.
• Every leaf is black.
• If a node is red, then both its children are black.
• Every simple path from a node to a descendant leaf contains the same number of black nodes.
• Guarantees O(log n) search times and can be re-balanced in O(log n) time.

AVL trees are "partially" balanced binary search trees, allowing for O(log n) time with find, insert, and delete operations. The criteria that is used to determine the "level" of "balanced-ness" is the difference between the heights of subtrees of a root in the tree. In an AVL tree the difference between the height of the right and left subtrees (or the root node) is never more than one. Whenever an item is inserted or deleted, a check is made to see if the tree has become unbalanced. If it has, balance is restored by performing a set of manipulations (called "rotations") on the tree. These rotations come in two flavors: single rotations and double rotations (and each flavor has its corresponding "left" and "right" versions).

Kd-tree and related spatial data structures hierarchically decompose space into a small number of cells, each containing a few representatives from an input set of points. Fast access to any item by position.

Problem: Given a set S of n points in k dimensions, construct a tree that partitions space by half-planes such that each item is contained in its own box-shaped region.

Typical algorithms construct kd-trees by partioning point sets. A plane cuts through one of the dimensions to equally partition the subset of points into left/right subsets. These children are again partitioned into equal halves, using planes through another dimension. Partitioning stops after log n levels, with each points in its own leaf cell.
Each box-shaped region is defined by 2k planes, where k is the number of dimensions (hence kd-tree).
kd-trees are most useful for small dimensions, 2-20. They lose effectiveness as the dimesionality increases because the retio of the volumn unit sphere in k-dimensions shrinks exponentially compared to the unit cube.

Applications: point location, nearest-neighbour search, range search, partial key search