Linked List

แนะนำ Linked List

Linked List เป็นโครงสร้างข้อมูลเชิงเส้น ที่แต่ละส่วนประกอบของข้อมูลแต่ละตัว จะมีสองส่วนหลัก คือ

1. ส่วนเก็บข้อมูล
2. ส่วนอ้างอิง (หรือ link) ที่ชี้ไปยัง node ถัดไปในลำดับข้อมูล

ด้วยโครงสร้างนี้ ทำให้การแทรกและการลบข้อมูล ณ ตำแหน่งใดๆ สามารถทำได้อย่างมีประสิทธิภาพ เนื่องจากไม่ต้องเลื่อนข้อมูลทั้งชุดเหมือนกับการทำงานกับ Array นอกจากนี้ Linked List เป็นโครงสร้างข้อมูลแบบเปลี่ยนแปลงได้ (dynamic) ที่จะมีขนาดเพิ่มขึ้นหรือลดลงได้ระหว่างที่โปรแกรมกำลังทำงานอยู่ได้

ประเภท Linked List

1. Singly Linked List

Singly linked list คือกลุ่มของ node ที่แต่ละ node ประกอบด้วยข้อมูลและตัวชี้ไปยัง node ถัดไป โครงสร้างนี้ช่วยให้เราแทรกหรือลบข้อมูลตรงจุดไหนก็ได้ใน list โดย node แรกของ list จะเรียกว่าส่วนหัว (head) และ node สุดท้ายจะชี้ไปที่ nullptr (หรือ NULL ) เพื่อแสดงถึงจุดสิ้นสุดของ list

Singly linked list ****รองรับการทำงานอย่างการแทรก การลบ และการสำรวจข้อมูล แต่จะอนุญาตให้เราสำรวจได้ในทิศทางเดียวคือจากส่วนหัวไปยังจุดสิ้นสุดเท่านั้น

นี่คือ code ตัวอย่างของ Singly Linked List

#include <iostream>
using namespace std;

class Node {
public:
  int data;
  Node *next;

  Node(int data) {
    this->data = data;
    this->next = nullptr;
  }
};

void printList(Node *n) {
  while (n != nullptr) {
    cout << n->data << " ";
    n = n->next;
  }
}

int main() {
  Node *head = new Node(1);
  Node *second = new Node(2);
  Node *third = new Node(3);

  head->next = second;
  second->next = third;

  printList(head);

  return 0;
}

2. Doubly Linked List

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

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

นี่คือตัวอย่าง code ของ Doubly linked list

#include <iostream>
using namespace std;

class Node {
public:
  int data;
  Node *prev;
  Node *next;

  Node(int data) {
    this->data = data;
    this->prev = nullptr;
    this->next = nullptr;
  }
};

void printList(Node *node) {
  while (node != nullptr) {
    cout << node->data << " ";
    node = node->next;
  }
}

int main() {
  Node *head = new Node(1);
  Node *second = new Node(2);
  Node *third = new Node(3);

  head->next = second;
  second->prev = head;
  second->next = third;
  third->prev = second;

  printList(head);

  return 0;
}

3. Circular Linked List

Circular linked list เป็นรูปแบบหนึ่งของ linked list ที่มีการปรับเปลี่ยนให้ตัวชี้ของ node สุดท้าย แทนที่จะชี้ไปยัง nullptr กลับชี้วนกลับมายัง node แรก (ส่วนหัว) ของ list แทน ทำให้เกิดโครงสร้างแบบวงกลมขึ้นมา เราสามารถสร้างได้ทั้งแบบ singly circular linked list หรือ doubly circular linked list

ในแบบ singly circular linked list แต่ละ node จะชี้ไปยัง node ถัดไป และ node สุดท้ายจะชี้กลับไปยังส่วนหัว ส่วนในแบบ doubly circular linked list แต่ละ node จะมีตัวชี้ไปยัง node ก่อนหน้า และตัวชี้ส่วนหัวของ node ก่อนหน้าจะชี้ไปยัง node สุดท้าย ทำให้เราสำรวจข้อมูลได้ทั้งสองทิศทางได้

