A linear list representation of a dictionary involves using a simple list structure (like an array or a linked list) to store key-value pairs. Each entry in the list consists of two parts: a unique key and an associated value. Let's walk through the implementation step by step:
When you initialize the dictionary, you start with an empty list. This list will hold all the key-value pairs.
dictionary = []
To insert a new key-value pair into the dictionary:
Check for the Key's Existence: Iterate through the list to check if the given key already exists.
Update or Insert:
function insert(key, value):
for each pair in dictionary:
if pair.key == key:
pair.value = value
return
dictionary.append((key, value))
To find a value associated with a given key:
function search(key):
for each pair in dictionary:
if pair.key == key:
return pair.value
return None // Or indicate that the key was not found
To delete a key-value pair from the dictionary:
function delete(key):
for each pair in dictionary:
if pair.key == key:
remove pair from dictionary
return
To traverse the dictionary and access each key-value pair:
function traverse():
for each pair in dictionary:
process(pair.key, pair.value)
Updating a value for a specific key follows the same procedure as insertion. If the key exists, its value is updated; otherwise, the key-value pair is added.
#include <stdio.h>
#include <stdlib.h>
struct Node {
int key; // Assuming keys are integers
int value; // Assuming values are integers
struct Node* next;
} *head=NULL;
//Function to Create a New Node
struct Node *createNode(int key, int value) {
struct Node *newNode;
newNode = (struct Node*) malloc(sizeof(struct Node));
newNode->key= key;
newNode->value = value;
newNode->next = NULL;
return newNode;
}
//Search Function
int search(int key) {
struct Node *temp;
temp=head;
while (temp != NULL) {
if (temp->key == key){
return 1;
}
temp = temp->next;
}
return 0; // Return 0 or appropriate error value if not found
}
//Insertion Function
void insert(int key, int value) {
struct Node *newNode,*temp1,*temp2;
if(search(key))
{
printf("insertion not possible, Key must be unique");
}
else{
newNode=createNode(key,value);
if(head==NULL)
{
printf("%d",head);
head=newNode;
printf("\n%d",head);
}
else if(head->key > key)
{
newNode->next=head;
head=newNode;
}
else{
temp1=head;
while(temp1!=NULL && temp1->key < key)
{
temp2=temp1;
temp1=temp1->next;
}
newNode->next=temp2->next;
temp2->next=newNode;
}
}
}
//Deletion Function
void deleteNode(int key)
{
struct Node *temp1,*temp2;
if(!search(key))
{
printf("deletion not possible, Key not found");
}
else{
temp1 = head;
// If head node holds the key
if (temp1 != NULL && temp1->key == key){
head = head->next;
free(temp1);
return;
}
// Search for the key
while (temp1 != NULL && temp1->key!=key){
temp2 = temp1;
temp1 = temp1->next;
}
// If key was not present
if (temp1 == NULL) return;
temp2->next = temp1->next;
free(temp1);
}
}
void update(int key,int value)
{
struct Node *temp;
if(!search(key))
{
printf("update not possible, Key not found");
}
else{
temp=head;
while(temp!=NULL)
{
if(temp->key == key)
{
temp->value=value;
break;
}
temp=temp->next;
}
}
}
display()
{
struct Node *temp;
temp=head;
while(temp!=NULL)
{
printf("\nkey = %d, value= %d",temp->key,temp->value);
temp=temp->next;
}
}
//Main Function
int main() {
int ch,key,value;
do{
printf("\n1.insert\n2.delete\n3.update\n4.display\n5.exit");
printf("\nEnter your choice: ");
scanf("%d",&ch);
switch(ch)
{
case 1:printf("enter key and value");
scanf("%d %d",&key,&value);
insert(key,value);
break;
case 2:printf("enter key to delete");
scanf("%d",&key);
deleteNode(key);
break;
case 3:printf("enter key and newvalue to update");
scanf("%d %d",&key,&value);
update(key,value);
break;
case 4:display();
break;
case 5:break;
default: printf("\nchoice is wrong!..");
}
}while(ch!=5);
return 0;
}
This program demonstrates a simple linked list-based dictionary where each node contains a string key and an integer value. The insert function adds a new node at the beginning of the list for simplicity. The search function iterates through the list to find a node with the given key. The deleteNode function removes the node with the specified key from the list.