[TH] Doubly Linked-List

บทความนี้เป็นการเขียนโปรแกรมภาษา C/C++ กับบอร์ด กับบอร์ด Arduino Nano, Arduino Uno, LGT8F328P [NANO F328P-C] และ ET-BASE AVR EASY32U4 หรือบอร์ดอื่น ๆ และแพล็ตฟอร์มอื่น ๆ ที่ใช้ภาษา C เพื่อจัดเก็บข้อมูลอุณหภูมิ/ความชื้นจากเซ็นเซอร์ DHT11 (ดังภาพที่ 1) ด้วยโครงสร้างข้อมูลแบบลิงค์ลิสต์คู่ โดยพื้นฐานของการจองหน่วยความจำ การเข้าถึง การยกเลิกการจองหน่วยความจำสามารถอ่านได้จากบทความก่อนหน้านี้ (Singly Linked List)

โครงสร้างข้อมูลแบบลิงค์ลิสต์คู่

ลิงค์ลิสต์คู่ (doubly linked list หรือ DLL) เป็นโครงสร้างข้อมูลแบบพลวัต (dynamic) ที่สามารถเพิ่มหรือลดจำนวนข้อมูลได้ตามที่ผู้เขียนโปรแกรมต้องการ โดยข้อมูลแต่ละชุดถูกเก็บอยู่ในลักษณะของโครงสร้างแบบมีตัวชี้ 2 ตัว สำหรับทำหน้าที่ชี้ไปยังข้อมูลก่อนหน้า (ในภาพที่ 2 ใช้ชื่อว่า prev) และตัวชี้ข้อมูลถัดไป (next) ทำให้มีความสะดวกกว่าลักษณะของลิงค์ลิสต์เดี่ยวที่มีตัวชี้สำหรับชี้ไปยังโหนดถัดไปเท่านั้น และเมื่อเขียนโปรแกรมเพื่อเข้าถึงโหนดก่อนหน้าจะต้องเริ่มต้นค้นหาจากโหนดรากทุกครั้ง แต่สำหรับลิงค์ลิสต์คู่มีความสะดวกกว่านั้นมากเนื่องจากมีตัวชี้ prev สำหรับเข้าถึงโหนดก่อนหน้า

ตัวอย่างการสร้างโครงสร้างสำหรับการทำงานแบบลิงค์ลิสต์คู่จะมีโค้ดดังนี้

struct dNode {
    int info;
    dNode * prev;
    dNode * next;
};

จากโครงสร้าง dNode จะกำหนดค่าเริ่มต้นของ prev และ next เป็น NULL และ info เป็นข้อมูลตัวเลข โดยการสร้างโหนดในหน่วยความจำสามารถเขียนโค้ดคำสั่งได้ดังนี้

dNode * node = (dNode*)malloc(sizeof(dNode));
if (node) {
    node->info = ข้อมูลตัวเลขจำนวนเต็ม;
    node->prev = NULL;
    node->next = NULL;
} else {
// หน่วยความจำไม่พอสำหรับจองข้อมูลเก็บ node
}

เมื่อใช้งานเสร็จหรือต้องการยกเลิกการจองหน่วยความจำของโหนดที่สร้างขึ้นสามารถเขียนโค้ดเพื่อยกเลิกหน่วยความจำและกำหนดค่าของตัวชี้ให้เป็น NULL ได้ดังนี้

if (node) {
    free(node);
    node = NULL;
} else {
// โหนดไม่ได้ถูกจอง
}

จากโค้ดของการยกเลิกการจองหน่วยความจำสำหรับเก็บข้อมูลจะพบว่าข้อมูลที่กำหนดไว้อาจจะไม่ถูกล้างออกไปเนื่องจากการสั่ง free() เป็นการยกเลิกการถือครองแต่ไม่ได้เปลี่ยนแปลงค่าในหน่วยความจำ ดังนั้น เพื่อความปลอดภัยของระบบและปกป้องข้อมูลที่ไม่ได้ใช้ (และไม่ต้องการให้ผู้อื่นมีโอกาสใช้งาน) ผู้เขียนควรเปลี่ยนค่าของข้อมูลในโหนดให้เป็นค่าเริ่มต้นดังตัวอย่างต่อไปนี้

if (node) {
    node->info = ค่าเริ่มต้นที่ต้องการ;
    node->prev = NULL;
    node->next = NULL;
    free(node);
    node = NULL;
} else {
// โหนดไม่ได้ถูกจอง
}

ด้วยเหตุนี้จะพบว่า โปรแกรมที่มีความปลอดภัย (secure) จะมีการทำงานที่ช้ากว่าโปรแกรมที่ไม่ได้มองความปลอดภัยเพราะต้องเพิ่มเงื่อนไขหรือการทำงานเพิ่มเติมเพื่อป้องกันความผิดพลาดที่อาจจะเกิดขึ้นได้ในอนาคต ดังนั้น ถ้าระบบที่พัฒนาเน้นความปลอดภัยเป็นหลัก ผู้เขียนโปรแกรมจะต้องวิเคราะห์โอกาสความผิดพลาดที่เกิดขึ้นได้ต่าง ๆ ที่มีผลกระทบต่อหลักการออกแบบภายใต้หลัก CIA (Confidentially, Integrity และ Availability) ตั้งแต่ขั้นตอนของการออกแบบ

