[TH] Singly Linked List

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

ภาพที่ 1 บอร์ดไมโครคอนโทรลเลอร์ที่ใช้ชิพ LGT8F328P กับโมดูล DHT11

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

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

ประเภทของลองค์ลิสต์นั้นนิยมเรียกตามลักษณะของโหนด (Node) เนื่องจากโครงสร้างของโหนดประกอบด้วย 2 ส่วนหลัก คือ

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

จากส่วนของตัวชี้ ถ้า มีตัวชี้ที่ใช้สำหรับชี้ไปยังโหนดอื่นจะเรียกว่าลิงค์สิวต์เดี่ยว (Singly Linked List) ถ้ามีตัวชี้จำนวน 2 ตัวชี้สำหรับชี้ไปยังโหนดก่อนหน้าและโหนดถัดไปจะเรียกว่าลิงค์ลิสต์คู่ (Doubly Linked List) และกรณีที่มีมีกกว่านี้จะเรียกว่ามัลติลิงค์ลิสต์ (Multiple Linked List) ดังภาพที่ 3

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

ตัวแปรตัวชี้

ตัวแปรตัวชี้ หรือตัวแปรพอยน์เตอร์ (pointer) เป็นตัวแปรขนาดเท่ากับจำนวนบิตของการอ้างอิงหน่วยความจำ เนื่องจากค่าที่เก็บในตัวแปรนี้ถูกนำไปใช้อ้างอิงถึงข้อมูล ณ ตำแหน่งที่เก็บในตัวแปรนี้ ทำให้สามารถใช้ตัวแปรประเภทนี้เข้าถึงหน่วยความจำส่วนต่าง ๆ ของหน่วยความจำ ซึ่งในระบบปฏิบัติการแบบเก่าเปิดให้ผู้เขียนโปรแกรมเข้าถึงหน่วยความจำได้โดยตรงทำให้ผู้ไม่ประสงค์ดีเข้าถึงข้อมูลต่าง ๆ ได้ ทำให้ระบบปฏิบัติการสมัยใหม่จึงปกป้องการเข้าถึงหน่วยความจำที่ไม่ใช่ของตนเอง แต่อย่างไรก็ดี เมื่อเราอนุญาตให้โปรแกรมทำงานในระดับผู้ดูแลระบบทำให้โปรแกรมสามารถเข้าถึงหน่วยความจำนอกพื้นที่ของตัวเองเช่นกัน ด้วยเหตุนี้ในหลายระบบปฏิบัติการจึงเพิ่มชุดคำสั่งพิเศษให้โปรแกรมที่มีความจำเป็นที่จะเข้าถึงนี้เรียกใช้ผ่านฟังก์ชันที่เตรียมไว้ให้เพื่อให้ระบบมีความปลอดภัย

การสร้างตัวแปรตัวชี้จะต้องระบุประเภทของข้อมูลที่เก็บอยู่ภายใน เนื่องจาก การเลื่อนตำแหน่งของหน่วยความจำด้วยคำสั่ง ++, –, +=, -= มีผลต่อขนาดของข้อมูล เช่น ถ้าเป็น char จะเลื่อนครั้งละ 1 ไบต์, short จะเลื่อนครั้งละ 2 ไบต์, long จะเลื่อนครั้งละ 4 ไบต์ ส่วน int จะเลื่อนครั้งละเท่ากับขนาดของสถาปัตยกรรมของชิพที่ทำงานอยู่ เป็นต้น ดังนั้น การประกาศจึงมีรูปแบบดังนี้

ประเภทของข้อมูลที่เก็บ * ชื่อตัวแปรตัวชี้;

ตัวอย่างการประกาศตัวแปรตัวชี้ชื่อ ptrByte, ptr2Bytes และ prt4Bytes ให้เป็นตัวแปรตัวชี้สำหรับชี้ข้อมูลขนาด 1, 2 และ 4 ไบต์ เขียนโค้ดได้ดังนี้

char * ptrByte;
short * ptr2Bytes;
long * ptr4Bytes;

