Open Source C Library Melon: Doubly Linked List
Tags: algorithms, c, opensource
Published: 2023-02-03 05:04:41

This article introduces the use of the double-linked list of the open source C library `Melon`.

Readers who are interested in the open source C library can visit its [Github repo](https://github.com/Water-Melon/Melon).

## Introduction to Linked List
First briefly introduce what is a doubly linked list. You can refer to the following figure:

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/l7wyw5vsg124zyt92irp.png)

Simply put, a linked list is to connect nodes one by one through pointers. In the doubly linked list, each node not only records the pointer to the next node, but also records the pointer to the previous node.

**Advantages of the doubly linked list:**

The time complexity of node insertion and deletion operations is O(1), so it is very suitable for frequent insertion and deletion scenarios.

## Use of doubly linked list
Let’s define a type first:
```c
typedef struct test_s {
 int val;
} test_t;
```
In the subsequent introduction, what we have to do is to use Melon’s linked list component to transform this structure and build it into a doubly linked list.

In Melon, there are two implementations of doubly linked lists. Both implementations have their own advantages, so readers can choose to use them according to the needs.

### The first implementation
```c
#include <stdio.h>
#include <stdlib.h>
#include "mln_defs.h"

typedef struct test_s {
    int val;
    struct test_s *prev;
    struct test_s *next;
} test_t;

MLN_CHAIN_FUNC_DECLARE(test, test_t, static inline void, );
MLN_CHAIN_FUNC_DEFINE(test, test_t, static inline void, prev, next);

int main(void)
{
  int i;
  test_t *head = NULL, *tail = NULL, *t;

  for (i = 0; i < 10; ++i) {
    t = (test_t *)malloc(sizeof(test_t));
    if (t == NULL) {
        fprintf(stderr, "malloc failed.\n");
        return -1;
    }
    t->val = i;
    t->prev = t->next = NULL;
    test_chain_add(&head, &tail, t);
  }

  for (t = head; t != NULL; t = t->next) {
    printf("%d\n", t->val);
  }
  return 0;
}
```
In this code, the `main` is very simple. It uses a for loop to `malloc` 10 `test_t` structures, and then fill their val with the integer `i`. Then use the `test_chain_add` to link these nodes into a list. Finally, uses a for loop to traverse the nodes and print the value of `val`.

Here comes the question, where did `test_chain_add` come from?

We see that there are two `MLN_CHAIN_FUNC_xxx` macros before main, these two macros are defined in the header file `mln_defs.h` in Melon, and are used to define and declare the insertion and deletion functions of the linked list.

**MLN_CHAIN_FUNC_DECLARE**

- The first parameter: function name prefix
- The second parameter: custom structure type
- The third parameter: function return value and function type
- The fourth parameter: function parameter restriction attribute (not used in this example)

**MLN_CHAIN_FUNC_DEFINE**

- The first parameter: function name prefix
- The second parameter: custom structure type
- The third parameter: function return value and function type
- The fourth parameter: the name of the pointer member used to access the previous node in the custom structure
- The fifth parameter: the name of the pointer member used to access the next node in the custom structure

These two macros will define and declare two functions named: `test_chain_add` and `test_chain_del`. The prototypes of these two functions are similar to the following:

```c
void (*chain_op)(type **head, type **tail, type *node);
```

The first parameter is the address of the first pointer of the doubly linked list, the second parameter is the address of the last pointer of the doubly linked list, and the third parameter is the node pointer to be operated.

#### Features

The advantage of this implementation is that the insertion and deletion functions can be defined as `inline`, and the names of the forward and backward pointers can be changed at will. And when traversing the linked list, you only need to access these two pointers of the custom node.

The disadvantage is that users need to know the member names of the forward and backward pointers in the custom structure. And if many doubly linked lists are defined, many insertion and deletion functions need to be defined either, which will increase the size of the executable program.

### The second implementation

```c
#include "mln_list.h"
#include "mln_defs.h"
#include <stdlib.h>

typedef struct {
    int        val;
    mln_list_t node;
} test_t;

int main(void)
{
    int i;
    test_t *t;
    mln_list_t sentinel = mln_list_null();

    for (i = 0; i < 3; ++i) {
        t = (test_t *)calloc(1, sizeof(*t));
        if (t == NULL)
            return -1;
        mln_list_add(&sentinel, &t->node);
        t->val = i;
    }
    for (t = mln_container_of(mln_list_head(&sentinel), test_t, node); \
         t != NULL; \
         t = mln_container_of(mln_list_next(&t->node), test_t, node))
    {
        printf("%d\n", t->val);
    }
    return 0;
}
```

The behavior of the `main` function is exactly the same as the code of the first implementation. The difference lies in the following aspects:

1. Include `mln_list.h`
2. Instead of adding the forward and backward pointers to `test_t`, a member (`node`) of a fixed type (`mln_list_t`) is added.
3. The head and tail pointers of the doubly linked list are changed to a `mln_list_t` type variable named `sentinel`.
4. The linked list insertion function is no longer a custom prefix function, but a function with a fixed name called `mln_list_add`.
5. To access the first node of the linked list use the macro `mln_list_head`
6. To obtain the pointer to the host structure where the linked list node is located (ie `test_t` in this example), you need to use the macro `mln_container_of` defined in `mln_defs.h`.

#### Features

Advantages: Users do not need to care about the implementation details of the linked list, they only need to add `mln_list_t` type members into the custom type. And the insertion and deletion operations of the function are fixed names, respectively: `mln_list_add` and `mln_list_remove`.

Disadvantage: Access to the host node (`test_t`) to which the linked list node belongs requires the help of the macro `mln_container_of`, which does not seem as intuitive as the first implementation. And the linked list operation functions are all non-inline, so the overhead of frequent calls will be higher than the first implementation.

In fact, readers may notice that the second implementation (`mln_list.c`) is implemented by the first doubly linked list implementation.

## End
Thanks for reading.

Readers can visit the [Melon library](https://github.com/Water-Melon/Melon) for more details.

Melon is an open source C language library that is free of dependencies and out of the box, and complete documentation.