สร้าง Linked List ด้วยภาษา Java

Linked List เป็นโครงสร้างข้อมูลแบบง่ายที่สุดที่เราได้เรียนกันตอนวิชาโครงสร้างข้อมูล (Data Structure) 

วันนี้ผมจะแสดงตัวอย่างการสร้าง Linked List ด้วยภาษาจาวา

อันดับแรก ต้องเข้าใจก่อนว่า Linked List ประกอบกันขึ้นด้วย "โหนด" ย่อยๆ ที่เรียงต่อกัน คล้ายอาร์เรย์ที่เรารู้จักกันดี แต่สำหรับโหนดที่ว่า ไม่จำเป็นต้องมีเพียงชนิดข้อมูลเดียว สามารถมีหลายข้อมูลอยู่รวมกันในโหนดเดียวได้ แต่สิ่งสำคัญที่ต้องมีในโหนดนั้นคือ link มันสำคัญอย่างไร สำคัญเพราะว่า link เป็นตัวชี้ว่าโหนดถัดไปคือโหนดใดนั่นเอง หากขาด link ก็เท่ากับว่า เราไม่สามารถเชื่อมโยงโหนดใดๆ เข้าหากันได้

ไม่พูดมากเรามาเริ่มโค๊ดกันเลยดีกว่า ผมแบ่งการเขียนโค๊ดออกเป็น 2 ไฟล์นะครับ คือ Node.java และ LinkedList.java

- Node.java คือ ไฟล์ที่สร้างข้อมูลภายในโหนดใดๆ

- LinkedList.java คือ ไฟล์ที่สร้างโหนดใดๆ ขึ้นมาแล้วนำโหนดนั้นๆ มาเชื่อมต่อกัน

มาเริ่มกันที่ Node.java ผมจะกำหนดให้ข้อมูลในหนึ่งโหนดเป็นดังนี้นะครับ

ข้อมูลที่จะบรรจุในโหนดใดๆ (Attribute of class)

อธิบายรูปคือ โหนดใดๆ จะประกอบด้วยข้อมูลดังนี้ 

1. String fName คือ ชื่อ
2. String lName คือ นามสกุล
3. String id คือ รหัสประจำตัว
4. double score คือ คะแนนสอบ
5. Node link คือ ตัวชี้ว่าโหนดถัดไปคือโหนดใด

และมี Constructor Method ดังนี้

Constructor Method

อธิบายรูปคือ มี constructor method อยู่ 2 แบบซึ่งได้แก่

1. Node() เป็น constructor method ที่ไม่มีการรับพารามิเตอร์ ใช้สำหรับการกำหนดค่าเริ่มต้นให้กับข้อมูลใดๆ ในโหนดนั้นๆ
2. Node(String fName, String lName, String id, double score, Node link) เป็น constructor method ที่มีการรับพารามิเตอร์ และกำหนดให้กับข้อมูลตามลำดับ

สำหรับไฟล์ Node.java ก็มีโค๊ดสั้นๆ เพียงเท่านี้ ต่อไปเป็นรายละเอียดของไฟล์ LinkedList.java ซึ่งการทำงานของไฟล์นี้จะแบ่งออกเป็นเมธอดย่อยๆ ดังนี้

• insertNode ใช้สำหรับการเพิ่มโหนดเข้าไปใน Linked List
• printLinkedList ใช้สำหรับการแสดงค่าต่างๆ ที่อยู่ใน Linked List
• main ใช้สำหรับการรับค่า และเรียกใช้เมธอดอื่นๆ

- insertNode method เขียนโค๊ดได้ดังนี้

insertNode method

อธิบายรูปคือ insertNode method มีการรับพารามิเตอร์ทั้งหมด 5 ตัว เพื่แนำมากำหนดให้กับข้อมูลในโหนด แต่ที่สำคัญคือ Node head คือตัวกำหนดว่าต้นลิสต์อยู่ที่ใด ในการเพิ่มโหนดนี้เราใช้แบบการเพิ่มที่ท้ายลิสต์ คือการสร้างโหนดใหม่มาต่อท้ายโหนดเดิมในลิสต์ไปเรื่อยๆ และมีการรีเทิร์นค่ากลับไปเป็นชนิดข้อมูลแบบ Node คือการคืน โหนด head ที่เป็นต้นลิสต์กลับไปนั่นเอง

