Data Structure & Algorithm(EP.7) — ลิงค์ลิสต์ (Linked-List)

Linked-List เป็นโครงสร้างข้อมูลขั้นพื้นฐานในการเก็บข้อมูล โดยมีโครงสร้างแบบเชิงเส้นสามารถเพิ่ม-ลดขนาดการเก็บข้อมูลได้ตามความต้องการ

โดยการเก็บข้อมูลนั้นจะเก็บลงในโหนด (Node) และนำข้อมูลแต่ละโหนดมาเรียงต่อกันเป็นลิสต์โดยใช้ ลิงค์ (Link) หรือ พอยเตอร์ (Pointer) เป็นตัวเชื่อมโยงแต่ละโหนดเข้าด้วยกัน

ลิงค์ลิสต์แบบทิศทางเดียว (Singly Linked-List) จะทำงานในทิศทางเดียวโดยมีจุดเริ่มต้นที่โหนดหัว (Head) ไปยังโหนดสุดท้าย (Tail) โดยไม่สามารถทำงานแบบย้อนกลับได้

สร้างลิงค์ลิสต์ (Linked-List)

class Node {
    constructor(value){
        this.value = value;
        this.next = null;
    }
}
class LinkedList {
    constructor(value) {
        const newNode = new Node(value);
        this.head = newNode;
        this.tail = this.head;
        this.length = 1;
    }
}
let myLinkedList = new LinkedList(1);
console.log(myLinkedList)

จัดการลิงค์ลิสต์ (Linked-List)

• push(value) — เพิ่มข้อมูลเข้าไปที่ลำดับสุดท้ายของลิงค์ลิสต์

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}
class LinkedList {
  constructor(value) {
    const newNode = new Node(value);
    this.head = newNode;
    this.tail = this.head;
    this.length = 1;
  }
  push(value) {
    const newNode = new Node(value);
    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      this.tail.next = newNode;
      this.tail = newNode;
    }
    this.length++;
    return this;
  }
}
let myLinkedList = new LinkedList(1);
myLinkedList.push(2);
console.log(myLinkedList);

• pop() — ดึงข้อมูลลำดับสุดท้ายออกจากลิงค์ลิสต์

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}
class LinkedList {
  constructor(value) {
    const newNode = new Node(value);
    this.head = newNode;
    this.tail = this.head;
    this.length = 1;
  }
  push(value) {
    const newNode = new Node(value);
    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      this.tail.next = newNode;
      this.tail = newNode;
    }
    this.length++;
    return this;
  }
  pop() {
    if (this.length === 0) return undefined;
    // if (!this.head) return undefined;
    let temp = this.head;
    let pre = this.head;
    while (temp.next) {
      pre = temp;
      temp = temp.next;
    }
    this.tail = pre;
    this.tail.next = null;
    this.length--;
    if (this.length === 0) {
      this.head = null;
      this.tail = null;
    }
    return temp;
  }
  showList() {
    let temp = this.head;
    while (temp !== null) {
      console.log(temp.value);
      temp = temp.next;
    }
  }
}
let myLinkedList = new LinkedList(1);
myLinkedList.push(2);
myLinkedList.push(3);
myLinkedList.pop();
myLinkedList.showList();

• unshift(value) — เพิ่มข้อมูลเข้าไปที่ลำดับแรกของลิงค์ลิสต์

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}
class LinkedList {
  constructor(value) {
    const newNode = new Node(value);
    this.head = newNode;
    this.tail = this.head;
    this.length = 1;
  }
  showList() {
    let temp = this.head;
    while (temp !== null) {
      console.log(temp.value);
      temp = temp.next;
    }
  }
  push(value) {
    const newNode = new Node(value);
    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      this.tail.next = newNode;
      this.tail = newNode;
    }
    this.length++;
    return this;
  }
  pop() {
    if (this.length === 0) return undefined;
    // if (!this.head) return undefined;
    let temp = this.head;
    let pre = this.head;
    while (temp.next) {
      pre = temp;
      temp = temp.next;
    }
    this.tail = pre;
    this.tail.next = null;
    this.length--;
    if (this.length === 0) {
      this.head = null;
      this.tail = null;
    }
    return temp;
  }
  unshift(value) {
    const newNode = new Node(value);
    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      newNode.next = this.head;
      this.head = newNode;
    }
    this.length++;
    return this;
  }
}
let myLinkedList = new LinkedList(1);
myLinkedList.push(2);
myLinkedList.unshift(4)
console.log(myLinkedList);

• shift() — ดึงข้อมูลลำดับแรกออกจากลิงค์ลิสต์

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}
class LinkedList {
  constructor(value) {
    const newNode = new Node(value);
    this.head = newNode;
    this.tail = this.head;
    this.length = 1;
  }
  showList() {
    let temp = this.head;
    while (temp !== null) {
      console.log(temp.value);
      temp = temp.next;
    }
  }
  push(value) {
    const newNode = new Node(value);
    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      this.tail.next = newNode;
      this.tail = newNode;
    }
    this.length++;
    return this;
  }
  pop() {
    if (this.length === 0) return undefined;
    // if (!this.head) return undefined;
    let temp = this.head;
    let pre = this.head;
    while (temp.next) {
      pre = temp;
      temp = temp.next;
    }
    this.tail = pre;
    this.tail.next = null;
    this.length--;
    if (this.length === 0) {
      this.head = null;
      this.tail = null;
    }
    return temp;
  }
  unshift(value) {
    const newNode = new Node(value);
    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      newNode.next = this.head;
      this.head = newNode;
    }
    this.length++;
    return this;
  }
  shift() {
    if (this.length === 0) return undefined;
    // if (!this.head) return undefined;
    let temp = this.head;
    this.head = this.head.next;
    this.length--;
    if (this.length === 0) {
      this.tail = null;
    }
    temp.next = null;
    return temp;
  }
}
let myLinkedList = new LinkedList(1);
myLinkedList.push(2);
myLinkedList.push(3);
myLinkedList.shift();
// myLinkedList.shift()
// myLinkedList.shift()
console.log(myLinkedList);

บทความที่เกี่ยวข้อง

• EP.1 — รู้จักกับโครงสร้างข้อมูลและอัลกอริทึม
• EP.2 — การวัดประสิทธิภาพอัลกอริทึม
• EP.3 — อัตราการเติบโตของฟังก์ชั่น
• EP.4 — การวิเคราะห์อัลกอริทึม
• EP.5 — Big-O Notation
• EP.6 — การคำนวณ Big-O
• EP.7 — ลิงค์ลิสต์ (Linked-List)
• EP.8 — สแต็ก (Stack)
• EP.9 — คิว(Queue)
• EP.10 — ทรี (Tree)
• EP.11 — Binary Search Tree (BST)
• EP.12 — กราฟ(Graphs)

เนื้อหาที่เกี่ยวข้อง

ช่องทางการสนับสนุน
🎓 คอร์สพัฒนาเว็บด้วย JavaScript 40 Workshop

🌎 ติดตามข่าวสารเพิ่มเติมได้ที่
Facebook | YouTube | TikTok