เนื่องจากสิ่งที่เก็บในตัวแปรเป็นค่าตำแหน่งของหน่วยความจำ ด้วยเหตุนี้ การเข้าถึงข้อมูลจึงต้องมีเครื่องหมาย * นำหน้าเพื่อให้ตัวแปลคำสั่งภาษา C/C++ เข้าใจว่าผู้เขียนโปรแกรมต้องการอ้างอิงถึงข้อมูล ดังตัวอย่างต่อไปนี้ที่คำสั่งแรกเป็นการกำหนดให้ตัวแปรตัวชี้ที่ชื่อ ptrA เก็บค่า 60 และคำสั่งที่ 2 เป็นการนำค่าที่เก็บมาบวกด้วย 5 แล้วนำไปเก็บในตัวแปร b

*ptrA = 60;
b = (*ptrA)+5;

การสร้างโครงสร้าง

ข้อมูลแบบโครงสร้างหรือ struct ในภาษา C/C++ เป็นการสร้างประเภทของข้อมูลขึ้นมาใหม่ โดยสมาชิกภายในโครงสร้างข้อมูลใหม่นี้เรียงลำดับตามการประกาศตัวแปรภายในถ้อยแถลงที่กำหนด ทำให้ยืดหยุ่นต่อการเขียนโปรแกรมหรือจัดกลุ่มข้อมูลให้ข้อมูลที่เกี่ยวข้องกันอยู่ภายในก้อนเดียวกัน และเป้นรากฐานเริ่มต้นของการพัฒนาไปสู่การสร้างความสัมพันธ์ข้อมูลในก้อนต่าง ๆ จนเป็นการสร้างโครงสร้างข้อมูลแบบสัมพันธ์ (relation database) ที่มองแต่ละโครงสร้างเป้นตาราง (table) และออกแบบความสัมพันธ์ของแอททริบิวต์ (attribute) ของแต่ละตาราง (…. และเพื่อไม่ให้ออกนอกเรื่องเกินไปเราขอตัดจบเท่านี้นะครับ)

การประกาศข้อมูลแบบโครงสร้างเป็นดังนี้

struct ชื่อโครงสร้าง {
ประเภทข้อมูล₁ ชื่อ₁;
ประเภทข้อมูล₂ ชื่อ₂;
…
ประเภทข้อมูล_n ชื่อ_n;
};

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

struct sNode{
  float t;
  float h;
  sNode * next;
};

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

struct sNode{
  float t;
  float h;
  sNode * next;
};

sNode node;

void printNode( sNode n ) {
  Serial.print("[");
  Serial.print(n.t);
  Serial.print(",");
  Serial.print(n.h); 
  Serial.print("][");
  Serial.print((int)(n.next));
  Serial.println("]");
}

void setup() {
  Serial.begin(9600);
  node.t = 29.5;
  node.h = 60.0;
  node.next = NULL;
  printNode(node);
}

void loop() {

}

โดยโปรแกรมจะรายงานผลดังนี้

[29.50,60.00][0]

การจองหน่วยความจำ

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

struct sNode{
  float t;
  float h;
  sNode * next;
};

sNode node[100];

void printNode( sNode n ) {
  Serial.print("[");
  Serial.print(n.t);
  Serial.print(",");
  Serial.print(n.h); 
  Serial.print("][");
  Serial.print((int)(n.next));
  Serial.println("]");
}

void setup() {
  Serial.begin(9600);
  node[0].t = 29.5;
  node[0].h = 60.0;
  node[0].next = NULL;
  printNode(node[0]);
}

void loop() {

}

