Psl/ลิงก์ลิสต์

หน้านี้เป็นส่วนหนึ่งของ problem solving lab

หน้านี้มีรายละเอียดเพิ่มเติมสำหรับการเขียนลิงก์ลิสต์ อ่านเพิ่มเติมได้ที่ วิกิพีเดีย

พื้นฐาน

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

struct ListNode {
  int value;
  ListNode* next;
};

ตัวอย่างการสร้างลิสต์แบบตรงไปตรงมา

main()
{
  ListNode* n1;
  ListNode* n2;

  n1 = new ListNode;
  n2 = new ListNode;
  n1->value = 10;
  n1->next = n2;
  n2->value = 40;
  n2->next = 0;

  print_list(n1);

  delete n1;
  delete n2;
}

ใน C++ เราใช้โอเปอร์เรเตอร์ new และ delete ในการสร้างและทำลาย object ในขั้นตอนของการสร้างจะมีการจองหน่วยความจำและกำหนดค่าเริ่มต้น เมื่อเราทำลายด้วย delete จะมีการคืนค่าหน่วยความจำ ถ้าเราเขียนในภาษา C, โดยมากเราจะใช้คำสั่ง malloc ซึ่งจะทำหน้าที่จองหน่วยความจำ และคำสั่ง free ที่คืนหน่วยความจำ

สังเกตว่าเราสามารถเขียน var->field แทน (*var).field ได้

ด้านล่างเป็นตัวอย่างฟังก์ชันที่วิ่งไปในลิสต์เพื่อพิมพ์รายการในลิสต์

void print_list(ListNode* list)
{
  while(list != 0) {
    printf("%d\n", list->value);
    list = list->next;
  }
}

โหนดฉบับปรับปรุง

ใน C++ การประกาศ struct ก็เปรียบเสมือนการประกาศคลาสที่ข้อมูลภายในเป็น public ทั้งหมด ในหลาย ๆ กรณี เราสามารถเพิ่ม constructor เพื่อเพิ่มความสะดวกในการใช้งานได้ ดังด้านล่าง

struct ListNode {
  int value;
  ListNode* next;

  ListNode(int v, ListNode* n)
  {
    value = v;
    next = n;
  }
};

เมื่อเราสั่ง

  ListNode* n = new ListNode(100,0);

ก็จะเหมือนกับการเรียก constructor ดังกล่าว

สังเกตเพิ่มเติมว่าจริง ๆ แล้วในการกำหนดค่าเริ่มต้นให้กับ value และ next นั้น ก็เป็นเหมือนการเรียก constructor ให้กับ data member ทั้งสอง ดังนั้นเราเขียนให้ชัดเจนได้เป็น

struct ListNode {
  int value;
  ListNode* next;

  ListNode(int v, ListNode* n=0)
    :value(v), next(n)
  {}
};

นอกจากนี้เรายังกำหนด default parameter ได้ด้วย ยกตัวอย่างเช่น n ในโค้ดด้านบน ถ้าเขียนแบบนี้ เราสามารถสั่ง

  ListNode* header = new ListNode(0);

ได้เลย โดยในกรณีนี้ header->next จะมีค่าเป็น 0

ลิงก์ลิสต์แบบมีหัว (header)

การเพิ่มข้อมูลเข้าไปด้านหลังโหนดใด ๆ ในลิงก์ลิสต์ทำได้โดยง่าย

สมมติว่าเรามีพอยน์เตอร์ p ที่ชี้ไปยังโหนด และต้องการเพิ่มโหนดที่เก็บค่า 100 ต่อจาก p เราทำได้ดังนี้

ListNode* new_node = new ListNode(100);
new_node->next = p->next;
p->next = new_node;

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

โค้ดทั่ว ๆ ไปจะเป็นดังนี้

// ประกาศหัวเปล่า
ListNode* header = new ListNode(0);

// แทรกข้อมูลเข้าที่หัว
ListNode* new_node = new ListNode(100);
new_node->next = header->next;
header->next = new_node;

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

ตัวอย่าง

  ListNode* header = new ListNode(0);
  for(int i=0; i<10; i++) {
    ListNode* nn = new ListNode(i*100);
    nn->next = header->next;
    header->next = nn;
  }

ลิสต์แบบสองทาง (doubly linked lists)

อ่านที่วิกิพีเดีย: [1]

การประกาศก็จะไม่ต่างจากลิงก์ลิสต์ธรรมดานัก

struct ListNode {
  int value;
  ListNode* next;
  ListNode* prev;

  ListNode(int v, ListNode* n=0, ListNode* p=0)
    :value(v), next(n), prev(p)
  {}
};

แต่ในการทำงานด้วย ก็จะต้องระวังการปรับพอยน์เตอร์ทั้ง next และ prev