นี่คือ code ตัวอย่างของ Circular Linked List

#include <iostream>
using namespace std;

class Node {
public:
  int data;
  Node *next;

  Node(int data) {
    this->data = data;
    this->next = nullptr;
  }
};

void printList(Node *head) {
  Node *temp = head;

  if (head != nullptr) {
    do {
      cout << temp->data << " ";
      temp = temp->next;
    } while (temp != head);
  }
}

int main() {
  Node *head = new Node(1);
  Node *second = new Node(2);
  Node *third = new Node(3);

  head->next = second;
  second->next = third;
  third->next = head;

  printList(head);

  return 0;
}

ตัวอย่างโจทย์การใช้งาน

Linked lists in C++ are versatile data structures that are used in various scenarios where dynamic data manipulation is required. One common use case is implementing a simple Music Playlist Manager. This application benefits from the linked list's ability to dynamically add and remove songs (nodes) without reallocating or reorganizing the entire data structure, as would be necessary with arrays.

Linked lists ใน C++ เป็นโครงสร้างข้อมูลที่ปรับเปลี่ยนได้หลากหลายและใช้กันอย่างแพร่หลายในสถานการณ์ที่ต้องการจัดการข้อมูลแบบ dynamic ตัวอย่างการใช้ที่เห็นได้ทั่วไป คือการสร้างโปรแกรมจัดการ Playlist เพลงอย่างง่าย โปรแกรมแบบนี้จะได้ประโยชน์จากความสามารถของ Linked lists ที่สามารถเพิ่มหรือลบเพลง ได้โดยไม่ต้องไปจัดสรรที่เก็บข้อมูลใหม่หรือรื้อโครงสร้างข้อมูลทั้งหมดออกมาได้ (ไม่ต้องรื้อใหม่เหมือนกับเวลาเราจัดการด้วย Array)

Scenario: Music Playlist Manager

ลองนึกถึงโปรแกรมจัดการ playlist เพลงที่เราสามารถเพิ่ม ลบ และย้ายตำแหน่งเพลงได้ เราจะใช้ doubly linked list กับเคสนี้เนื่องจาก

• เราต้องสามารถเพิ่มหรือลบเพลงแต่ละเพลงออกจาก playlist ได้
• ต้องสามารถย้ายไปมาระหว่างเพลงได้ ด้วยความสามารถของตัวชี้ที่เชื่อมไปยังเพลงก่อนหน้าและเพลงถัดไปทำให้เราสามารถทำเคสนี้ได้
• เราสามารถทำให้เพลย์ลิสต์วน loop จากเพลงสุดท้ายกลับมาที่เพลงแรกได้ (และในทางกลับกัน) ซึ่งสิ่งนี้สามารถใช้รูปแบบการทำงานของ circular linked ในการจัดการเคสนี้ได้

และนี่คือ code ตัวอย่าง (เชิงไอเดีย) สำหรับ Playlist

#include <iostream>
#include <string>

class Song {
public:
  std::string title;
  Song *next;
  Song *prev;

  Song(std::string title) : title(title), next(nullptr), prev(nullptr) {}
};

class Playlist {
private:
  Song *head;
  Song *tail;

public:
  Playlist() : head(nullptr), tail(nullptr) {}

  // Add a new song to the end of the playlist
  void addSong(std::string title) {
    Song *newSong = new Song(title);
    if (!head) {
      head = newSong;
      tail = newSong;
    } else {
      tail->next = newSong;
      newSong->prev = tail;
      tail = newSong;
    }
  }

  // Remove a song from the playlist
  bool removeSong(std::string title) {
    Song *temp = head;
    while (temp != nullptr) {
      if (temp->title == title) {
        if (temp->prev)
          temp->prev->next = temp->next;
        if (temp->next)
          temp->next->prev = temp->prev;
        if (temp == head)
          head = temp->next;
        if (temp == tail)
          tail = temp->prev;
        delete temp;
        return true;
      }
      temp = temp->next;
    }
    return false; // Song not found
  }