จากตัวอย่างมองดูราบรื่นดี และถ้าเพิ่มเป็น 1000 ยังคงคอมไพล์และอัพโหลดได้โดยปกติ แต่เมื่อปรับเป็น 10000 จะเกิดปัญหากับไมโครคอนโทรลเลอร์อย่างดังภาพที่ 3 ซึ่งเกิดจาก โครงสร้างเองใช้พื้นที่ประมาณ 4+4+4 = 12 ไบต์ต่อข้อมูล 1 ชุด เมื่อต้องการ 10,000 ชุดจำต้องใช้หน่วยความจำ 120,000 ไบต์ ซึ่งอาจจะมากเกินกว่าที่ไมโครคอนโทรลเลอร์ติดตั้งมาให้ ทำให้โปรแกรมไม่สามารถทำงานได้ ดังนั้น ถ้าต้องการให้โปรแกรมทำงานได้จึงจ้องปรับแต่งจำนวนสมาชิกที่เหมาะสมกับไมโครคอนโทรลเลอร์ทุกครั้งเพื่ออัพโหลดเข้าชิพ และเมื่อเขียนโปรแกรมในส่วนอื่นกินหน่วยความจำมากขึ้นอาจส่งผลให้จำนวนสมาชิกของแถวลำดับของโครงสร้างต้องปรับลดลงและคอมไลฑ์โปรแกรมใหม่ทุกครั้ง

ภาพที่ 3 เหตุการณ์ความผิดพลาดเมื่อหน่วยความจำไม่พอสำหรับให้ตัวแปรแถวลำดับที่ต้องการใช้งาน

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

การจองหน่วยความจำในภาษา C (ภาษา C++ ใช้ได้ด้วยเช่นกัน) มีรูปแบบของคำสั่งดังนี้

ตัวแปรตัวชี้ = (ประเภทข้อมูล *)malloc( ขนาดของหน่วยความจำที่ต้องการจอง )

ตัวอย่างการสร้างตัวแปรตัวชี้และจองหน่วยความจำเขียนได้ดังนี้

sNode * node;
node = (sNode*)malloc( sizeof( sNode ));

การเข้าถึง

เมื่อจองหน่วยความจำแทนการใช้แถวลำดับแบบปกติ ทำให้วิธีการเข้าถึงหน่วยความจำแตกต่างออกไป คือ ต้องใช้เครื่องหมาย -> แทนเครื่องหมาย . คั่นระหว่างชื่อตัวแปรกับสมาชิกภายในตัวแปร นั่นหมายความว่า จะการจองหน่วยความจำในตัวอย่างก่อนหน้านี้เมื่อเพิ่มข้อมูลให้กับ h, t และ next จะเขียนใหม่เป็นดังนี้

struct sNode{
  float t;
  float h;
  sNode * next;
};

sNode *node;

void printNode( sNode *n ) {
  Serial.print("[");
  Serial.print(n->t);
  Serial.print(",");
  Serial.print(n->h); 
  Serial.print("][");
  Serial.print((int)(n->next));
  Serial.println("]");
}

void setup() {
  Serial.begin(9600);
  node = (sNode*)malloc(sizeof(sNode));
  node->t = 29.5;
  node->h = 60.0;
  node->next = NULL;
  printNode(node);
}

void loop() {

}

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

struct sNode{
  float t;
  float h;
  sNode * next;
};

sNode *node;

void printNode( sNode *n ) {
  Serial.print("[");
  Serial.print(n->t);
  Serial.print(",");
  Serial.print(n->h); 
  Serial.print("][");
  Serial.print((int)(n->next));
  Serial.println("]");
}

void setup() {
  Serial.begin(9600);
  long count = 0;
  do {
    node = (sNode*)malloc(sizeof(sNode));
    if (node) {
      count++;
      Serial.print(".");
    }
  } while (node != NULL);
  Serial.println();
  Serial.print("Number of node(s) = ");
  Serial.println(count);
}

void loop() {

}

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

ภาพที่ 4 ตัวอย่างผลลัพธ์ของการทำงาน

การยกเลิกการใช้หน่วยความจำ

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

free( ตัวแปรตัวชี้ )

ลิงค์ลิสต์เดี่ยว

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

rootNode เป็นตัวแปรตัวชี้ประเภทตามโครงสร้างข้อมูลของโหนดที่สร้างขึ้น ใช้สำหรับชี้ไปยังโหนดแรกของลิงค์ลิสต์
currentNode เป็นตัวแปรตัวชี้เช่นเดียวกับ rootNode แต่ใช้สำหรับชี้ไปยังโหนดสุดท้าย
newNode เป็นตัวแปรตัวชี้ที่ใช้สำหรับชี้ไปยังโหนดที่ถูกสร้างขึ้นมาใหม่