การท่องลิสต์

การท่องลิสต์เป็นการเข้าถึงแต่ละโหนดของลิสต์ เพื่อใช้ในการค้นหาข้อมูล โดยขั้นตอนวิธีของการท่องลิสต์เป็นดังนี้

1. ให้ currentNode ชี้ที่ rootNode
2. ถ้า next ของ currentNode ไม่ใช่ค่าว่าง
    2.1 เลื่อน currentNode ไปยังโหนดถัดไป

จากขั้นตอนวิธีด้านบนเมื่อเขียนโค้ดจะได้ดังนี้

dNode = currentNode = rootNode;
while (currentNode->next != NULL) {
    currentNode = currentNode->next;
}

นอกจากนี้เมื่อต้องการขยับไปโหนดก่อนหน้าจะสามารถสั่งงานได้ดังนี้

dNode * currentNode = NULL;
currentNode = lastNode;
currentNode = currentNode->prev;

เช่นเดียวกันกับการเลื่อนตำแหน่งไปโหนดก่อนหน้าแต่เปลี่ยนเป็นโหนดถัดไปจะสั่งงานดังนี้

dNode * currentNode = NULL;
currentNode = rooNode;
currentNode = currentNode->next;

การเพิ่มโหนด

การเพิ่มข้อมูลเข้าโหนดมีด้วยกัน 3 แบบ คือ การเพิ่มที่ส่วนหัวของลิสต์ การเพิ่มที่ท้ายลิสต์ และการเพิ่มระหว่างลิสต์ โดยแต่ละวิธีมีขั้นตอนการทำงานดังนี้

การเพิ่มที่หัวลิสต์

ขั้นตอนวิธีของการเพิ่มโหนดใหม่ที่หัวลิสต์ (rootNode) เป็นดังนี้

1. สร้างโหนดใหม่ชื่อ newNode
2. ให้ next ของ newNode ชี้ไปยัง
3. ให้ prev ของ rootNode ชี้ไปที่ newNode
4. rootNode ชี้ไปที่ newNode

โค้ดโปรแกรมเขียนได้ดังนี้

dNode * newNode = (dNode*)malloc(sizeof(dNode));
newNode->info = ข้อมูลของโหนด;
newNode->prev = NULL;
newNode->next = rootNode;
rootNode->prev = newNode;
rootNode = newNode;

การเพิ่มที่ท้ายลิสต์

ขั้นตอนวิธีของการเพิ่มโหนดใหม่ที่ท้ายลิสต์ (lasttNode) เป็นดังนี้

1. สร้างโหนดใหม่ชื่อ newNode
2. ให้ prev ของ newNode ชี้ไปที่ lastNode
3. ให้ next ของ lastNode ชี้ไปที่ newNode
4. ให้ lastNode ชี้ไปที่ newNode

โค้ดโปรแกรมเขียนได้ดังนี้

dNode * newNode = (dNode*)malloc(sizeof(dNode));
newNode->info = ค่าของข้อมูล;
newNode->next = NULL;
newNode->prev = lastNode;
lastNode->next = newNode;
lastNode = newNode;

การเพิ่มระหว่างลิสต์

ขั้นตอนวิธีของการเพิ่มโหนดแทรกด้านหน้าโหนดที่กำหนด เป็นดังนี้

1. สร้างโหนดใหม่ชื่อ newNode
2. กำหนดให้ currentNode ชี้ไปที่ rootNode
3. ค้นหาโหนดที่ต้องการแทรก newNode ไว้ด้านหน้า 
4. ให้ prev ของ newNode ชี้ไปที่ prev ของ currentNode
5. ให้ next ของ newNode ชี้ไปที่ currentNode
4. กำหนดให้ next ของ prev ของ currentNode ชี้ไปที่ newNode
5. กำหนดให้ prev ของ next ของ currentNode ชี้ไปที่ newNode

โค้ดโปรแกรมเขียนได้ดังนี้

dNode * newNode = (dNode*)malloc(sizeof(dNode));
dNode->info = ข้อมูลของโหนด;
dNode * currentNode = rootNode;
while (currentNode->info != ค่าที่ค้นหา) {
    currentNode = currentNode->next; // ขยับไปโหนดถัดไป
}
// เมื่อพบ
newNode->prev = currentNode->prev;
newNode->next = currentNode;
(currentNode->prev)->next = newNode;
(currentNode->next)->prev = newNode;

ขั้นตอนวิธีของการเพิ่มโหนดแทรกด้านหลังโหนดที่กำหนด เป็นดังนี้