  // Display all songs in the playlist
  void display() {
    Song *temp = head;
    while (temp != nullptr) {
      std::cout << temp->title << std::endl;
      temp = temp->next;
    }
  }
};

int main() {
  Playlist myPlaylist;
  myPlaylist.addSong("Song 1");
  myPlaylist.addSong("Song 2");
  myPlaylist.addSong("Song 3");

  std::cout << "Current Playlist:" << std::endl;
  myPlaylist.display();

  myPlaylist.removeSong("Song 2");
  std::cout << "\nPlaylist after removing a song:" << std::endl;
  myPlaylist.display();

  return 0;
}

This C++ code demonstrates a basic implementation of a playlist manager using a doubly linked list. It allows songs to be added to the playlist, removed by title, and the entire playlist to be displayed. This example leverages the flexibility and efficiency of linked lists for dynamic data manipulation, making it ideal for scenarios where the dataset's size changes frequently.

code นี้เป็นตัวอย่าง การสร้างโปรแกรมจัดการ Playlist อย่างง่ายโดยใช้ doubly linked list เราจะสามารถเพิ่มเพลงเข้าไปใน Playlist ลบเพลงออกโดยใช้ชื่อเพลง และแสดงเพลงทั้งหมดในรายการได้ ตัวอย่างนี้แสดงให้เห็นถึงความยืดหยุ่นและประสิทธิภาพของ linked list ในการจัดการข้อมูลแบบ dynamic ออกมาได้ ซึ่งเหมาะอย่างยิ่งสำหรับกรณีที่ข้อมูลมีการเปลี่ยนแปลงบ่อยๆได้

use case อื่นๆ

1. Dynamic Memory Allocation linked list มีบทบาทในการจัดการหน่วยความจำแบบ dynamic ซึ่งขนาดของพื้นที่หน่วยความจำที่ต้องการจะยังไม่สามารถระบุได้ตั้งแต่ตอน compile และอาจจะมีการเพิ่มหรือลดขนาดระหว่างที่โปรแกรมทำงานอยู่ linked list ก็สามารถทำการประกาศเป็นตัวแปรลักษณะนี้เอาไว้ก่อน เพื่อใช้ในตอน runtime ได้
2. Implementing Stacks and Queues Linked lists เปิดทางให้เราสร้างโครงสร้างข้อมูลพื้นฐานอื่นๆ อย่าง stack และ queue ได้โดยไม่ต้องเจอข้อจำกัดเรื่องขนาดที่ตายตัวเหมือนกับการใช้ array ได้
3. Graphs Representation linked list สามารถใช้กับ adjacency list ในการสร้าง Graph ได้ linked list จะทำหน้าที่เก็บรายการ vertices ที่อยู่ติดกันของแต่ละ vertex ทำให้เราสามารถสำรวจและปรับเปลี่ยน Graph ได้อย่างมีประสิทธิภาพ (เราจะกลับมาลงลึกอีกทีในหัวข้อ Graph)
4. Image Viewer Applications Linked lists จะช่วยจัดการลำดับของภาพในโปรแกรมดูรูปภาพ ทำให้ผู้ใช้สามารถเลื่อนไปมาระหว่างภาพได้ (คล้ายๆกับเคส Playlist นี่แหละ)
5. Undo Functionality in Applications คล้ายกับ function "Undo" ในโปรแกรมแต่งข้อความทั่วๆไป Linked List สามารถติดตามการกระทำหรือสถานะของผู้ใช้ในโปรแกรมต่างๆ ช่วยให้การสั่งย้อนกลับ (undo) ได้ โดยการย้อนตาม Linked List ทางเดิมกลับไปได้
6. Blockchain Implementation แต่ละ block ใน Blockchain นั้นสามารถเปรียบได้กับ node ใน linked list ที่จะมีตัวชี้ไปยัง block ที่อยู่ก่อนหน้า ทำให้สามารถรับประกันความถูกต้องของธุรกรรมต่างๆ ที่เกิดขึ้นได้ จากการที่ history ถูกเก็บเป็นข้อมูลเชื่อมต่อที่ต่อเนื่องกันไว้ได้