Linked List

Author: Black Cat & Neighborhood's Cat

---

Linked list คือ ระบบการจัดเก็บข้อมูลรูปแบบหนึ่ง ที่นำข้อมูลมาเรียงต่อกันไปเป็น list ได้อย่างไม่สิ้นสุด ซึ่งจะประกอบด้วย node ที่เป็น struct หลาย ๆ node มาเชื่อมเข้าด้วยกันด้วย pointer ที่อยู่ใน struct แต่ละตัวอีกทีเป็นห่วงโซ่ต่อเนื่องกัน

Pointer of Struct

จากบทของ struct เราได้เรียนรู้การเข้าถึงค่าของตัวแปรย่อยภายใน struct แล้ว โดยการใช้คำสั่งในรูปแบบของ variable_name.var_i

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

และในกรณีที่เราต้องการเข้าถึงค่าย่อยของ struct ที่ถูก pointer ชี้อยู่นั้น เราสามารถเข้าถึงได้โดยนำคำสั่งสองรูปแบบนี้มารวมกัน เป็น (*pointer).var_i ได้ หรือ สามารถเขียนในรูปแบบ pointer -> var_i ได้เช่นกัน โดยทั้งสองคำสั่งนี้ให้ผลลัพธ์ที่เหมือนกันอยู่ที่ความถนัดและความเคยชินของผู้ที่เขียนโค้ด

การสร้าง Linked List

มีขั้นตอนดังนี้

1. สร้าง node ที่จะนำมาต่อกันเป็น list

   โดย เราจะสามารถสร้าง struct ที่บรรจุตัวแปรกี่ตัวก็ได้ กี่ประเภทก็ได้ ตามที่เราต้องการจะนำไปใช้งาน แต่ต้องมีตัวแปร pointer ที่จะชี้ไปที่ตัวแปรประเภท struct นั้นด้วย

   ตัวอย่าง 1

   struct node{
       int data;
       struct node *next;
   };
   

   ตัวอย่าง 2

   struct node{
       int weight,cost;
       char name[100];
       struct node *next;
   };
   

2. สร้าง head หรือส่วนหัวของ list

   ในขั้นตอนนี้ เราจะกำหนด pointer ของ node ขึ้นมา 1 ตัว เพื่อจองพื้นที่ให้กับ head ของ list โดย เราจะใช้คำสั่ง new <datatype> เพื่อทำการสร้างพื้นที่เก็บข้อมูล ณ ตำแหน่งที่ pointer ชี้อยู่ เทียบเท่ากับการประกาศตัวแปร แต่การประกาศตัวแปรเราสามารถทำได้อย่างจำกัด และต้องตั้งชื่อให้กับมัน แต่การใช้คำสั่ง new เราสามารถ loop เพื่อสร้างพื้นที่เก็บข้อมูลใหม่นี้ได้เรื่อย ๆ อย่างไม่จำกัด

   และ กำหนดให้ pointer ใน node ที่สร้างขึ้นมานั้นชี้ไปที่ NULL เพื่อเป็นตัวบ่งบอกถึง tail หรือส่วนท้ายของ list

   ตัวอย่าง

   struct node *head;
   head = new node; 
   head->next = NULL;
   

3. ใส่ข้อมูลเข้าไปใน list

   ทำโดยการสร้าง pointer ของ node ขึ้นมาอีก 1 ตัว เพื่อสร้าง node ขึ้นมา และทำการกำหนดค่าของข้อมูลภายใน node ก่อนจะเอาไปต่อเข้าใน list

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

   ตัวอย่าง

   struct node *link, *temp;
   
   link = head; //ให้ link ชี้ตำแหน่งเดียวกับ head
   
   while (link->next != NULL) link=link->next; //loop เพื่อหา tail ของ list เพื่อเป็นตำแหน่งที่เราจะนำ node ใหม่มาต่อ
   
   temp = new node; //จองพื้นที่สำหรับ node ใหม่
   
   temp->data = data; //กำหนดค่าให้กับตัวแปรใน node (อ้างอิง ตัวอย่าง 1 ของการประกาศ struct node)
   
   temp->next = link->next; //กำหนดให้ pointer ของ node ใหม่ ชี้ไปที่ที่เดียวกันกับ pointer ของ tail node ของ list (ในที่นี้ก็คือ NULL)
   
   link->next = temp; //ให้ tail เดิม ชี้มาที่ node ใหม่ที่เราสร้างขึ้น และ node ใหม่นี้ก็จะกลายเป็น tail ใหม่
   

การดำเนินการอื่น ๆ กับ linked list

