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;
  }
}