บทที่ 3 ลิงค์ลิสต์ (Linked List)
ลิงค์ลิสต์เป็นการจัดเก็บชุดข้อมูลเชื่อมโยงต่อเนื่องกันไปตามลำดับ ซึ่งอาจอยู่ในลักษณะแบบเชิงเส้น (Linear) หรือ ไม่เป็นเส้นตรง (nonlinear) ก็ได้
ลักษณะของลิงค์ลิสต์ 1. เป็นการนำข้อมูลของแต่ละโหนดมาจัดเรียงกัน มีการเชื่อมโยงกัน
2.ในแต่ละโหนดมี 2ฟิลด์ คือส่วนของข้อมูลและแอดเดรสของโหนดถัดไป
3. ฟิลด์แอดเดรสของแต่ละโหนด เป็นตัวกำหนดลำดับ
4. มีพอยเตอร์ชี้ไปยังโหนดแรกของลิงค์ลิสต์เสมอโหนดแรกนิยมเรียก Top, First และ Head
5. ฟิลด์แอดเดรสของโหนดสุดท้ายจะต่องเป็น null
6. ลิงค์ลิตส์ที่ไม่มีโหนดอยู่ภายในเรียกว่าลิสต์ว่าง
Dynamic Linked List เป็นการใช้เนื้อที่หน่วยความจำ แบบไม่ต้องจองเนื้อที่
Static Linked List เป็นการใช้เนื้อที่หน่วยความจำ แบบอาร์เรย์แทนที่ ลิงค์ลิสต์ในหน่วยความจำ
ประเภทของลิงค์ลิสต์ ลิงค์ลิสต์เดี่ยว (Singly Linked List)
- ประกอบด้วยฟิลด์แอดเดรส 1 ฟิลด์ ชี้ไปยังโหนดถัดไป
- การดำเนินการเริ่มจากโหนดแรกไปโหนดสุดท้ายย้อนกลับไม่ได้
ลิงค์ลิสต์คู่ (Doubly Linked List)
- แต่ละโหนดมีฟิลด์แอดเดรส 2 ฟิลด์ ชี้ไปยังโหนดถัดไปและก่อนหน้า
- การดำเนินการสามารถดำเนินการไปข้างหน้าและย้อนกลับได้
การดำเนินการกับลิงค์ลิสต์ การเพิ่มโหนดให้กับลิงค์ลิสต์
1.การเพิ่มข้อมูลที่จุดเริ่มต้นของโครงสร้างโหนดที่เพิ่มจะไปอยู่ที่ตำแหน่งแรกในลิสต์
2. การเพิ่มข้อมูลต่อจากโหนดที่กำหนดโหนดที่เพิ่มสามารถแทรกอยู่ตรงส่วน ใดก็ได้ในลิสต์ตามที่กำหนด
3. การเพิ่มข้อมูลที่จุดสุดท้ายของโครงสร้าง โหนดที่เพิ่มจะไปอยู่ในตำแหน่งสุดท้ายของลิสต์
การค้นหาโหนดที่ต้องการในลิสต์
จะใช้คำสั่ง searchnode เช่น searchnode(chlist,B); หมายถึง ค้นหาข้อมูล B ในลิสต์ ชื่อ chlist
การแทรกโหนดในลิสต์
จะใช้คำสั่ง insafter เช่น insafter(num,20,25); หมายถึง เพิ่มข้อมูล 25 เข้าไปหลังโหนดที่เก็บข้อมูล 20
การลบโหนดออกจากลิสต์
จะใช้คำสั่ง delnode เช่น delnode(num,50); หมายถึง ลบข้อมูล 50 ออกจากลิสต์ ชื่อ num
การท่องลิสต์
จะใช้คำสั่ง displaynode เช่น displaynode(numlist); หมายถึง แสดงข้อมูลในลิสต์ ชื่อ numlist จะแสดงผลลัพธ์ได้หลังใช้คำสั่ง displaynode(ChL);
ลิสต์เชื่อมโยงเป็นวงกลม (Circular List) เป็นลิสต์ที่ไม่มีโหนดแรก และโหนดสุดท้าย
- สามารถเข้าถึงโหนดจากจุดใดก็ได้ในลิสต์
- ต้องมีพอยเตอร์ ชี้ที่โหนดสุดท้ายในลิสต์เพื่อบ่งบอกถึงจุดสิ้นสุด
- การดำเนินการใด ๆ ใช้คำสั่งเดียวกับลิสต์ทางเดียว แต่ขั้นตอนในการทำงานจะต่างกัน เช่น การลบโหนดใด ๆ ออกจากลิสต์ จะต้องให้พอยเตอร์ ก่อนหน้าตัวที่จะลบ ชี้ไปโหนดที่อยู่หลังตัวที่จะลบ
ตัวอย่างโปรแกรม
การเพิ่ม Node
#include <stdio.h>
#include <conio.h>
struct node
{
int data;
node *next;
};
node *first;
void addnode (int i)
{
node *n;
n=new node;
n->data=i;
if (first->next==NULL) n->next=NULL;
else
n->next=first->next;
first->next=n;
}
void main()
{
clrscr();
first=new node;
first->data=0;
first->next=NULL;
addnode(5);
addnode(9);
addnode(4);
addnode(7);
addnode(3);
node *p;
for (p=first->next;p!=NULL;p=p->next)
{
printf("data=%d\n",p->data);
}
getch();
}
ผลรัน data=3
data=7
data=4
data=9
data=5
อธิบายโปรแกรม ลักษณะการทำงานของโปรแกรม สร้าง struct เพื่อใช้เก็บข้อมูลในโหนด และพอยเตอร์ไว้ในชุดเดียวกัน สร้างฟังก์ชั่น addnode ประกาศค่าตัวแปร i มีชนิดข้อมูลเป็นตัวเลขจำนวนเต็ม ในฟังก์ชั่นจะมีการสร้างพอยเตอร์และ โหนดใหม่ คือ n โดยใช้คำสั่ง new จองหน่วยความจำให้กับโหนด และเก็บตัวเลขที่ต้องการเอาไว้ ในที่นี้จะใช้เป็นค่าตามตัวแปร i ถ้าพอยเตอร์ frist ชี้ไปที่ NULL ก็ให้พอยเตอร์ n ชี้ไปยัง NULL แสดงว่าเป็นโหนดสุดท้าย มิฉะนั้นให้พอยเตอร์ n ชี้ไปยังโหนดที่ frist มันชี้อยู่ แล้วให้โหนด n ชี้ไปหาโหนดเดียวกับที่ first ชี้ก็เพื่อไม่ให้ list ขาดช่วง แล้ว first ก็จะมาชี้ที่ตัวใหม่นี้แทน ต่อมาในฟังก์ชั่น main ทำการสร้างโหนดแรก กำหนดค่าให้กับโหนดแรก มีค่า 0 แล้วกำหนดให้พอยเตอร์ของ frist ชี้ไปที่ NULL เพื่อให้เรารู้ว่าไม่มีสมาชิกใด ๆ ใน list แล้วทำการเพิ่มโหนด 5, 9, 4, 7, 3 หลังจากนั้นสร้างพอยเตอร์ p ใช้คำสั่ง for วนลูป เช็คเงื่อนไข ให้ พอยเตอร์ p ชี้ไปยังตำแหน่งของโหนดที่ frist หรือโหนดล่าสุดที่เราเพิ่งเพิ่มเข้าไปนั่นเอง ถ้า p ยังไม่เป็นค่า NULL ก็ให้ p ชี้ไปยังตำแหน่งโหนดถัดไป เสร็จแสดงค่าในโหนด ตำแหน่งที่ p ชี้อยู่
การลบ Node
#include <stdio.h>
#include <conio.h>
struct node
{
int data;
node *next;
};
node *first;
void addnode (int i)
{
node *n;
n=new node;
n->data=i;
if (first->next==NULL) n->next=NULL;
else
n->next=first->next;
first->next=n;
}
void removefromfirst()
{
node *p;
p=first->next;
first->next=p->next;
delete p; }
void main()
{
clrscr();
first=new node;
first->data=0;
first->next=NULL;
addnode(5);
addnode(9);
addnode(4);
addnode(7);
addnode(3);
addnode(15);
addnode(19);
addnode(56);
node *p; printf("Current data\n");
for (p=first->next;p!=NULL;p=p->next)
{
printf("data=%d\n",p->data);
}
removefromfirst ();
removefromfirst ();
removefromfirst ();
removefromfirst ();
removefromfirst ();
removefromfirst ();
printf("\nCurrent data\n");
for (p=first->next;p!=NULL;p=p->next)
{
printf("data=%d\n",p->data);
}
getch();
}
ผลรัน Current Data
data=56
data=19
data=15
data=3
data=7
data=4
data=9
data=5
Current Data
data=9
data=5
อธิบายโปรแกรม ลักษณะการทำงานของโปรแกรม สร้าง struct เพื่อใช้เก็บข้อมูลในโหนด และพอยเตอร์ไว้ในชุดเดียวกัน สร้างฟังก์ชั่น addnode ประกาศค่าตัวแปร i มีชนิดข้อมูลเป็นตัวเลขจำนวนเต็ม ในฟังก์ชั่น จะมีการสร้างพอยเตอร์และ โหนดใหม่ คือโหนด n โดยใช้คำสั่ง new จองหน่วยความจำให้กับโหนด และเก็บตัวเลขที่ต้องการเอาไว้ ในที่นี้จะใช้เป็นค่าตามตัวแปร i ถ้าพอยเตอร์ frist ชี้ไปที่ NULL ก็ให้พอยเตอร์ n ชี้ไปยัง NULL แสดงว่าเป็นโหนดสุดท้าย มิฉะนั้นให้พอยเตอร์ n ชี้ไปยังโหนดที่frist มันชี้อยู่ แล้วให้โหนด n ชี้ไปหาโหนดเดียวกับที่ first ชี้ก็เพื่อไม่ให้ list ขาดช่วง แล้ว first ก็จะมาชี้ที่ตัวใหม่นี้แทน สร้างฟังก์ชั่น removefromfirst ในฟังก์ชั่นมีการสร้างพอยเตอร์ p ให้พอยเตอร์ของ frist ชี้ไปยัง โหนดที่ พอยเตอร์ p ชี้อยู่ เพื่อ ลบโหนดในตำแหน่งที่พอยเตอร์ p ชี้อยู่ ในฟังก์ชั่น main สร้างโหนดแรกและกำหนดค่าให้กับโหนดแรกมีค่า 0 แล้วกำหนดให้พอยเตอร์ของ frist ชี้ไปที่ NULL เพื่อให้เรารู้ว่าไม่มีสมาชิกใด ๆ ใน list แล้วทำการเพิ่มโหนด 5, 9, 4, 7, 3, 15, 19, 56 สร้างพอยเตอร์ p ใช้คำสั่ง for วนลูป เช็คเงื่อนไข ให้ พอยเตอร์ p ชี้ไปยังตำแหน่งของโหนดที่ frist หรือโหนดล่าสุดที่เราเพิ่งเพิ่มเข้าไปนั่นเอง ถ้า p ยังไม่เป็นค่า NULL ก็ให้ p ชี้ไปยังตำแหน่งของโหนดถัดไป เสร็จแสดงค่าในโหนด ตำแหน่งที่ p ชี้อยู่ แล้วทำการลบโหนดจากโหนดแรก 6 โหนด ใช้คำสั่ง for วนลูป เช็คเงื่อนไข ให้ พอยเตอร์ p ชี้ไปยังตำแหน่งของโหนดที่ frist ถ้า p ยังไม่เป็นค่า NULL ก็ให้ p ชี้ไปยังตำแหน่งของโหมดถัดไป เสร็จแสดงค่าในโหนด ตำแหน่งที่ p ชี้อยู่
1. การแทรกโหนดในลิสต์ว่าง (Insert into Empty List)
กรณีนี้เป็นการแทรกโหนดเพิ่มเข้าไปในลิสต์ในขณะที่ลิสต์ว่างเปล่าหรือไม่มีข้อมูล
ใดๆ อยู่นั่นหมายถึงเป็นการแทรกสมาชิกตัวแรกเข้าไป ซึ่งขณะนั้นเฮดพอยน์เตอร์จะมีค่าเป็น
null เนื่องจากเป็นลิสต์ว่าง หลังจากนั้นมีลิสต์ใหม่ที่ต้องการแทรกเพิ่มเข้ามา (pNew)
(a) Before add
(b) After add
รูป แสดงการแทรกโหนดเมื่อลิสต์ภายในว่าง
2 การแทรกโหนดที่ตำแหน่งแรก (Insert at Beginning)
เป็นการแทรกโหนดเข้าไปไว้ในตำแหน่งโหนดแรก ซึ่งทำให้โหนดที่เคยอยู่ลำดับแรก
เดิมต้องมาต่อท้ายโหนดใหม่ที่แทรกเข้าไป ขั้นตอนแรกของการแทรกข้อมูลที่โหนดแรกของลิสต์
จะต้องทราบถึงตัวชี้ของตัว Predecessor ก่อน ซึ่งหากไม่มี หรือมีค่าเป็น nullก็หมายความว่า
เป็นการแทรกโหนดแรกในลิสต์ว่างเปล่า
การแทรกโหนดที่ลำดับแรกจะมีวิธีการคือ ให้นำตัวชี้ของโหนดใหม่ชี้ไปยังโหนดแรก
ของ ลิสต์หลังจากนั้นก็ทำการกำหนดเฮดพอยน์เตอร์ชี้ไปยังโหนดใหม่ ซึ่งเราจะรู้ตำแหน่งแอด
เดรสของโหนดใหม่อยู่แล้วหลังจากที่ได้สร้างขึ้นมา
(a) Before add
(b) After add
รูป แสดงการแทรกโหนดไว้ที่ตำแหน่งแรกของลิสต์
3 การแทรกโหนดที่กึ่งกลางของลิสต์ (Insert in Middle)
การเพิ่มโหนดในส่วนกลางของลิสต์หรือการแทรกระหว่างโหนด ในขั้นตอนแรก ต้องรู้ตำ
แหน่งโหนดก่อนหน้าเสียก่อน ซึ่งก็คือตัว Predecessor (pPre) ความสำคัญของโหนด
Predecessor ก็คือจะมีลิงก์ที่ใช้เชื่อมโยงไปยังโหนดถัดไป
ในการแทรกโหนดระหว่างสองโหนด ตัวชี้หรือลิงก์ฟิลด์ของโหนดใหม่จะชี้ไปยังโหนด
Successor ในขณะที่ตัวชี้ pPre ก็จะชี้ไปยังโหนดใหม่
(a) Before add
(b) After add
รูป แสดงแทรกโหนดที่กึ่งกลางของลิสต์
4 การแทรกโหนดที่ท้ายลิสต์ (Insert at End)
เมื่อมีการเพิ่มโหนดที่ส่วนท้ายของลิสต์ เราต้องการเพียงแค่ตัวชี้ของ Predecessor
เพื่อชี้ไปยังโหนดใหม่เท่านั้น ซึ่งในที่นี้จะไม่มีโหนด Successor เนื่องจากเป็นการแทรกที่ท้าย
ลิสต์ดังนั้นลิงก์ฟิลด์ของโหนดใหม่จึงถูกกำหนดให้เป็นค่า null
อย่างไรก็ตาม ก็ยังมีตรรกะพิเศษในอีกรูปแบบหนึ่งเพื่อใช้กับอัลกอริทึมการแทรกโหนด
ที่ท้ายลิสต์ ซึ่งจัดเป็นข้อดีข้อหนึ่งของโครงสร้างลิงก์ลิสต์ โดยเราทราบอยู่แล้วว่าโหนดสุดท้ายของ
ลิสต์จะมีตัวชี้ที่เชื่อมโยงไปที่ null นั่นหมายถึงโหนดสุดท้ายที่ไม่มีโหนดตัวถัดไปแล้วนั่นเองแต่ถ้า
หากเรามีความต้องการใช้พอยน์เตอร์มากกว่าที่จะใช้ค่าคงที่ของ null เป็นตัวกำหนด
a) Before add
(b) After add
