DS Menu

Linear list representation

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:

Step 1: Initialization

When you initialize the dictionary, you start with an empty list. This list will hold all the key-value pairs.

dictionary = []

Step 2: Insertion

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:

If the key exists, update the associated value.
If the key does not exist, append a new key-value pair to the list.

function insert(key, value):
    for each pair in dictionary:
        if pair.key == key:
            pair.value = value
            return
    dictionary.append((key, value))

Step 3: Search

To find a value associated with a given key:

Iterate Through the List: Go through each key-value pair in the list.
Compare Keys: Check if the current key matches the search key.
Return Value if Found: If a match is found, return the associated value.

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

Step 4: Deletion

To delete a key-value pair from the dictionary:

Search for the Key: Iterate through the list to find the key.
Remove the Pair: Once the key is found, remove the key-value pair from the list.

function delete(key):
    for each pair in dictionary:
        if pair.key == key:
            remove pair from dictionary
            return

Step 5: Traversal

To traverse the dictionary and access each key-value pair:

Iterate Through the List: Go through each key-value pair in the list.
Process Each Pair: Perform the desired operation (like printing) on each pair.

function traverse():
    for each pair in dictionary:
        process(pair.key, pair.value)

Step 6: Update

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.

C Program to Creating a Ordered list Dictionary using a linked list

Program:


#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.

Advantages linear list representation of a dictionary

Simplicity: A linear list is simple and easy to implement.
Dynamic Size: The list can grow or shrink as key-value pairs are added or removed.

Disadvantages linear list representation of a dictionary

Search Time: The search time is linear in the worst case, which can be inefficient for large numbers of entries.
Insertion Time: Similar to search, if the list is being kept in sorted order, then finding the correct place to insert a new key can take linear time.
Deletion Time: Removing an entry requires a search followed by a deletion, both of which can be inefficient in a large list.

Next Topic :Skip list representation