Data Structures

Department of Computer Science & Engineering

ANURAG Engineering College

An Autonomous Institution
(Accredited by NBA, Approved by AICTE, New Delhi, Affiliated to JNTUH, Hyderabad)

Ananthagiri (V & M), Kodad, Suryapet (Dt.) – 508206.

Data Structures CSE Dept.
UNIT – II

Dictionary:
• In C programming, a "dictionary" is not a built-in data type like it is in some other
languages (e.g., Python's dict or C#'s Dictionary). Instead, it is an abstract data type that
must be implemented using other fundamental data structures.
• The most common and efficient way to implement a dictionary in C is using a hash table.
• A dictionary, also known as a map or associative array, stores data in key -value pairs. Each
unique key is associated with a specific value, allowing for efficient retrieval of the value by
providing its corresponding key.
• A dictionary is defined as a general-purpose data structure for storing a group of objects. A
dictionary is associated with a set of keys and each key has a single associated value. When
presented with a key, the dictionary will simply return the associated value.

Representation of Dictionary:
➢ C programming does not natively provide a built-in "dictionary" or "map" data structure like
some higher-level languages (e.g., Python's dictionaries, Java's HashMaps). However, you
can implement dictionary-like functionality in C using various approaches:
➢ Parallel Arrays:
o This is a simple approach where you maintain two arrays: one for keys and one for
values. The element at index i in the key array corresponds to the element at index i
in the value array.
Example: Storing string keys and integer values
char *keys[] = {"apple", "banana", "orange"};
int values[] = {10, 20, 30};
int size = 3;
// To find the value for "banana":
for (int i = 0; i < size; i++)
{
if (strcmp(keys[i], "banana") == 0)
{
// value is values[i]
break;
}
}
Anurag Engineering College Page 2
Data Structures CSE Dept.

Limitations: Searching requires linear traversal, which can be inefficient for large datasets.
Adding/removing elements can be cumbersome if you need to maintain sorted order.

➢ Structures (Structs):
You can define a struct to hold a key-value pair and then create an array of structures.
struct KeyValuePair
{
char *key;
int value;
};

struct KeyValuePair dictionary[] =

{
{"apple", 10}, {"banana", 20}, {"orange", 30} };

Limitations: Similar to parallel arrays, searching still requires linear traversal unless you
implement a more sophisticated search algorithm (e.g., binary search on a sorted array of structs).

➢ hash tables:
Hash tables provide efficient key-value storage and retrieval. They involve a hash function
that maps keys to array indices (buckets). Collisions (multiple keys mapping to the same
index) are handled using techniques like separate chaining (linked lists in each bucket) or
open addressing.
Advantages: Offers average-case O(1) time complexity for insertion, deletion, and lookup.
Complexity: More complex to implement from scratch in C compared to arrays or structs.

➢ Binary Search Trees (BSTs):

BSTs can store key-value pairs in a hierarchical structure where left children have smaller
keys and right children have larger keys.
Advantages: Provides logarithmic time complexity (O(log N)) for search, insertion, and
deletion in a balanced tree.
Complexity: Requires implementing tree traversal, balancing mechanisms (e.g., AVL trees,
Red-Black trees) for optimal performance.

Anurag Engineering College Page 3

Data Structures CSE Dept.

The choice of representation depends on your specific requirements for performance,

memory usage, and the complexity you are willing to manage. For simple, small -scale key-
value storage, arrays or structs might suffice. For larger datasets and performance -critical
applications, hash tables or binary search trees are generally preferred.

Linear List Representation of Dictionaries:

A linear list representation of a dictionary in C programming involves storing key -value
pairs sequentially within a linear data structure. This can be implemented using either an array or a
linked list.