ในภาพที่ 5 เป็นตัวอย่างของลิงค์ลิสต์ที่มีโหนดอยู่ 3 โหนด โดยที่ rootNode ชี้ไปยังโหนดแรก และมี currentNode ชี้ไปยังโหนดสุดท้าย พร้อมทั้งจะเห็นว่าค่าตัวชี้ Next ของแต่ละโหนดจะชี้ไปยังตำแหน่งของโหนดถัดไป ยกเว้นโหนดสุดท้ายที่มีค่า Next เป็น NULL เพื่อใช้เป็นค่าอ้างอิงให้ทราบว่าไม่มีข้อมูลถัดไปและตำแหน่งนี้เป้นโหนดสุดท้าย

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

ภาพที่ 5 ตัวอย่างโครงสร้างข้อมูลลิงค์ลิสต์เดี่ยว

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

ขั้นตอนการทำงานของลิงค์ลิสต์เดี่ยวเป็นดังนี้

สร้างหน่วยความจำโดยให้ newNode เป็นผู้ชี้ (ดังภาพที่ 5)
แทรกเข้าลิงค์ลิสต์โดย rootNode ชี้ไปที่โหนดแรก และ currentNode ชี้ไปยังโหนดสุดท้าย
1. กรณีที่ newNode เป็นโหนดแรกของลิงค์ลิสต์ให้ rootNode และ currentNode ชี้ไปยัง newNode ดังภาพที่ 6
2. กรณีที่มีอยู่แล้ว ดังภาพที่ 7 ให้ currentNode->next ชี้ไปที่ newNode หลังจากนั้นให้ currentNode ชี้ไปยัง newNode ดังภาพที่ 8

ภาพที่ 6 กรณีที่ newNode เป็นโหนดแรกของลิงค์ลิสต์

ภาพที่ 7 ทำการกำหนดค่าของ currentNode->Next เป็น newNode

ภาพที่ 8 ตัวอย่างผลลัพธ์ของการให้ currentNode = newNode

ตัวอย่างโค้ดโปรแกรมเป็นดังนี้

struct sNode {
  float t;
  float h;
  sNode * next;
};

sNode *rootNode;
sNode *currentNode;
sNode *newNode;

void printNode( sNode *n ) {
  Serial.print("[");
  Serial.print(n->t);
  Serial.print(",");
  Serial.print(n->h);
  Serial.print("][");
  Serial.print((int)(n->next));
  Serial.println("]");
}

void setup() {
  rootNode = NULL;
  Serial.begin(9600);
  long count = 0;
  do {
    newNode = (sNode*)malloc(sizeof(sNode));
    if (newNode) {
      newNode->t = 0.0;
      newNode->h = 0.0;
      newNode->next = NULL;
      if (rootNode == NULL) {
        rootNode = newNode;
        currentNode = newNode;
      } else {
        currentNode->next = newNode;
        currentNode = newNode;
      }
      count++;
      Serial.print(".");
    }
  } while (newNode != NULL);

  Serial.println();
  Serial.print("Number of node(s) = ");
  Serial.println(count);

  currentNode = rootNode;
  while (currentNode) {
    Serial.print("This = ");
    Serial.print((int)currentNode);
    Serial.print("Next = ");
    Serial.println((int)currentNode->next);
    currentNode = currentNode->next;
  }
}

void loop() {

}

ตัวอย่างผลลัพธ์ของการทำงานเป็นดังภาพที่ 9 และ 10 จะพบว่ามีจำนวนโหนดได้สูงสุด 138 โหนด และเมื่อเข้าไปดูแต่ละโหนดจะพบว่าโหนดแรกมีค่า Next เป็น 514 และเป็นค่าเดียวกับ This ของข้อมูลถัดไป นั่นหมายความว่า Next ชี้ไปยังข้อมูลถัดไป และไล่เรียงกันไปเรื่อย ๆ จนก่อนโหนดสุดท้ายมีค่า This เป็น 2134 โดย Next เป็น 2146 ซึ่งชี้ไปยังโหนดสุดท้าย และที่โหนดสุดท้ายที่มีค่า This เป็น 2146 จะมีค่า Next เป็น 0 หรือ NULL เนื่องจากไม่สามารถจองหน่วยความจำเพิ่มได้แล้วด้วยเหตุผลดังที่ยกตัวอย่างไปก่อนหน้านี้