• การแทรกค่า

  หลักการเหมือนกันกับการเพิ่ม node ใหม่เข้าใน linked list ตามที่ได้กล่าวมาแล้ว เพียงแต่ จุดที่เราจะใส่ข้อมูลใหม่ในคำสั่งนี้ จะไม่ใช่ส่วน tail แต่เป็นการแทรกข้อมูลเข้าไปตรงกลางของ list และตอนที่ loop จะไม่ได้เป็นการหา tail แต่เป็นการหาค่าที่ตรงกับเงื่อนไขที่เราต้องการไปแทรก หรือเป็นการนับจำนวนตำแหน่งจาก head แทน

  ตัวอย่าง 1

  struct node *link, *temp;
  
  link = head;
  
  while (link->next!=NULL && link->data != a) link=link->next; //loop เพื่อหา node ที่มีข้อมูลตรงกับเงื่อนไข ถ้าไม่เจอ จะหยุดหาที่ tail node และเพิ่มข้อมูลลงที่ tail
  
  temp = new node;
  temp->data = data;
  temp->next = link->next; //ชุดคำสั่งเป็นเหมือนเดิม แต่ถ้าลองไล่ค่าดูจะเห็นว่า temp->next ไม่ได้ชี้ไปที่ null แล้ว แต่จะชี้ไปที่ตัวถัดไปที่ link->next กำลังชี้ไปอยู่จริง ๆ และทำให้ node ถัดไปนี้เองถูกชี้จาก 2 node
  link->next = temp; //ตัดการเชื่อมต่อจาก node ถัดไปเดิม มาเชื่อมกับ node ใหม่ที่แทรกเข้าไปแทน
  

  ตัวอย่าง 2

  struct node *link, *temp;
  
  link = head;
  
  for(int i=0; link->next!=NULL && i<n; i++) link=link->next; //loop เพื่อหา node ที่อยู่ที่ตำแหน่ง n นับจาก head
  
  temp = new node;
  temp->data = data;
  temp->next = link->next;
  link->next = temp;
  

• การลบค่า

  การลบค่าจะทำได้โดยการทำให้ค่าก่อนหน้าค่าที่ต้องการจะลบ ชี้ไปที่ค่าถัดจากค่าที่ต้องการจะลบ (หรือ NULL ในกรณีที่ลบ tail node) และใช้คำสั่ง delete ในการคืนพื้นที่เก็บข้อมูลที่เราได้สร้างไว้ด้วยคำสั่ง new

  ตัวอย่าง

  while ( (link->next!=NULL) && (data!=link->next->data) ) link=link->next; // จะเห็นว่าในเงื่อนไขที่เรา scan หาค่าที่ต้องการลบ เราไม่ได้ตรวจสอบ link->data เหมือนการแทรกค่า แต่เราตรวจสอบ link->next->data หรือข้อมูลของตัวถัดไปของตัวที่ link ชี้อยู่ เนื่องจากโครงสร้าง node ตามตัวอย่างนั้นเป็น linked list ทางเดียว ทำให้เราไม่สามารถ access ข้อมูลย้อนกลับไปทางหัวได้ เราจึงต้องตรวจสอบไปข้างหน้า 1 ตำแหน่งเพื่อให้ *link อยู่ในตำแหน่งก่อนหน้าตำแหน่งที่ต้องการจะลบ
  
  if (data==link->next->data) //ตรวจสอบอีกครั้ง เพื่อป้องกันกรณีค้นหาไม่เจอค่าที่ต้องการลบ จะได้ไม่ลบค่าอื่น ๆ ที่ไม่ได้ต้องการ
  {
      temp = link->next; //ให้ตัวแปร temp ชี้ค่าที่เราต้องการลบ
  
      link->next = temp->next; //ให้ pointer ของ node ที่ link ชี้ ชี้ข้าม node ที่ temp ชี้ ไปหาตัวถัดไป (หรือ NULL ในกรณีที่เป็น tail node)
  
      delete temp; //คืนพื้นที่เก็บข้อมูลที่ temp ชี้อยู่
  }
  

คำแนะนำ

• ตัวอย่างในบทนี้ทั้งหมด เป็น linked list แบบทางเดียว คือ pointer ทั้งหมดใน list ชี้เชื่อมต่อไปในทิศทางเดียวกัน คือ จาก head ไป tail แต่เราสามารถสร้างให้เป็น 2-way linked list หรือ linked list สองทางได้ด้วย โดยการเพิ่ม pointer อีกตัวเข้าไปใน node โดยกำหนดให้มันชี้ในทิศของ tail ไป head และในทุกการดำเนินการเราต้องกำหนดค่า pointer ในทิศทางนี้ให้คงความต่อเนื่องของ list ไว้ด้วย
• เช่นเดียวกัน เราสามารถสร้าง linked list ที่เชื่อมต่อกันเป็นวงกลมได้ด้วย

หมายเหตุ

• เนื่องจากในตัวอย่าง และ linked list ส่วนมาก จะเป็น linked list ทางเดียว (เนื่องจากการเขียน 2-way linked list นั้นทั้งเพิ่มขั้นตอนและเปลือง memory) ทำให้ head ของ list สำคัญมาก ๆ ในการเข้าถึง node ต่าง ๆ ใน list จึงไม่ควรแก้ไขข้อมูลใน head node หรือย้ายตำแหน่งของ *head โดยไม่มีเหตุจำเป็นที่สมควร