Data Structures - Introduction
- Abstract data types
- Linear Data Structures
- Linked List Introduction
- Single Linked List
- Stacks using Array
- Stacks using linkedlist
- Queues using array
- Queues using linkedlist
- Stack Applications
- Infix to Postfic Converstion
- Postfix Evaluation
- Dictionaries
- Introduction to Dictionaries
- Linear list representation
- Skip list representation
- Hash Table
- Introduction Hash Table
- Hash functions
- Collision Resolution
- Separate chaining
- Open addressing
- Rehashing
- Extendible hashing
- Trees
- Introduction to Tree
- Binary trees Representation
- Binary tree traversals
- Binary Search Tree
- AVL Tree
- Red Black Tree
- Splay Tree
- B Tree
- B+ Tree
- Comparison of Trees
- Graphs
- Introduction to Graph
- Graph Representation
- Breadth-First Search
- Depth-First Search
- Sorting
- Quick Sort
- Merge Sort
- Heap Sort
- Pattern Matching
- Introduction to pattern Matching
- Brute force Pattern Matching
- Boyer–Moore Pattern Matching
- KMP Pattern Matching
- Tries
- Introduction to Tries
- Standard Trie
- Compressed tries
- Suffix Trie
Introduction to Dictionaries
In computer science, a dictionary is an abstract data type that represents an ordered or unordered list of key-value pair elements where keys are used to search/locate the elements in the list. In a dictionary ADT, the data to be stored is divided into two parts:
- Key
- Value.
Each item stored in a dictionary is represented by a key-value pair. Key is used to access the elements in the dictionary. With the key we can access value which has more information about the element.
Characteristics of Dictionary
- Key-Value Pairs: Dictionaries store data as key-value pairs where each key is unique and maps to exactly one value.
- Direct Access: The primary feature of dictionaries is to provide fast access to elements not by their position, as in lists or arrays, but by their keys.
- Dynamic Size: Like many abstract data types, dictionaries typically allow for dynamic resizing. New key-value pairs can be added, and existing ones can be removed.
- Ordering: Some dictionaries maintain the order of elements, such as ordered maps or sorted dictionaries. Others, like hash tables, do not maintain any particular order.
- Key Uniqueness: Each key in a dictionary must be unique, though different keys can map to the same value.
Fundamental Operations of Dictionary
- Insert: Add a new key-value pair to the dictionary.
- Search: Retrieve the value associated with a particular key.
- Delete: Remove a key-value pair from the dictionary.
- Update: Change the value associated with a given key.
- Keys: Return a collection of all the keys in the dictionary.
- Values: Return a collection of all the values in the dictionary.
Types of Dictionary
There are two major variations of dictionaries:
Ordered dictionary.
- In an ordered dictionary, the relative order is determined by comparison on keys.
- The order should be completely dependent on the key.
Unordered dictionary.
- In an unordered dictionary, no order relation is assumed on keys.
- Only equality operation can be performed on the keys.
Implementation of Dictionary
A dictionary can be implemented in several ways, such as
- Fixed length array.
- Linked lists.
- Hashing
- Trees (BST, Balancing BSTs, Splay trees, Tries etc.)
Next Topic :Linear list representation