1. สร้างโหนดใหม่ชื่อ newNode
2. กำหนดให้ currentNode ชี้ไปที่ rootNode
3. ค้นหาโหนดที่ต้องการแทรก newNode ไว้ด้านหลัง 
4. ให้ prev ของ newNode ชี้ไปที่ currentNode
5. ให้ next ของ newNode ชี้ไปที่ next ของ currentNode
4. กำหนดให้ next ของ prev ของ currentNode ชี้ไปที่ newNode
5. กำหนดให้ prev ของ next ของ currentNode ชี้ไปที่ newNode

โค้ดโปรแกรมเขียนได้ดังนี้

dNode * newNode = (dNode*)malloc(sizeof(dNode));
dNode->info = ข้อมูลของโหนด;
dNode * currentNode = rootNode;
while (currentNode->info != ค่าที่ค้นหา) {
    currentNode = currentNode->next; // ขยับไปโหนดถัดไป
}
// เมื่อพบ
newNode->prev = currentNode;
newNode->next = currentNode->next;
(currentNode->prev)->next = newNode;
(currentNode->next)->prev = newNode;

การลบโหนด

การลบโหนดออกจากลิงค์ลิสต์คู่มี 3 รูปแบบ คือ ลบที่หัวลิสต์ ลบที่ท้ายลิสต์ และลบโหนดระหว่างลิสต์ โดยแต่ละวิธีมีหลัการและตัวอย่างโค้ดภาษา C ดังนี้

การลบหัวลิสต์

ขั้นตอนวิธีของการลบโหนดที่อยู่หัวลิสต์เป็นดังนี้

1. ขยับ rootNode ไปยังโหนดถัดไป
2. ยกเลิกการจอง prev ของ rootNode
3. ให้ prev ของ rootNode เป็นค่าว่าง

จากขั้นตอนวิธีเขียนเป็นโค้ดตัวอย่างได้ดังนี้

rootNode = rootNode->next;
free(rootNode->prev);
rootNode->prev = NULL;

การลบท้ายลิสต์

ขั้นตอนวิธีของการลบโหนดที่อยู่ท้ายลิสต์เป็นดังนี้

1. ย้าย lastNode ไปโหนดก่อนหน้า
2. ยกเลิกการจองโหนดถัดไปของ lastNode
3. ให้ next ของ lastNode เป็นค่าว่าง

จากขั้นตอนวิธีเขียนเป็นโค้ดตัวอย่างได้ดังนี้

lastNode = lastNode->prev;
free(lastNode->next);
lastNode->next = NULL;

การลบโหนดที่อยู่ระหว่างโหนดอื่น

ขั้นตอนวิธีของการลบโหนดที่ต้องการซึ่งอยู่ระหว่าง 2 โหนดเป็นดังนี้

1. ให้ currentNode ชี้ที่ rootNode
2. ค้นหาข้อมูลที่ต้องการ
3. ให้ next ที่ prev ของ currentNode ชี้ไปที่ next ของ currentNode
4. ให้ prev ที่ next ของ currentNode ชี้ไปที่ prev ของ currentNode
5. ยกเลิกการจอง currentNode

จากขั้นตอนวิธีเขียนเป็นโค้ดตัวอย่างได้ดังนี้

dNode * currentNode = rootNode;
while (currentNode->info != ข้อมูลที่ค้นหา) {
    currentNode = currentNode->next;
}
(currentNode->prev)->next = currentNode->next;
(currentNode->next)->prev = currentNode->prev;

ตัวอย่างโปรแกรม

ตัวอย่างโปรแกรมต่อไปนี้เป็นการประยุกต์ใช้ลิงค์ลิสต์คู่เป็นที่เก็บข้อมูลอุณหภูมิและความชื้นที่อา่นได้จากโมดูลเซ็นเซอร์ DHT11 ที่ต่อเข้ากับขา D2 ของ Arduino Uno ทุก 2 วินาที โดยการเพิ่มข้อมูลนั้นเป็นการเพิ่มที่ท้ายของลิสต์ และถ้ามีข้อมูล 10 ชุดจะทำการนำข้อมูลที่หัวลิสต์ออกไปก่อนทำการเพิ่มข้อมูล และตัวอย่างผลลัพธ์ของโปรแกรมดังภาพที่ 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);
}

สรุป

จากบทความนี้ผู้เขียนหวังว่าผู้อ่านได้เข้าใจเหตุผลของการมีโครงสร้างข้อมูลแบบลิงค์ลิสตคู่ พร้อมทั้งเข้าใจกระบวนการคิดและวิธีการเขียนโปรแกรม เพื่อนำแนวคิดโครงสร้างข้อมูลไปใช้กับโปรแกรมจริงซึ่งหวังว่าจะมีประโยชน์ต่อไปในอนาคต อย่างไรก็ดีถ้ามีเรื่องเล่าหลังจากมีการนำไปใช้ก็สามารถแลกเปลี่ยนเรียนรู้ร่วมกันได้นะครับผม สุดท้ายขอให้สนุกกับการเขียนโปรแกรมครับ

(C) 2020-2022, โดย อ.ดนัย เจษฎาฐิติกุล/อ.จารุต บุศราทิจ
ปรับปรุงเมื่อ 2022-12-31