ภาพที่ 9 ตัวอย่างผลลัพธ์ของการเพิ่มโหนดส่วนที่ 1/2

ภาพที่ 10 ตัวอย่างผลลัพธ์ของการเพิ่มโหนดส่วนที่ 2/2

การลบโหนด

ขั้นตอนวิธีการลบโหนดที่ยกมาเป็นตัวอย่างมีด้วยกัน 3 แบบ คือ ลบโหนดแรกที่ rootNode ชี้อยู่ ลบโหนดสุดท้ายที่ currentNode ชี้ และลบโหนดใด ๆ (โดยยกตัวอย่างการลบโหนดที่ 2) ซึ่งมีขั้นตอนวิธีดังนี้

การลบโหนดแรก

ขั้นตอนการลบโหนดแรกที่อยู่ตามภาพที่ 11 เป็นดังนี้

newNode = rootNode เพื่อให้ newNode ชี้ไปยังโหนดแรกดังภาพที่ 12
rootNode = newNode->Next เพื่อย้าย rootNode ไปยังโหนดถัดไปดังภาพที่ 13
free(newNode) เพื่อยกเลิกการจองหน่วยความจำดังภาพที่ 14 และได้ผลลัพธ์เมื่อลบ newNode ออกไปแล้วดังภาพที่ 15

ภาพที่ 11 ตัวอย่างโครงสร้างก่อนลบโหนดแรก

ภาพที่ 12 กำหนดให้ newNode ชี้ไปยังโหนดแรก

ภาพที่ 13 ย้าย rootNode ไปที่ newNode->Next

ภาพที่ 15 ตัวอย่างผลลัพธ์หลังจากลบโหนดแรก

การลบโหนดที่ 2

การลบโหนดที่ 2 จากตัวอย่างในภาพที่ 15 มีขั้นตอนดังนี้

newNode = rootNode->Next เพื่อให้ newNode ชี้ไปยังโหนดที่อยู่ถัดจาก rootNode ซึ่งเป็นโหนดลำดับที่ 2 ดังภาพที่ 16
rootNode->Next = newNode->Next เพื่อให้ rootNode->Next ชี้ไปยังโหนดที่อยู่ถัดจากโหนดที่ 2 ดังภาพที่ 17
free(newNode) เพื่อลบโหนดที่ newNode ชี้อยู่ดังภาพที่ 18 และได้ตัวอย่างผลลัพธ์ในภาพที่ 19

ภาพที่ 17 ให้ rootNode->Next ชี้ไปที่ newNode->Next

ภาพที่ 19 ตัวอย่างผลลัพธ์หลังจากลบ newNode ไปแล้ว

การลบโหนดสุดท้าย

จากภาพที่ 19 เมื่อต้องการลบโหนดสุดท้ายมีขั้นตอนดังต่อไปนี้

newNode = rootNode เพื่อให้ newNode ชี้ไปที่โหนดแรก ดังภาพที่ 20
ย้าย newNode ไปเรื่อย ๆ ด้วยคำสั่ง newNode = newNode->Next จนกว่าค่า Next ของ newNode เท่ากับ currentNode เพื่อให้ newNode ชี้อยู่ที่โหนดก่อนโหนดสุดท้ายดังภาพที่ 21
newNode->Next = NULL เพื่อระบุว่าโหนดนี้เป็นโหนดสุดท้ายดังภาพที่ 22
free(currentNode) เพื่อลบโหนดสุดท้ายก่อนหน้านี้ออกไปดังภาพที่ 23
currentNode = newNode ย้าย currentNode มาชี้โหนดสุดท้ายอันใหม่ดังภาพที่ 24

ภาพที่ 21 เมื่อ newNode อยู่ในตำแหน่งที่ newNode->Next เท่ากับ currentNode

ภาพที่ 22 เมื่อให้ newNode->Next เป็น NULL