1. Using Arrays:
Structure:
Two parallel arrays can be used: one to store keys and another to store corresponding values.
Alternatively, an array of structures, where each structure contains a key -value pair, can be
employed.
Implementation:
Insertion: New key-value pairs are added to the end of the arrays, or inserted at a specific position
if maintaining a sorted order.
Search: A linear search is performed on the key array to find the desired key, and the
corresponding value is retrieved from the value array at the same index.
Deletion: To remove a key-value pair, the elements after the deleted element are shifted to fill the
gap.
Considerations:
Arrays offer contiguous memory allocation and direct access by index, but resizing can be
inefficient, and insertions/deletions in the middle require shifting elements.

Anurag Engineering College Page 4

Data Structures CSE Dept.

2. Using Linked Lists:

Structure:
A linked list is composed of nodes, where each node contains a key, a value, and a pointer to the
next node in the list.
Implementation:
Insertion: New nodes can be inserted at the beginning, end, or a specific position in the list by
adjusting pointers.
Search: Traversal of the linked list is performed, comparing the key of each node with the target
key until a match is found.
Deletion: The node to be deleted is located, and the pointers of the preceding and succeeding nodes
are adjusted to bypass the deleted node.
Considerations:
Linked lists provide dynamic resizing and efficient insertions/deletions, but access to elements
requires sequential traversal, which can be slower than array access for large lists.

General Characteristics of Linear List Dictionaries:

Simplicity: They are relatively straightforward to implement.
Search Complexity: Searching for a key typically involves a linear scan, resulting in O(n) time
complexity in the worst case, where 'n' is the number of elements.
Insertion/Deletion Complexity: Depending on the implementation and whether order is
maintained, insertion and deletion can also be O(n) in the worst case.

While simple, linear list representations of dictionaries are generally less efficient for large datasets
compared to other dictionary implementations like hash tables or balanced binary search trees,
which offer faster average-case performance for search, insertion, and deletion operations.

Anurag Engineering College Page 5

Data Structures CSE Dept.

Skip List Representation of a Dictionaries:

A skip list provides an efficient, probabilistic data structure for representing dictionaries in
C programming, offering performance comparable to balanced trees like AVL or Red -Black trees
but with a simpler implementation.
A skip list is an advanced data structure that incorporates the principles of a linked list, but
with the addition of multiple layers that allow it to skip over elements from the previous layer. As a
type of randomized data structure, skip lists offer efficient average-case performance for key
operations such as insertion, search, and deletion.
Structure:
Layers of Linked Lists:
A skip list consists of multiple levels of sorted linked lists. The bottom layer (Layer 0)
contains all elements of the dictionary, sorted by their keys. Each subsequent higher layer contains
a subset of the elements from the layer below it, also sorted.
Nodes:
Each node in a skip list typically contains:
➢ A key for sorting and searching.
➢ A value associated with the key (the dictionary entry).
➢ An array of forward pointers, where forward[i] points to the next node in the same layer i.
Head Node:
A special "head" node exists, which has forward pointers for each level, initially pointing to
the head node itself or NULL.
Probabilistic Level Assignment:
When a new element is inserted, its level (how many layers it will span) is determined
probabilistically, often using a "coin flip" mechanism. This ensures that, on average, the height of
the skip list is logarithmic to the number of elements, leading to efficient operations.
Operations:
Search:
To search for a key, start from the highest level of the skip list. Traverse forward in the
current level until the next node's key is greater than or equal to the target key. If the next node's
key is greater, drop down to the next lower level and repeat the process. If the next node's key
matches the target, the element is found.

Anurag Engineering College Page 6

Data Structures CSE Dept.

Insertion:
To insert a new key-value pair:
➢ Determine the random level for the new node.
➢ Search for the correct insertion point at each relevant level, keeping track of the update
pointers (the nodes whose forward pointers will need to be adjusted).
➢ Create the new node with its assigned level.
➢ Adjust the forward pointers of the update nodes to link in the new node.

Deletion:
To delete a key:
➢ Search for the element to be deleted, again keeping track of update pointers.
➢ If found, adjust the forward pointers of the update nodes to bypass the deleted node.
➢ Deallocate the memory of the deleted node.

