This article is about programming C/C++ language with Arduino Nano, Arduino Uno, LGT8F328P [NANO F328P-C], ET-BASE AVR EASY32U4 or other boards and platforms that use C language to store temperature/humidity data from the DHT11 sensor (Figure 1) with a dual linked list data structure. The basics of memory reservation, access, memory deallocation can be read in the previous article (Singly Linked List).
Double Linked List Data Structure
A doubly linked list (DLL) is a dynamic data structure where the amount of data can be increased or decreased as the programmer wishes. Each set of data is stored in the form of a structure with 2 pointers for pointing to the previous data (Figure 2, ie. prev) and the next data pointer (next), making it more convenient than a single link list with a pointer to point to the next node only. When writing a program to access the previous node, it must start searching from the root node every time but for doubly linked lists it is much more convenient due to prev pointer to access the previous node.
An example of constructing a structure for a doubly linked list operation would be the following code:
struct dNode {
int info;
dNode * prev;
dNode * next;
};From the dNode structure, prev and next are initialized to NULL and info to numeric data. By creating nodes in memory, commands can be written as follows.
dNode * node = (dNode*)malloc(sizeof(dNode));
if (node) {
node->info = int value;
node->prev = NULL;
node->next = NULL;
} else {
// Insufficient memory to store node
}When finished using or wanting to deallocation the memory reservation of the node, you can write a code to deallocate the memory and set the pointer value to NULL as follows.
if (node) {
free(node);
node = NULL;
} else {
// The node is not reserved.
}From the code of deallocation memory for storage, it is found that the specified data may not be cleared because the free() statement cancels the holding but does not change the value in the memory. Therefore, for System security and protect unused data (and don’t want others to have a chance to use it) you should change the value of the data in the node to the default value as in the following example.
if (node) {
node->info = default value;
node->prev = NULL;
node->next = NULL;
free(node);
node = NULL;
} else {
// The node is not reserved.
}Therefore, secure programs will run slower than programs that do not emphasize security because they must add additional conditions to prevent errors in the future, Programmers must analyze the various potential errors that affect the design principles under CIA (Confidentially, Integrity and Availability) at the design stage.
List traversing
List traversing is to access each node of the list for information. The algorithm for traversing the list is as follows.
1. currentNode point to rootNode
2. if next of currentNode is not null
2.1 shift currentNode to the next nodeFrom the algorithm above when writing the code will be as follows.
dNode = currentNode = rootNode;
while (currentNode->next != NULL) {
currentNode = currentNode->next;
}In addition, when want to move to the previous node, it can be operated as follows.
dNode * currentNode = NULL;
currentNode = lastNode;
currentNode = currentNode->prev;Similarly, to move to the previous node but move to the next node will operate as follows.
dNode * currentNode = NULL;
currentNode = rooNode;
currentNode = currentNode->next;Adding Node
There are three ways to add data to a node: adding to the root of the list. Adding at the end of the list and adding between lists. Each method has the following steps.
Insert data to the head of the list
The algorithm for adding a new node to the rootNode is as follows.
1. create newNode
2. next of newNode point to rootNode
3. prev of rootNode point to newNode
4. rootNode point to newNodeCode
dNode * newNode = (dNode*)malloc(sizeof(dNode));
newNode->info = data;
newNode->prev = NULL;
newNode->next = rootNode;
rootNode->prev = newNode;
rootNode = newNode;Add node to the end of the list
The algorithm for adding a new node to the end of the list (lasttNode) is as follows.
1. create newNode
2. prev of newNode point to lastNode
3. next of lastNode point to newNode
4. lastNode point to newNodeCode
dNode * newNode = (dNode*)malloc(sizeof(dNode));
newNode->info = data;
newNode->next = NULL;
newNode->prev = lastNode;
lastNode->next = newNode;
lastNode = newNode;Insert node in the list
The algorithm for insert a node in front of a given node is as follows.
1. create newNode
2. currentNode point to rootNode
3. search for the node you want to insert before newNode
4. prev of newNode point to prev of currentNode
5. next of newNode point to currentNode
4. next of prev of currentNode point to newNode
5. prev of next of currentNode point to newNodeCode
dNode * newNode = (dNode*)malloc(sizeof(dNode));
dNode->info = data;
dNode * currentNode = rootNode;
while (currentNode->info != key) {
currentNode = currentNode->next; // mvoe to next
}
// found
newNode->prev = currentNode->prev;
newNode->next = currentNode;
(currentNode->prev)->next = newNode;
(currentNode->next)->prev = newNode;ขั้นตอนวิธีของการเพิ่มโหนดแทรกด้านหลังโหนดที่กำหนด เป็นดังนี้
The algorithm of inserting node after a given node is as follows.
1. create newNode
2. currentNode point to rootNode
3. search for newNode to the rear
4. prev of newNode point to currentNode
5. next of newNode point to next of currentNode
4. next of prev of currentNode point to newNode
5. prev of next of currentNode point to newNodeCode
dNode * newNode = (dNode*)malloc(sizeof(dNode));
dNode->info = data;
dNode * currentNode = rootNode;
while (currentNode->info != key) {
currentNode = currentNode->next; // move to next
}
// found
newNode->prev = currentNode;
newNode->next = currentNode->next;
(currentNode->prev)->next = newNode;
(currentNode->next)->prev = newNode;Node removing
There are 3 ways to delete a node from a double linked list: delete at the first of the list, delete at the last of the list and delete nodes between lists. Each method has principles and examples of C language code as follows.
Delete at the start of the list
The algorithm for deleting the first node is as follows.
1. change rootNode to next node
2. reallocate prev of rootNode
3. set prev of rootNode to nullCode
rootNode = rootNode->next;
free(rootNode->prev);
rootNode->prev = NULL;Delete at the last of the list
The algorithm for deleting the last node is as follows.
1. change lastNode to previous node
2. deallocate lastNode
3. set next of lastNode to nullCode
lastNode = lastNode->prev;
free(lastNode->next);
lastNode->next = NULL;Deleting nodes that are between other nodes
The algorithm of deleting the required nodes between 2 nodes is as follows.
1. currentNode point to rootNode
2. search for the key
3. next of prev of currentNode point to next of currentNode
4. prev of next of currentNode point to prev of currentNode
5. deallocate currentNodeCode
dNode * currentNode = rootNode;
while (currentNode->info != key) {
currentNode = currentNode->next;
}
(currentNode->prev)->next = currentNode->next;
(currentNode->next)->prev = currentNode->prev;
Example Code
ตัวอย่างโปรแกรมต่อไปนี้เป็นการประยุกต์ใช้ลิงค์ลิสต์คู่เป็นที่เก็บข้อมูลอุณหภูมิและความชื้นที่อา่นได้จากโมดูลเซ็นเซอร์ DHT11 ที่ต่อเข้ากับขา D2 ของ Arduino Uno ทุก 2 วินาที โดยการเพิ่มข้อมูลนั้นเป็นการเพิ่มที่ท้ายของลิสต์ และถ้ามีข้อมูล 10 ชุดจะทำการนำข้อมูลที่หัวลิสต์ออกไปก่อนทำการเพิ่มข้อมูล และตัวอย่างผลลัพธ์ของโปรแกรมดังภาพที่ 3
The following program uses a double linked list to store temperature and humidity data read from a DHT11 sensor module connected to pin D2 of the Arduino Uno every 2 seconds. The data incrementing is at the end of the list. If there are 10 sets of data, it will remove the first node before adding data and an example of the output of the program as shown in Figure 3
#include <Arduino.h>
#include <DHT.h>
DHT dht = DHT(2, DHT11);
struct dNode {
float t;
float h;
dNode * next;
dNode * prev;
};
dNode *rootNode = NULL;
dNode *lastNode = NULL;
dNode *newNode = NULL;
int countNode = 0;
void printNode( dNode *n ) {
Serial.print("[");
Serial.print(n->t);
Serial.print(",");
Serial.print(n->h);
Serial.print("][");
Serial.print((int)(n->next));
Serial.println("]");
}
void printList( dNode *r) {
int counter = 0;
dNode * currentNode = r;
while (currentNode) {
counter++;
Serial.print("Node No.");
Serial.print(counter);
Serial.print(" address = ");
Serial.print((int)currentNode);
Serial.print(" T = ");
Serial.print(currentNode->t);
Serial.print("C H = ");
Serial.print(currentNode->h);
Serial.print("% prev = ");
Serial.print((int)currentNode->prev);
Serial.print(", next = ");
Serial.println((int)currentNode->next);
currentNode = currentNode->next;
}
}
void addNode() {
if (countNode == 10) {
delete1stNode();
countNode--;
}
newNode = (dNode*)malloc(sizeof(dNode));
if (newNode) {
newNode->t = dht.readTemperature();
newNode->h = dht.readHumidity();
newNode->next = NULL;
newNode->prev = NULL;
if (rootNode == NULL) {
rootNode = newNode;
lastNode = newNode;
} else {
newNode->prev = lastNode;
lastNode->next = newNode;
lastNode = newNode;
}
countNode++;
} else {
Serial.print("Not enough memory!");
while (1) {
}
}
}
void delete1stNode() {
newNode = rootNode;
rootNode = newNode->next;
rootNode->prev = NULL;
free(newNode);
}
void setup() {
Serial.begin(9600);
dht.begin();
}
void loop() {
addNode();
Serial.println("------------------------------");
printList(rootNode);
delay(2000);
}
Conclusion
From this article, We hope that readers can understand the reasons for having a double linked list data structure as well as understanding the thinking process and programming methods to apply data structure concepts to real programs, which will hopefully be useful in the future. However, if there is a story after being used, we can share and learn together. Finally, enjoy programming.
(C) 2020-2022, By Jarute Busarathid and Danai Jedsadathitikul
Updated 2023-01-25