ภาพที่ 24 ตัวอย่างผลลัพธ์เมื่อให้ currentNode ชี้ไปโหนดสุดท้าย

ตัวอย่างการลบโหนด

ตัวอย่างโปรแกรมของการเพิ่มโหนด จำนวน 5 โหนด แล้วทำการลบโหนดแรก โหนดที่ 2 (หลังจากลบโหนดแรก) และโหนดสุดท้าย เป็นดังนี้ และผลลัพธ์ของการทำงานเป็นดังภาพที่ 25

struct sNode {
  float t;
  float h;
  sNode * next;
};

sNode *rootNode;
sNode *currentNode;
sNode *newNode;

void printNode( sNode *n ) {
  Serial.print("[");
  Serial.print(n->t);
  Serial.print(",");
  Serial.print(n->h);
  Serial.print("][");
  Serial.print((int)(n->next));
  Serial.println("]");
}

void printList( sNode *r) {
  sNode * currentNode = r;
  while (currentNode) {
    Serial.print("This = ");
    Serial.print((int)currentNode);
    Serial.print(" next = ");
    Serial.println((int)currentNode->next);
    currentNode = currentNode->next;
  }
}

void setup() {
  rootNode = NULL;
  Serial.begin(9600);
  int count = 0;

  // Add 5 nodes
  for (count = 0; count < 5; count++) {
    newNode = (sNode*)malloc(sizeof(sNode));
    if (newNode) {
      newNode->t = 0.0;
      newNode->h = 0.0;
      newNode->next = NULL;
      if (rootNode == NULL) {
        rootNode = newNode;
        currentNode = newNode;
      } else {
        currentNode->next = newNode;
        currentNode = newNode;
      }
      Serial.print(".");
    } else {
      Serial.print("Not enough memory!");
      while (1) {

      }
    }
  }
  // show all nodes
  Serial.println();
  Serial.println("The 5 nodes:");
  printList( rootNode );

  // Delete the 1st node
  newNode = rootNode;
  rootNode = newNode->next;
  free(newNode);
  Serial.println("After deleted the 1st node.");
  printList( rootNode );

  // Delete the 2nd node
  newNode = rootNode->next;
  rootNode->next = newNode->next;
  free(newNode);
  Serial.println("After deleted the 2st node.");
  printList( rootNode );

  // Delete the last node
  newNode = rootNode;
  while (newNode->next != currentNode) {
    newNode = newNode->next;
  }
  newNode->next = NULL;
  free(currentNode);
  Serial.println("After deleted the last node.");
  currentNode = newNode;
  printList( rootNode );
}

void loop() {

}

ภาพที่ 25 ตัวอย่างผลลัพธ์การลบโหนดแรก โหนดที่2และโหนดสุดท้าย

ตัวอย่างการเก็บข้อมูลอุณหภูมิและความชื้นในโครงสร้างลิงค์ลิสต์

โค้ดสำหรับทดสอบการเชื่อมต่อกับ DHT11 ที่เชื่อมต่อขา S หรือขา I/O ระหว่างไมโครคอนโทรลเลอร์กับโมดูลเซ็นเซอร์เข้ากับ D2 เป็นดังนี้

#include <DHT.h>

DHT dht = DHT(D2, DHT11);

void setup() {
  Serial.begin(9600);
  dht.begin();
}

void loop() {
  float h = dht.readHumidity();
  float tc = dht.readTemperature();
  float tf = dht.readTemperature(true);

  if (isnan(h) || isnan(tc) || isnan(tf)) {
    Serial.println("DHTsensor Failed");
    return;
  }

  float hic = dht.computeHeatIndex(tc, h, false);
  float hif = dht.computeHeatIndex(tf, h);

  Serial.println("--------------------------------");
  Serial.print("Temperature ...:");
  Serial.print(tc);
  Serial.print("C/");
  Serial.print(tf);
  Serial.println("F");
  Serial.print("Heat index ....:");
  Serial.print(hic);
  Serial.print("C/");
  Serial.print(hif);
  Serial.println("F");
  Serial.print("Humidity ......:");
  Serial.print(h);
  Serial.println("%");

  delay(1000);
}