C Implementation Considerations:
Node Structure:
Define a struct for nodes, including the key, value, and a dynamic array of snode** forward
pointer.
Skip List Structure:
Define a struct for the skip list itself, including the maximum level, current level, size, and a
pointer to the header node.
Memory Allocation:
Use malloc and free for dynamic memory management of nodes and pointer arrays.
Random Level Generation:
Implement a function to generate random levels for new nodes, typically using rand() and a
probability factor.

Anurag Engineering College Page 7

Data Structures CSE Dept.

Skip List Representation:

Anurag Engineering College Page 8

Data Structures CSE Dept.

Skip list insertion operation:

Now consider a case in which we want to insert Key=5Key=5 in the above-illustrated skip
list. We will start from the top layer, which is Layer 2. We will compare the key to the right of the
current node. We will move down if the key is greater than or equal to the right of the current node
value. Otherwise, we will move forward. If we reach layer 0, we will place the key instead of
moving down and set the pointers accordingly.
When the key is inserted, we need to decide whether this key needs to be promoted to the upper
layers. This criterion is determined based on a coin toss; we will promote the key to the upper layer
if we encounter a head.
We will stop promoting the key only if we encounter a tail during the coin toss. Below is a diagram
showing the insertion Key=5Key=5 in the skip list.

So, 5 will be placed between 2 and 8. To promote 5, we will perform a coin toss as illustrated
below. We keep promoting 5 to the next layer until the coin toss gives us a tail.

Anurag Engineering College Page 9

Data Structures CSE Dept.

Skip list search operation:

Follow the below-mentioned steps if you want to delete a key in the skip list.
1. Start from the top layer of the skip list.
2. Move forward until you find a node whose value is greater than the key. In case it is small,
move down.
3. If the node’s value equals the key, return the node.
4. If not found, then repeat steps 2–3.

Anurag Engineering College Page 10

Data Structures CSE Dept.

Skip list deletion operation:

We'll apply the same steps in searching for a key. The only difference is that we'll keep
track of the key found at the layer because we have to delete the key at every layer. We will delete
the key with the value 2020 in the diagram below.

Anurag Engineering College Page 11

Data Structures CSE Dept.

Hash Table Representation of Dictionaries:

In C programming, a dictionary is commonly implemented using a hash table. A hash table
is a data structure that stores key-value pairs and allows for efficient retrieval of values based on
their corresponding keys.
Here's how a hash table represents a dictionary in C:
Underlying Array (Buckets):
A hash table uses a fixed-size array as its primary storage. Each element of this array is
often referred to as a "bucket" or "slot."
Hash Function:
A crucial component is the hash function. This function takes a key as input and computes
an integer "hash code" or "hash value." The goal of the hash function is to distribute keys as evenly
as possible across the array's indices.
Mapping Keys to Indices:
The hash code generated by the hash function is then typically used in conjunction with the
modulo operator (%) and the array's size to determine the specific index (bucket) where the key -
value pair should be stored.
index = hash_function(key) % array_size;
Collision Handling:
Since different keys can potentially map to the same index (a "collision"), a strategy is
needed to handle these. Common methods include:
Separate Chaining: Each bucket stores a linked list (or another data structure like a dynamic
array) of key-value pairs that hash to that same index. When searching for a key, the hash function
leads to the correct bucket, and then the linked list is traversed to find the specific key.
Open Addressing: If a collision occurs, the system probes for the next available empty slot in the
array using techniques like linear probing, quadratic probing, or double hashing.
Key-Value Pair Storage:
Each element stored within the hash table (whether directly in a bucket or within a linked list in a
bucket) is a structure or union containing both the key and its associated value.

Anurag Engineering College Page 12

Data Structures CSE Dept.

In essence, a C dictionary implemented with a hash table provides:

