Linked Lists คืออะไร๊!!

Linked Lists คืออะไร?

• เป็นการเก็บข้อมูลแบบ Linked (ข้อมูลไม่เรียงต่อเนื่องกันใน Array แต่เชื่อมถึงกัน) ของ Node (MyNode) แต่ละอัน

• โดยจะมีตัวแปร head หรือ tail มาเก็บตัวแรก และ ตัวสุดท้าย
• ซึ่ง Node (MyNode) จะประกอบด้วยสองส่วนหลักๆ (บางครั้งสาม)
  • ข้อมูล (Data)
  • ตำแหน่งของ Linked Lists ต่อไป

การเข้าถึง / แก้ไขข้อมูล

• การนำ Data (ข้อมูล) ออกมาจาก Node (MyNode)

Student std = node.getData();

• การเอาค่าของ Node (MyNode) ถัดไป

// จะเป็นการเอา Node ต่อไปของ a
MyNode b = a.getNextNode();

• การให้ Data (ข้อมูล) ใหม่กับ Node (MyNode)

Student std = new Student();
b.setData(std);

• การเปลี่ยน Node (MyNode) ต่อไปเป็นเป็น Node (MyNode) อื่น

MyNode f = new MyNode();
b.setNextNode(f);

• กรณีพิเศษ head / tail ไว้อ้างอิงตำแหน่งต่างๆ แต่จะไม่เป็น Node!

MyNode head = a;
MyNode tail = f;

ซึ่ง head และ tail จะไม่ถือว่าเป็น Node แต่เป็นตัวแปรอ้างอิงตำแหน่งเฉยๆ

ประเภทของ Linked List

• Singly Linked List: เป็น Linked List เวอร์ชันปกติทั่วไป หรือเรียกว่าเป็น Linked List ทางเดียว โดยจะสามารถเดินจากหัวไปท้ายได้เท่านั้น
• Doubly Linked List: เป็น Linked List ที่มี 2 ทางจะสามารถ เดินได้ทั้งหน้าและหลัง
• Circular Linked List: วนๆ
  • (เพิ่มเติม) Circular Doubly Linked List

การสำรวจ / เดินทาง (Traverse)

• เดินจน temp เป็น null
  • ใน loop temp จะวนครบทุก Node
  • เหมาะกับ Code ที่ต้องการดูให้ครบทุก Node

MyNode temp = head;
while(temp != null) {
    System.out.print(temp + " ");
    temp = temp.getNextNode();
}
System.out.println("\ntemp: " + temp);
// a b c d e
// temp: null

• เดินจน temp เป็นตัวสุดท้ายของ Linked Lists
  • ใน loop จะวนไม่ครบทุกตัว จะขาดตัวสุดท้าย
  • เหมาะกับโปรแกรมที่ต้องการใช้ Node ตัวสุดท้าย
    • เช่น Insert last

MyNode temp = head;
while(temp.getNextNode() != null) {
    System.out.print(temp + " ");
    temp = temp.getNextNode();
}
System.out.println("\ntemp: " + temp);
// a b c d
// temp: e

ตัวอย่างการเขียน Code

• การสร้าง Linked Lists

Student std1 = new Student();
MyNode node1 = new MyNode(std1);

Student std2 = new Student();
MyNode node2 = new MyNode(stds);

// ต่อจากเดิม
// ตั้งให้ตัวต่อไปของ node1 เป็น node2
node1.setNextNode(node2);

System.out.println(node1.getData());
// จะได้ std1

System.out.println(node2.getData());
// จะได้ std2

System.out.println(node1.getNextNode());
// จะได้ node2

System.out.println(node1.getNextNode().getData());
// จะได้ std2

คำสั่งต่างๆ

• Insert first: คือการสร้าง Node (MyNode) ใหม่และนำไปไว้ด้านหน้าสุด

  • ขั้นตอน
    1. สร้าง Node ใหม่
    2. ให้ตัวต่อไปของ Node ใหม่เป็น Node ที่ head ชี้อยู่​ (ตัวแรก)
    3. ให้ head ชี้มาที่ Node ใหม่แทน

  // 1. สร้าง Node ใหม่
  MyNode newNode = new MyNode(e);
  // 2. ให้ตัวต่อไปของ Node ใหม่เป็น Node ที่ head ชี้อยู่​ (ตัวแรก)
  newNode.setNextNode(head);
  // 3. ให้ head ชี้มาที่ Node ใหม่แทน
  head = newNode;
  

  

• Delete first: ลบตัวแรก

  • ขั้นตอน
    1. ให้ head เป็นตัวต่อไปของตัวแรก

  // 1. ให้ head เป็นตัวต่อไปของตัวแรก
  head = head.getNextNode();
  

  

• Insert last: การสร้าง Node (MyNode) ใหม่ละอันไปไว้ด้านหลังสุด

  • ขั้นตอน
    1. สร้าง Node ใหม่
    2. ลูปจนกว่า temp จะเป็นตัวสุดท้าย
    3. ให้ตัวต่อไปของตัวสุดท้ายเป็น Node ใหม่

  // 1. สร้าง Node ใหม่
  MyNode newNode = MyNode(e);
  
  // 2. ลูปจนกว่า temp จะเป็นตัวสุดท้าย
  MyNode temp = head;
  while(tmp.getNextNode() != null) {
    tmp = tmp.getNextNode();
  }
  
  // 3. ให้ตัวต่อไปของตัวสุดท้ายเป็น Node ใหม่
  tmp.setNextNode(newNode);
  

  

  • ขั้นตอน (กรณีมี tail ให้)
    1. สร้าง Node ใหม่
    2. ให้ตัวต่อไปของ tail (ตัวสุดท้าย) เป็น Node ใหม่
    3. ให้ Node ใหม่ เป็น tail แทน

  // 1. สร้าง Node ใหม่
  MyNode newNode = MyNode(e);
  // 2. ให้ตัวต่อไปของ tail (ตัวสุดท้าย) เป็น Node ใหม่
  tail.setNextNode(newNode);
  // 3. ให้ Node ใหม่ เป็น tail แทน
  tail = newNode;