ในโครงสร้างข้อมูล รายการเชื่อมต่อ (Link List) เป็นการรวบรวมข้อมูลแบบเส้นตรง แต่ละองค์ประกอบหรือโหนดของรายการประกอบด้วยสองรายการ - ข้อมูลและการอ้างอิงไปยังโหนดถัดไป โหนดสุดท้ายมีการอ้างอิงไปยัง null เข้าสู่รายการเชื่อมต่อ จุดเข้าถึงเรียกว่า head ของรายการ
รายการเชื่อมต่อคู่ (Doubly linked list) ประกอบด้วยชุดของเรคคอร์ดที่เชื่อมต่อลำดับกันเรียกว่าโหนด แต่ละโหนดมีสามฟิลด์: ฟิลด์ข้อมูลหนึ่งและฟิลด์ลิงก์สองฟิลด์ การอ้างอิงไปยังโหนดก่อนหน้าและโหนดถัดไปในลำดับของฟิลด์โหนด
ในกรณีของรายการเชื่อมต่อคู่ที่จัดเรียงแล้ว ตามค่าของฟิลด์ข้อมูลที่จัดเรียงแล้ว รายการเชื่อมต่อจะยังคงจัดเรียงอยู่
อัลกอริทึม
Begin ฟังก์ชัน createnode() เพื่อแทรกโหนดในรายการ: สร้าง newnode และแทรกตัวเลขในฟิลด์ข้อมูลของ newnode ตรวจสอบว่ารายการว่างหรือไม่ ถ้ารายการว่าง ให้วางโหนดเป็นองค์ประกอบแรกและอัปเดต head ทั้งพอยน์เตอร์ prev และ next จะถูกเริ่มต้นด้วย NULL ถ้ารายการไม่ว่าง โหนดใหม่นี้จะถูกแทรกเข้าไปในรายการเชื่อมต่อที่มีอยู่ โดยที่รายการเชื่อมต่อจะยังคงจัดเรียงอยู่ในที่สุด พอยน์เตอร์ Prev และ next จะถูกอัปเดตตามลำดับ End Begin ฟังก์ชัน display_head() เพื่อแสดงรายการจาก head: เริ่มต้น c=0 เริ่มต้นตัวแปรพอยน์เตอร์ด้วยที่อยู่โหนด head while (c <= i ) พิมพ์ข้อมูลโหนด อัปเดตตัวแปรพอยน์เตอร์ เพิ่ม c End Begin ฟังก์ชัน dispslay_tail() เพื่อแสดงรายการจาก tail: เริ่มต้น m=0 เริ่มต้นตัวแปรพอยน์เตอร์ด้วยที่อยู่โหนด tail while (m <= i ) พิมพ์ข้อมูลโหนด อัปเดตตัวแปรพอยน์เตอร์ เพิ่ม m End
ตัวอย่างโค้ด
#include<iostream> using namespace std; struct nod { int d; nod *n, *p; } *p = NULL, *head = NULL, *r = NULL, *np = NULL, *tail = NULL; int c = 0; void createnode(int n) { np = new nod; np->d = n; np->n = NULL; np->p = NULL; if (c == 0) { tail = np; head = np; p = head; p->n = head; p->p = head; c++; } else if (c == 1) { p = head; r = p; if (np->d < p->d) { np->n = p; p->p = np; head = np; p->n = np; np->p = p; tail = p; } else if (np->d > p->d) { p->n = np; np->p = p; np->n= head; p->p = np; } c++; } else { p = head; r = p; if (np->d < p->d) { np->n = p; p->p = np; head = np; do { p = p->n; } while (p->n != r); tail = p; p->n = np; np->p = p; } else if (np->d > p->d) { while (p->n != head && np->d > p->d) { r = p; p = p->n; if (p->n == head && (p->d < np->d)) { p->n = np; np->p = p; np->n = head; tail = np; head->p = np; break; } else if (np->d< p->d) { r->n= np; np->p = r; np->n= p; p->p= np; if (p->n != head) { do { p = p->n; } while (p->n != head); } tail = p; break; } } } } } void display_head(int i) { nod *t = head; int c = 0; while (c <= i) { cout<<t->d<<"\t"; t = t->n; c++; } cout<<endl; } void display_tail(int i) { nod *t = tail; int m = 0; while (m <= i) { cout<<t->d<<"\t"; t = t->p; m++; } cout<<endl; } int main() { int i = 0, n, a, ch; cout<<"enter the no of nodes\n"; cin>>n; while (i < n) { cout<<"\nenter value of node\n"; cin>>a; createnode(a); i++; } cout<<"\nsorting Doubly Linked List head first\n"; display_head(n); cout<<"\nsorting Doubly Linked List tail first\n"; display_tail(n); }
ผลลัพธ์
enter the no of nodes 5 enter value of node 7 enter value of node 4 enter value of node 6 enter value of node 2 enter value of node 1 sorting Doubly Linked List head first 1 2 4 6 7 1 sorting Doubly Linked List tail first 7 6 4 2 1 7
