Understanding Association List Data Type

In the realm of data structures, association lists (also known as alists) are a fundamental concept that allows us to map keys to values. These lists are particularly useful for scenarios where we need a simple and flexible way to store and retrieve data based on unique keys. This article will explore the basics of association lists and demonstrate how to implement and use them in C and TypeScript.

What is an Association List?

An association list is a collection of pairs, where each pair consists of a key and a value. The key is unique within the list, and it is used to retrieve the corresponding value. Association lists can be thought of as a simplified form of dictionaries or hash tables.?

Implementing an association list in C involves using structures and pointers.

First, we define a structure to represent each node in the association list:

// C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct Node {
    char *key;
    char *value;
    struct Node *next;
} Node;

// TypeScript

interface AssocList<T> {
    [key: string]: T;
}        

Next, we create a function to initialize a new node:

// C

Node* createNode(char key, char value) {
    Node newNode = (Node)malloc(sizeof(Node));
    newNode->key = strdup(key);
    newNode->value = strdup(value);
    newNode->next = NULL;
    return newNode;
}

// TypeScript

function insert<T>(alist: AssocList<T>, key: string, value: T): void {
    alist[key] = value;
}
        

To insert a new key-value pair, we traverse the list and add the new node at the end:

// C 

void insert(Node **head, char key, char value) {
    Node *newNode = createNode(key, value);
    if (*head == NULL) {
        *head = newNode;
    } else {
        Node temp = head;
        while (temp->next != NULL) {
            temp = temp->next;
        }
        temp->next = newNode;
    }
}

// Typescript

function insert<T>(alist: AssocList<T>, key: string, value: T): void {
    alist[key] = value;
}
        

To search for a value by key, we iterate through the list and compare keys:

// C

char* search(Node head, char key) {
    Node *temp = head;
    while (temp != NULL) {
        if (strcmp(temp->key, key) == 0) {
            return temp->value;
        }
        temp = temp->next;
    }
    return NULL;
}

// TypeScript

function search<T>(alist: AssocList<T>, key: string): T | undefined {
    return alist[key];
}
        

Here is an example of how to use these functions:

// C

int main() {
    Node *alist = NULL;
    insert(&alist, "name", "Alice");
    insert(&alist, "age", "25");
    insert(&alist, "city", "New York");
    printf("Name: %s\n", search(alist, "name"));
    printf("Age: %s\n", search(alist, "age"));
    printf("City: %s\n", search(alist, "city"));
    return 0;
}

// TypeScript

const alist: AssocList<string> = {};
insert(alist, "name", "Alice");
insert(alist, "age", "25");
insert(alist, "city", "New York");

console.log("Name:", search(alist, "name"));
console.log("Age:", search(alist, "age"));
console.log("City:", search(alist, "city"));
        

Association lists are a versatile and straightforward way to manage key-value pairs. Whether you're working in a low-level language like C or a high-level language like TypeScript, understanding how to implement and use association lists can significantly enhance your ability to manage data effectively. By leveraging the power of these lists, you can create more efficient and organized code, capable of handling a variety of tasks with ease.