ตัวอย่างของผลลัพธ์ที่แสดงใน Serial Monitor เป็นดังภาพที่ 26

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

#include <DHT.h>
DHT dht = DHT(D2, DHT11);

struct sNode {
  float t;
  float h;
  sNode * next;
};

sNode *rootNode;
sNode *currentNode;
sNode *newNode;
int countNode;

void printNode( sNode *n ) {
  Serial.print("[");
  Serial.print(n->t);
  Serial.print(",");
  Serial.print(n->h);
  Serial.print("][");
  Serial.print((int)(n->next));
  Serial.println("]");
}

void printList( sNode *r) {
  int counter = 0;
  sNode * 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("% next = ");
    Serial.println((int)currentNode->next);
    currentNode = currentNode->next;
  }
}

void addNode() {
  if (countNode == 10) {
    delete1stNode();
    countNode--;
  }
  newNode = (sNode*)malloc(sizeof(sNode));
  if (newNode) {
    newNode->t = dht.readTemperature();
    newNode->h = dht.readHumidity();
    newNode->next = NULL;
    if (rootNode == NULL) {
      rootNode = newNode;
      currentNode = newNode;
    } else {
      currentNode->next = newNode;
      currentNode = newNode;
    }
    countNode++;
  } else {
    Serial.print("Not enough memory!");
    while (1) {
    }
  }
}

void delete1stNode() {
  newNode = rootNode;
  rootNode = newNode->next;
  free(newNode);
}

void setup() {
  countNode = 0;
  rootNode = NULL;
  Serial.begin(9600);
  dht.begin();
}

void loop() {
  addNode();
  Serial.println("------------------------------");
  printList(rootNode);  
  delay(2000);
}

ภาพที่ 26 ตัวอย่างการทำงานของใช้ SLL เก็บข้อมูลจาก DHT11

กรณีที่ใช้กับ SAM-D21 ที่เชื่อมต่อขา IO ของ DHT11 เข้ากับขา D13 สามารถเขียนโค้ดได้ดังนี้

#include <Arduino.h>
#include <DHT.h>
DHT dht = DHT(13, DHT11); // D13

struct sNode {
  float t;
  float h;
  sNode * next;
};

sNode *rootNode;
sNode *currentNode;
sNode *newNode;
int countNode;

void printNode( sNode *n ) {
  SerialUSB.print("[");
  SerialUSB.print(n->t);
  SerialUSB.print(",");
  SerialUSB.print(n->h);
  SerialUSB.print("][");
  SerialUSB.print((int)(n->next));
  SerialUSB.println("]");
}

void printList( sNode *r) {
  int counter = 0;
  sNode * currentNode = r;
  while (currentNode) {
    counter++;
    SerialUSB.print("Node No.");
    SerialUSB.print(counter);
    SerialUSB.print(" address = ");
    SerialUSB.print((int)currentNode);
    SerialUSB.print(" T = ");
    SerialUSB.print(currentNode->t);
    SerialUSB.print("C H = ");
    SerialUSB.print(currentNode->h);
    SerialUSB.print("% next = ");
    SerialUSB.println((int)currentNode->next);
    currentNode = currentNode->next;
  }
}

void addNode() {
  if (countNode == 10) {
    delete1stNode();
    countNode--;
  }
  newNode = (sNode*)malloc(sizeof(sNode));
  if (newNode) {
    newNode->t = dht.readTemperature();
    newNode->h = dht.readHumidity();
    newNode->next = NULL;
    if (rootNode == NULL) {
      rootNode = newNode;
      currentNode = newNode;
    } else {
      currentNode->next = newNode;
      currentNode = newNode;
    }
    countNode++;
  } else {
    SerialUSB.print("Not enough memory!");
    while (1) {
    }
  }
}

void delete1stNode() {
  newNode = rootNode;
  rootNode = newNode->next;
  free(newNode);
}

void setup() {
  countNode = 0;
  rootNode = NULL;
  SerialUSB.begin(9600);
  dht.begin();
}

void loop() {
  addNode();
  SerialUSB.println("------------------------------");
  printList(rootNode);  
  delay(2000);
}

สรุป

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

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