• Node newNode = new Node(); คือการสร้าง newNode ให้เป็น object ของ class Node จะเห็นว่า เราเรียกใช้ constructor method แบบ Node() ซึ่งยังไม่มีการกำหนดค่าจากผู้ใช้ใดๆทั้งสิ้น แต่จะเป็นการกำหนดค่าเริ่มต้นเท่านั้น จากนั้นเริ่มทำการกำหนดค่าที่จากพารามิเตอร์ให้กับข้อมูลในโหนดตามลำดับ โดยการเข้าถึงข้อมูลต่างๆในโหนดสามารถเข้าถึงได้โดยตรง เพราะการสร้าง class Node ได้กำหนดให้ attribute ใดๆ มีการเข้าถึงแบบ public ไว้ แต่ถ้าหากมีการกำหนดการเข้าถึงข้อมูลแบบ private ไว้ เราจำเป็นต้องสร้าง method getter setter ให้กับข้อมูลทุกตัวเพื่อใช้ในการเข้าถึงข้อนั้นๆ
• Node trav1, trav2; สร้างโหนด 2 โหนดเปล่าขึ้นมา เพื่อใช้ในการท่องเข้าไปในลิสต์
• trav1 = trav2 = head; กำหนดให้ทั้งสองโหนดชี้ที่ต้นลิสต์
• ใน while loop ทำการท่องเข้าไปในลิสต์ โดยให้ โหนด trav2 ท่องตาม โหนด trav1 หากในลิสต์มีข้อมูล โหนด trav2 จะหยุดที่โหนดสุดท้ายในลิสต์พอดี และจะหยุด loop ก็ต่อเมื่อ trav1 ท่องไปจนสุดลิสต์
• trav2 = trav1; กำหนดให้ โหนด trav2 ท่องตาม โหนด trav1
• trav1 = trav1.link; กำหนดให้ โหนด trav1 ท่องไปยังโหนดถัดไป
• if(trav1 != trav2) trav2.link = newNode; ถ้าหาก โหนด trav1 ไม่เท่ากับโหนด trav2 แสดงว่าในลิสต์มีโหนดใดๆ อยู่ให้ โหนด trav2 ที่ชี้อยู่โหนดสุดท้ายในลิสต์ ทำการชี้ link ไปยัง โหนด newNode ซึ่งก็คือโหนดที่เพิ่มเข้ามาใหม่
• else head = newNode; แต่ถ้าเงื่อนไข if ด้านบนไม่เป็นจริง แสดงว่าในลิสต์ยังไม่มีโหนดใดๆ เลย ก็กำหนดให้เป็นโหนดแรกของลิสต์ โดยให้ โหนด head มีค่าเท่ากับ โหนด newNode

- printLinkedList method เขียนโค๊ดได้ดังนี้

printLinkedList method

อธิบายรูปคือ printLinkedList method มีการรับพารามิเตอร์ตัวเองคือ Node head คือต้นลิสต์ เอาไว้สำหรับท่องเข้าไปยังโหนดทั้งหมดในลิสต์ แล้วแสดงค่าในโหนดต่างๆ ออกมาตามรูปแบบที่ต้องการ

• Node trav = head; สร้างโหนด trav ขึ้นมาและกำหนดค่าให้เท่ากับ head ซึ่งชี้อยู่ที่ต้นลิสต์
• ใน while loop ทำการท่องเข้าไปในลิสต์ที่ละโหนด แล้วแสดงค่าต่างๆ ออกมาตามรูปแบบต้องการ จะพบว่าการเข้าถึงข้อมูลในแต่ละโหนดนั้นสามารถเข้าถึงได้โดยตรงเช่นเดียวกับการกำหนดค่า และจะหยุด loop ก็ต่อเมื่อ trav ท่องไปจนสุดลิสต์
• trav = trav.link; กำหนดให้โหนด trav ท่องไปยังโหนดถัดไป

- main method เขียนโค๊ดได้ดังนี้

main method

อธิบายรูปคือ main method จะมีการรับค่ามาจากผู้ใช้เป็นจำนวนนักเรียนที่ต้องการใส่ข้อมูล และทำการใช้ for loop วนรับค่าเก็บไว้ที่ตัวแปรตามลำดับ และเรียกใช้ method insertNode เพื่อเพิ่มโหนดใหม่ไปยังลิสต์ และมีการเรียกใช้ method linkedList เพื่อแสดงค่าทั้งหมดในลิสต์

• Node head = null; สร้างโหนด head เพื่อเอาไว้ชี้ต้นลิสต์
• head = insertNode(head, fName, lName, id, score); เรียกใช้ insertNode method เพื่อนำข้อมูลที่รับมาจากผู้ใช้ใส่เข้าในในโหนด และเพิ่มโหนดเข้าไปในลิสต์ และ method นี้จะรีเทิร์นค่าที่เป็น Node ที่เป็นต้นลิสต์กลับมา จึงกำหนดค่าให้กับโหนด head
• printLinkedList(head); แสดงค่าแต่ละโหนดในลิสต์

ก็จะได้ Linked List อย่างง่ายไปใช้งาน แต่จริงๆแล้วยังมี method ที่สามารถทำได้อีกเช่น การเพิ่มข้อมูลเข้าไปที่ต้นลิสต์ การเพิ่มข้อมูลแบบเรียงลำดับ การลบข้อมูลที่ต้นลิสต์ การลบข้อมูลที่ท้ายลิสต์ การลบข้อมูลโดยอ้างอิงข้อมูลที่ตรงกับข้อมูลในสิลต์ การค้นหาข้อมูลในลิสต์ เป็นต้น

โค๊ดสมบูรณ์ของทั้งสองไฟล์สามารถดาวน์โหลดได้ดังนี้

Node.java

LinkedList.java