13 KiB
Introduction
A linked list is a data structure in which data elements are logically continuous but can be physically stored in a dispersed manner. It can link multiple data blocks of the same type into a complete sequence through pointers and plays an important role in the implementation of data structures.
The dList module is a general-purpose doubly linked list module, which is very similar to the sList module. The difference lies in that the pointer field has been changed from a single pointer in the singly linked list to two pointers (one pointing to the next element and one pointing to the previous element). As a result, there are also differences in the storage structure. The sList is a unidirectional open-loop structure, while the dList is a bidirectional closed-loop structure (with the head and tail connected to form a ring).
In terms of the API, its usage is basically the same as that of sList (although the underlying implementation is different). The comparison of the rest of the performance, advantages, and disadvantages is shown below.
Interface
Creating a dList
dList *dList_create(void);
In dList, dList is both a linked list and a node (because a node can be regarded as a linked list with a length of 1). So this method is used to create an empty linked list with a length of 1 (that is, to create an empty node).
Deleting a dList
void dList_delete(dList *list);
This method will delete the linked list (including all of its nodes).
Setting and Getting the Content of a dList Node
int dList_set(dList *list, void* data, int size);
int dList_get(dList *list, void* data, int size);
After a node is created, its data field does not have content initially. You need to use the dList_set method to set the content of its data field, and you can use the dList_get method to get the content of the node's data field. The dList_set method will overwrite the original data, and you can also specify size as 0 to delete the data content of the dList node.
static void test_set(void)
{
dList *list = NULL;
int dataInt = 3;
char *dataString = "Hello dList";
list = dList_create();
if (!list)
{
printf("dList_create Fail!\r\n");
return;
}
printf("dList_create Success!\r\n");
dList_set(list, &dataInt, sizeof(dataInt));
printf("list->data %d\r\n", dList_ref(list, int));
dList_set(list, dataString, strlen(dataString) + 1);
printf("list->data %s\r\n", ((char *)(list->data)));
dList_delete(list);
}
Result:
dList_create Success!
list->data 3
list->data Hello dList
The dList_ref in the example is for data reference, and its specific usage is described below.
Inserting Data into a dList
dList *dList_insert(dList **listRef, int index, void *data, int size);
The method for inserting data is more convenient to use. It saves the steps of creating a node and setting data (even when inserting at the head of the linked list, the creation can be omitted and completed internally by this method), and it can flexibly insert specified data into the specified position.
static void test_insert(void)
{
dList *list = NULL;
for (int i = 0; i < 2; i++)
{
if (!dList_insert(&list, -1, &i, sizeof(i))) goto FAIL;
}
int i = 100;
if (!dList_insert(&list, -1, &i, sizeof(i))) goto FAIL;
dList_forEachForward(list, n)
{
printf("data %d\r\n", dList_ref(n, int));
}
printf("------------\r\n");
dList_forEachReverse(list, n)
{
printf("data %d\r\n", dList_ref(n, int));
}
FAIL:
dList_delete(list);
}
Result:
data 0
data 1
data 100
------------
data 100
data 1
data 0
The dList_forEachForward and dList_forEachReverse in the example are traversal methods, and their specific usages are described below. When the reference to dList passed in is NULL, a node will be created for the first time and the head of the list will be generated. Passing in a negative index means inserting at the tail. You can use the predefined dList_front and dList_back macros to represent the head and tail.
Erasing Data from a dList
int dList_erase(dList **listRef, int index, dList **outPrev);
This method corresponds to the dList_insert method. It erases the data at the specified position (it will remove the node from the linked list). At the same time, in order to make it more flexible to use, it also supports getting the previous node of the erased node (which can make it more convenient and efficient to perform continuous erasing).
static void test_erase(void)
{
dList *list = NULL;
for (int i = 0; i < 5; i++)
{
if (!dList_insert(&list, -1, &i, sizeof(i))) goto FAIL;
}
dList_erase(&list, 0, NULL);
dList_forEachForward(list, n)
{
printf("data %d\r\n", dList_ref(n, int));
}
FAIL:
dList_delete(list);
}
Result:
data 1
data 2
data 3
data 4
This is compared with the previous insertion example, erasing the head of the list.
Pushing and Popping in a dList
int dList_pushFront(dList **listRef, void *data, int size);
int dList_pushBack(dList **listRef, void *data, int size);
int dList_popFront(dList **listRef);
int dList_popBack(dList **listRef);
These are methods for inserting at the head, inserting at the tail, deleting from the head, and deleting from the tail respectively. In fact, they are encapsulations based on the dList_insert and dList_erase methods for common scenarios, making them easier to use.
static void test_pop(void)
{
dList *list = NULL;
for (int i = 0; i < 5; i++)
{
if (!dList_pushFront(&list, &i, sizeof(i))) goto FAIL;
}
for (int i = 0; i < 5; i++)
{
if (!dList_pushBack(&list, &i, sizeof(i))) goto FAIL;
}
dList_popBack(&list);
dList_popBack(&list);
dList_popFront(&list);
dList_forEachForward(list, n)
{
printf("data %d\r\n", dList_ref(n, int));
}
FAIL:
dList_delete(list);
}
Result:
data 3
data 2
data 1
data 0
data 0
data 1
data 2
Appending in a dList
int dList_append(dList *list, dList **append);
This method can concatenate two linked lists into one. The append linked list will become invalid after the concatenation is successful.
Note: The append should be the head of the list. Although it can still be concatenated successfully even if it is not the head, it still belongs to the original linked list, and some unexpected situations may occur during operations.
static void test_append(void)
{
dList *list = NULL, *ap = NULL;
for (int i = 0; i < 10; i++)
{
if (!dList_pushBack(&list, &i, sizeof(i))) goto FAIL;
if (!dList_pushBack(&ap, &i, sizeof(i))) goto FAIL;
}
if (!dList_append(list, &ap)) goto FAIL;
printPoint(ap);
dList_forEachForward(list, n)
{
printf("data %d\r\n", dList_ref(n, int));
}
FAIL:
dList_delete(list);
dList_delete(ap);
}
Result:
ap: 00000000
data 0
data 1
data 2
data 3
data 4
data 5
data 6
data 7
data 8
data 9
data 0
data 1
data 2
data 3
data 4
data 5
data 6
data 7
data 8
data 9
Attaching Nodes in a dList
dList *dList_attach(dList **listRef, int index, dList *attach);
This method can attach a node (or a linked list) to an existing linked list. You can use the index to specify the specific position to attach. This method is very flexible and directly operates on the structure of the linked list. Generally, this method is not commonly used. Instead, methods encapsulated based on this one, such as dList_insert, are usually used. This method can be combined with other methods to be flexibly encapsulated into other methods again.
static void test_attach(void)
{
dList *list = NULL, *a = NULL;
for (int i = 0; i < 5; i++)
{
if (!dList_pushBack(&list, &i, sizeof(i))) goto FAIL;
}
for (int i = 0; i < 3; i++)
{
if (!dList_pushBack(&a, &i, sizeof(i))) goto FAIL;
}
dList_attach(&list, -1, a);
dList_forEachForward(list, n)
{
printf("data %d\r\n", dList_ref(n, int));
}
FAIL:
dList_delete(list);
}
Result:
data 0
data 1
data 2
data 3
data 4
data 0
data 1
data 2
Detaching Nodes in a dList
dList *dList_detach(dList **listRef, int begin, int end, dList **outPrev);
This method is the counterpart of the dList_attach method. It can detach several nodes (a sub-linked list) from the linked list. You can use the index to specify which positions to detach and the count to specify the number of nodes. This method is very flexible and directly operates on the structure of the linked list. Generally, this method is not commonly used. Instead, methods encapsulated based on this one, such as dList_erase, are usually used. This method can be combined with other methods to be flexibly encapsulated into other methods again.
static void test_detach(void)
{
dList *list = NULL, *node = NULL;
for (int i = 0; i < 10; i++)
{
if (!dList_insert(&list, -1, &i, sizeof(i))) goto FAIL;
}
#if 1
node = dList_detach(&list, 0, 3, NULL);
if (!node)
{
printf("dList_detach fail\r\n");
}
#endif
dList_forEachForward(node, n)
{
printf("node data %d\r\n", dList_ref(n, int));
}
dList_delete(node);
dList_forEachForward(list, n)
{
printf("data %d\r\n", dList_ref(n, int));
}
FAIL:
dList_delete(list);
}
Result:
node data 0
node data 1
node data 2
node data 3
data 4
data 5
data 6
data 7
data 8
data 9
Copying a dList
dList *dList_copy(dList *list, int begin, int end);
This method will make a deep copy of a new linked list according to the specified interval of the source linked list.
static void test_copy(void)
{
dList *list = NULL, *copy = NULL;
for (int i = 0; i < 10; i++)
{
if (!dList_pushBack(&list, &i, sizeof(i))) goto FAIL;
}
copy = dList_copy(list, -5, -1);
if (!copy)
{
printf("dList_copy fail\r\n");
}
dList_forEachForward(copy, n)
{
printf("data %d\r\n", dList_ref(n, int));
}
FAIL:
dList_delete(list);
dList_delete(copy);
}
Result:
data 5
data 6
data 7
data 8
data 9
Reversing an Interval in a dList
int dList_reverse(dList *list, int begin, int end);
This method will reverse the specified interval of the source linked list.
static void test_reverse(void)
{
dList *list = NULL;
for (int i = 0; i < 10; i++)
{
if (!dList_pushBack(&list, &i, sizeof(i))) goto FAIL;
}
if (!dList_reverse(list, 1, 5))
{
printf("dList_reverse fail\r\n");
}
dList_forEachForward(list, n)
{
printf("data %d\r\n", dList_ref(n, int));
}
FAIL:
dList_delete(list);
}
Result:
data 0
data 5
data 2
data 3
data 4
data 1
data 6
data 7
data 8
data 9
Getting a Specified Node in a dList
dList *dList_to(dList *list, int index);
This method can get the node with a specified offset from the current position of the head of the list. Passing in a negative number allows you to search backward from the end.
static void test_to(void)
{
dList *list = NULL, *node;
for (int i = 0; i < 10; i++)
{
if (!dList_pushBack(&list, &i, sizeof(i))) goto FAIL;
}
node = dList_to(list, -6);
if (!node)
{
printf("dList_to fail\r\n");
goto FAIL;
}
printf("dList_to data %d\r\n", dList_ref(node, int));
dList_forEachForward(list, n)
{
printf("data %d\r\n", dList_ref(n, int));
}
FAIL:
dList_delete(list);
}
Result:
dList_to data 4
data 0
data 1
data 2
data 3
data 4
data 5
data 6
data 7
data 8
data 9
Getting the Size of a dList
int dList_size(dList *list);
This method is used to get the number of data elements in the linked list.
static void test_size(void)
{
dList *list = NULL;
for (int i = 0; i < 10; i++)
{
if (!dList_pushBack(&list, &i, sizeof(i))) goto FAIL;
}
printf("size %d\r\n", dList_size(list));
printf("size %d\r\n", dList_size(dList_to(list, 3)));
FAIL:
dList_delete(list);
}
Result:
size 10
size 7
Traversing a dList
#define dList_forEach(list, node) // Traverse from the front to the back
#define dList_forEachForward(list, node) // Traverse from the front to the back
#define dList_forEachReverse(list, node) // Traverse from the back to the front
These are methods for traversing the linked list. For specific examples, you can refer to the other usage examples above.
Referencing Node Data in a dList
#define dList_ref(node, type)
This method is similar to the reference in C++. In fact, it operates on pointers (but hides the pointer operations), making reading and writing more convenient. However, it should be noted to avoid out-of-bounds data operations. For example, if the node originally stores char-type data (only 1 byte of space is allocated), using it as int-type data will cause an out-of-bounds problem. For specific examples, you can refer to the other usage examples above.