Fast Average-Case Performance:
Operations like insertion, deletion, and lookup typically achieve O(1) average time
complexity due to the direct mapping provided by the hash function.
Collision Management:
Mechanisms are in place to handle instances where multiple keys map to the same location,
ensuring data integrity.
Dynamic Sizing (Optional):
Many implementations incorporate resizing logic (e.g., rehashing when a certain "load
factor" is exceeded) to maintain performance as the number of entries grows.

Hash Function:
The core component of a hash table is the hash function, which maps a given key to an
index within an array (the hash table). This index indicates where the corresponding value should
be stored or retrieved.

Purpose of a Hash Function:

• Mapping Keys to Indices:
The primary role is to transform a key (e.g., a string, an integer) into an integer index that can be
used to access an element in the hash table's underlying array.
• Efficiency:
A good hash function aims to distribute keys uniformly across the hash table, minimizing collisions
and enabling near O(1) average-case time complexity for insertion, deletion, and search operations.

Anurag Engineering College Page 13

Data Structures CSE Dept.

Common Types of Hash Functions (Simplified for C Context):

• Division Method:
➢ h(key) = key % table_size
➢ This method is simple but can lead to poor distribution if table_size is not a prime
number.
• Multiplication Method:
➢ h(key) = floor(table_size * (key * A mod 1)) where A is a constant between 0 and 1.
➢ This method can offer better distribution and is less sensitive to the choice of table_size.
• Folding Method:
➢ Breaks the key into parts, folds (adds) them together, and then applies a modulus
operation. Useful for multi-part keys like strings.
• Mid-Square Method:
➢ Square the key and then extract a portion of the middle digits to form the hash.

Anurag Engineering College Page 14

Data Structures CSE Dept.

Collision Resolution Techniques:

Collision resolution techniques in hashing are methods for managing hash collisions, which
occur when two different keys hash to the same index.
The two main categories are Separate Chaining (or open hashing), where each hash table
slot points to a linked list of elements, and Open Addressing (or closed hashing), where colliding
keys are placed in other empty slots within the table itself. Common open addressing methods
include Linear Probing (checking the next sequential slot), Quadratic Probing (checking slots
using a quadratic function), and Double Hashing (using a second hash function to determine the
step size).

Anurag Engineering College Page 15

Data Structures CSE Dept.

Separate Chaining (Open Hashing):

• How it works: When a collision occurs, the colliding element is added to a separate data
structure, typically a linked list, associated with that hash table index.
• Pros: Simple to implement and handle high load factors effectively.
• Cons: Requires extra space for the linked lists and can have slower access times due to
pointer traversal.
Example:
Using the hash function ‘key mod 7’, insert the following sequence of keys in the hash table-
50, 700, 76, 85, 92, 73 and 101
Use separate chaining technique for collision resolution.

The given sequence of keys will be inserted in the hash table as-

Step-01:

• Draw an empty hash table.

• For the given hash function, the possible range of hash values is [0, 6].
• So, draw an empty hash table consisting of 7 buckets as-

Anurag Engineering College Page 16

Data Structures CSE Dept.

Step-02:
• Insert the given keys in the hash table one by one.
• The first key to be inserted in the hash table = 50.
• Bucket of the hash table to which key 50 maps = 50 mod 7 = 1.
• So, key 50 will be inserted in bucket-1 of the hash table as-

Step-03:
• The next key to be inserted in the hash table = 700.
• Bucket of the hash table to which key 700 maps = 700 mod 7 = 0.
• So, key 700 will be inserted in bucket-0 of the hash table as-

Anurag Engineering College Page 17

Data Structures CSE Dept.

Step-04:
• The next key to be inserted in the hash table = 76.
• Bucket of the hash table to which key 76 maps = 76 mod 7 = 6.
• So, key 76 will be inserted in bucket-6 of the hash table as-

Step-05:
• The next key to be inserted in the hash table = 85.
• Bucket of the hash table to which key 85 maps = 85 mod 7 = 1.
• Since bucket-1 is already occupied, so collision occurs.
• Separate chaining handles the collision by creating a linked list to bucket -1.
• So, key 85 will be inserted in bucket-1 of the hash table as-

Anurag Engineering College Page 18

Data Structures CSE Dept.

Step-06:
• The next key to be inserted in the hash table = 92.
• Bucket of the hash table to which key 92 maps = 92 mod 7 = 1.
• Since bucket-1 is already occupied, so collision occurs.
• Separate chaining handles the collision by creating a linked list to bucket -1.
• So, key 92 will be inserted in bucket-1 of the hash table as-

Step-07:
• The next key to be inserted in the hash table = 73.
• Bucket of the hash table to which key 73 maps = 73 mod 7 = 3.
• So, key 73 will be inserted in bucket-3 of the hash table as-

Anurag Engineering College Page 19

Data Structures CSE Dept.

Step-08:
• The next key to be inserted in the hash table = 101.
• Bucket of the hash table to which key 101 maps = 101 mod 7 = 3.
• Since bucket-3 is already occupied, so collision occurs.
• Separate chaining handles the collision by creating a linked list to bucket -3.
• So, key 101 will be inserted in bucket-3 of the hash table as-

Anurag Engineering College Page 20

Data Structures CSE Dept.

Open Addressing (Closed Hashing):

In open addressing, all keys are stored directly within the hash table. When a collision happens,
the algorithm probes for the next available slot.
• Linear Probing:
• How it works: If a slot is occupied, the algorithm checks the next slot sequentially
(index + 1) until an empty slot is found.
• Pros: Good for cache performance because it accesses nearby slots.
• Cons: Suffer from primary clustering, where occupied slots group together, leading
to long sequences of occupied slots and slower lookups.
Example:
Using the hash function ‘key mod 7’, insert the following sequence of keys in the hash table-
50, 700, 76, 85, 92, 73 and 101
Use linear probing technique for collision resolution.

The given sequence of keys will be inserted in the hash table as-
Step-01:
• Draw an empty hash table.
• For the given hash function, the possible range of hash values is [0, 6].
• So, draw an empty hash table consisting of 7 buckets as-

Anurag Engineering College Page 21

Data Structures CSE Dept.

Step-02:
• Insert the given keys in the hash table one by one.
• The first key to be inserted in the hash table = 50.
• Bucket of the hash table to which key 50 maps = 50 mod 7 = 1.
• So, key 50 will be inserted in bucket-1 of the hash table as-

Step-03:
• The next key to be inserted in the hash table = 700.
• Bucket of the hash table to which key 700 maps = 700 mod 7 = 0.
• So, key 700 will be inserted in bucket-0 of the hash table as-

Anurag Engineering College Page 22

Data Structures CSE Dept.

Step-04:
• The next key to be inserted in the hash table = 76.
• Bucket of the hash table to which key 76 maps = 76 mod 7 = 6.
• So, key 76 will be inserted in bucket-6 of the hash table as-

Step-05:
• The next key to be inserted in the hash table = 85.
• Bucket of the hash table to which key 85 maps = 85 mod 7 = 1.
• Since bucket-1 is already occupied, so collision occurs.
• To handle the collision, linear probing technique keeps probing linearly until an empty
bucket is found.
• The first empty bucket is bucket-2.
• So, key 85 will be inserted in bucket-2 of the hash table as-

Anurag Engineering College Page 23

Data Structures CSE Dept.
Step-06:
• The next key to be inserted in the hash table = 92.
• Bucket of the hash table to which key 92 maps = 92 mod 7 = 1.
• Since bucket-1 is already occupied, so collision occurs.
• To handle the collision, linear probing technique keeps probing linearly until an empty
bucket is found.
• The first empty bucket is bucket-3.
• So, key 92 will be inserted in bucket-3 of the hash table as-

Step-07:
• The next key to be inserted in the hash table = 73.
• Bucket of the hash table to which key 73 maps = 73 mod 7 = 3.
• Since bucket-3 is already occupied, so collision occurs.
• To handle the collision, linear probing technique keeps probing linearly until an empty
bucket is found.
• The first empty bucket is bucket-4.
• So, key 73 will be inserted in bucket-4 of the hash table as-

Anurag Engineering College Page 24

Data Structures CSE Dept.

Step-08:
• The next key to be inserted in the hash table = 101.
• Bucket of the hash table to which key 101 maps = 101 mod 7 = 3.
• Since bucket-3 is already occupied, so collision occurs.
• To handle the collision, linear probing technique keeps probing linearly until an empty
bucket is found.
• The first empty bucket is bucket-5.
• So, key 101 will be inserted in bucket-5 of the hash table as-

Anurag Engineering College Page 25

Data Structures CSE Dept.

• Quadratic Probing:
• How it works: After a collision, the algorithm searches for the next available slot
using a quadratic function (e.g., index + 1², index + 2², index + 3², etc.).
• Pros: Better at reducing primary clustering compared to linear probing.
• Cons: Can suffer from secondary clustering, where keys that initially hash to the
same slot follow the same probe sequence.
Example:
Using the hash function ‘key mod 10’, insert the following sequence of keys in the hash table-
18, 89, 21, 58, and 68
Use Quadratic probing technique for collision resolution.

Anurag Engineering College Page 26

Data Structures CSE Dept.

• Double Hashing:
• Double hashing is a computer programming technique. Double hashing is hashing
collision resolution technique
• Double Hashing uses 2 hash functions and hence called double hashing.
• How it works: A second hash function is used to determine the step size for probing,
meaning each key has a unique probe sequence based on two hash values.
• Pros: Significantly reduces clustering issues as different keys have different probe
sequences, leading to better overall performance.
• Cons: More complex to implement and has poorer cache performance due to the less
sequential nature of probing.

Double Hashing - Hash Function 1 or First Hash Function - formula

h i = ( Hash(X) + F(i) ) % Table Size
where
• F(i) = i * hash 2 (X)
• X is the Key or the Number for which the hashing is done
• i is the i th time that hashing is done for the same value. Hashing is repeated only when
collision occurs
• Table size is the size of the table in which hashing is done
This F(i) will generate the sequence such as hash 2 (X), 2 * hash 2 (X) and so on.

Double Hashing - Hash Function 2 or Second Hash Function - formula

Second hash function is used to resolve collision in hashing
We use second hash function as
hash2 (X) = R - (X mod R)
where
• R is the prime number which is slightly smaller than the Table Size.
• X is the Key or the Number for which the hashing is done

Let us consider the same example in which we choose R = 7.

Anurag Engineering College Page 27

Data Structures CSE Dept.

Double Hashing Example:

Key Hash Function h(X) Index Collision Alt Index

79 h0 (79) = ( Hash(79) + F(0)) % 10 9

= ((79 % 10) + 0) % 10 =9

28 h0 (28) = ( Hash(28) + F(0)) % 10 8

= ((28 % 10) + 0) % 10 =8

39 h0 (39) = ( Hash(39) + F(0)) % 10 9 first

= ((39 % 10) + 0) % 10 =9 collision
occurs

h1 (39) = ( Hash(39) + F(1)) % 10 2 2

= ((39 % 10) + 1(7-(39 % 7))) % 10
= (9 + 3) % 10 =12 % 10 =2

68 h0 (68) = ( Hash(68) + F(0)) % 10 8 collision

= ((68 % 10) + 0) % 10 =8 occurs

h1 (68) = ( Hash(68) + F(1)) % 10 0 0

= ((68 % 10) + 1(7-(68 % 7))) % 10
= (8 + 2) % 10 =10 % 10 =0

89 h0 (89) = ( Hash(89) + F(0)) % 10 9 collision

= ((89 % 10) + 0) % 10 =9 occurs

h1 (89) = ( Hash(89) + F(1)) % 10 0 Again

= ((89 % 10) + 1(7-(89 % 7))) % 10 = (9 collision
+ 2) % 10 =10 % 10 =0 occurs

h2 (89) = ( Hash(89) + F(2)) % 10 3 3

= ((89 % 10) + 2(7-(89 % 7))) % 10 = (9
+ 4) % 10=13 % 10 =3

Anurag Engineering College Page 28

Data Structures CSE Dept.

A Closed Hash Table using Double Hashing

Anurag Engineering College Page 29