โครงสร้างข้อมูลลิงค์ลิสต์

โครงสร้างข้อมูลแบบลิงค์ลิสต์ ถูกนำมาใช้แก้ปัญหาโครงสร้างข้อมูลแบบอาร์เรย์ ซึ่งมีข้อจำกัด ดังนี้

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

โดยทั่วไปลิงค์ลิสต์จะประกอบด้วยสมาชิกที่ถูกเรียกว่าโหนด (node) ที่อยู่กันอย่างเป็นลำดับ โดยแต่ละโหนดจะประกอบไปด้วย 2 ส่วนคือ ส่วนที่ 1 จะเป็นสารสนเทศของโหนด (Info) ส่วนที่ 2 จะเป็นข้อมูลของโหนดถัดไป หรือโหนดที่มาตามหลัง (Link)
เราสามารถจำแนกลิงค์ลิสต์ได้ตามลักษณะของโหนดและลิงค์ ได้ดังนี้

ลิงค์ลิสต์เดี่ยว (singly linked list)

เป็นลิงค์ลิสต์ที่แต่ละโหนดมีเพียง 1 link และแต่ละโหนดจะประกอบไปด้วย 2 ส่วนคือส่วนที่เป็นข้อมูล (Info) และส่วนที่ใช้ชี้ไปยังโหนดถัดไป (Link) สำหรับโหนดสุดท้ายของลิงค์ลิสต์จะมีโหนดถัดไปเป็นค่าว่าง (Null)

ตัวอย่าง การใช้งาน Linked List ของจาวา

package linkedlist;

import java.util.LinkedList;

public class LinkListExample {

	public static void main(String[] args) {

		 LinkedList<String> linkedlist = new LinkedList<String>();

		 linkedlist.add("A");
		 linkedlist.add("B");
		 linkedlist.add("C");
		 linkedlist.add("D");
		 linkedlist.add("E");

	     System.out.println("Linked List Content: " +linkedlist);
	}

}

ผลลัพธ์

Linked List Content: [A, B, C, D, E]

การท่องไปในลิงค์ลิสต์

การท่องไปในลิงค์ลิสต์ จะเริ่มต้นค้นหาจากโหนดแรก ไปจนถึงโหนดที่ต้องการ

ตัวอย่าง การค้นหาข้อมูล E จากในลิงค์ลิสต์ก่อนหน้า

public static void main(String[] args) {

		 LinkedList<String> linkedlist = new LinkedList<String>();

		 linkedlist.add("A");
		 linkedlist.add("B");
		 linkedlist.add("C");
		 linkedlist.add("D");
		 linkedlist.add("E");

	     for(int i=0; i < linkedlist.size(); i++){
	    	 if(linkedlist.get(i).equals("E")){
	    		 System.out.println("Found E at "+i);
	    		 break;
	    	 } else {
	    		 System.out.println("Not found");
	    	 }
	     }
	}

ผลลัพธ์

Found E at 4

การแทรกข้อมูลและการลบข้อมูล

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

ตัวอย่าง การแทรกข้อมูล จากลิงค์ลิสต์ข้างบน ก่อนค่า C

public static void main(String[] args) {

		 LinkedList<String> linkedlist = new LinkedList<String>();

		 linkedlist.add("A");
		 linkedlist.add("B");
		 linkedlist.add("C");
		 linkedlist.add("D");
		 linkedlist.add("E");

	     for(int i=0; i < linkedlist.size(); i++){
	    	 if(linkedlist.get(i).equals("C")){
	    		 linkedlist.add(i, "F");
	    		 break;
	    	 }
	     }
	     System.out.println("Linked List Content: "+linkedlist);
	}

ผลลัพธ์

Linked List Content: [A, B, F, C, D, E]

ลิงค์ลิสต์พร้อมใช้งาน

ในทางความคิดโหนดทั้งหมด จะเก็บอยู่ ในรายการอิสระ ซึ่งเราเรียกว่า ลิงค์ลิสต์พร้อมใช้งาน (availability list ) หรือ หน่วยเก็บรวม (storage pool ) เมื่อต้องการนำโหนดมาแทรกในลิงค์ลิสต์ ก็จะมีพอยเตอร์ 1 ตัวในการที่จะชี้ไปยังสมาชิกตัวแรกของลิสต์พร้อมใช้งาน แล้วนำโหนดอิสระมาจากลิงค์ลิสต์พร้อมใช้งาน และเชื่อมกับ ลิสต์ในตำแหน่งที่ต้องการ ในขณะเดียวกันถ้ามีการลบโหนดออกจากลิสต์ เราก็จะต้องมีการคืนโหนดไปยังลิสต์พร้อมใช้งาน เพื่อให้สามารถจะนำมาใช้ได้ในภายหลัง

ลิงค์ลิสต์วงกลม

ลิงค์ลิสต์ชนิดนี้ เกิดจากการปรับปรุงค่าลิงค์ลิสต์ เพื่อให้ได้การประมวลผลที่ดีขึ้น โดยการแทนค่าลิงค์ที่เป็น NULL ของโหนดสุดท้ายของลิงค์ลิสต์ด้วยตำแหน่ง ที่อยู่ของโหนดแรก ลิงค์ลิสต์ในลักษณะนี้เราเรียกว่า ลิงค์ลิสต์วงกลม (circular linking linear list ) หรือ ลิสต์วงกลม ( circular list)

ลิงค์ลิสต์คู่

ในลิงค์ลิสต์ประเภทนี้จะมีโหนดซึ่งประกอบด้วยลิงค์ลิสต์ 2 ส่วน เพื่อแสดงโหนดที่มาก่อน และโหนดที่มาทีหลัง โหนดที่มาก่อนเราเรียกว่า ลิงค์ซ้าย (left link) ซึ่งแทนด้วยพอยเตอร์ LLINK และลิงค์ที่แทนโหนดที่มาหลังเรา เรียกว่า ลิงค์ขวา(rigth link) ซึ่งแทนด้วยพอยเตอร์ RLINK ซึ่งลิงค์ลิสต์ที่ประกอบด้วย คุณสมบัติดังกล่าวเราเรียกว่า “ลิงค์ลิสต์เชิงเส้นคู่” (double linked linear list) หรือลิงค์ลิสต์คู่ (double linked list) ในแต่ละทิศทาง ไม่ว่าขวาสุด หรือซ้ายสุด จะมีค่า NULL เพื่อแสดงว่าสิ้นสุดลิสต์ในแต่ละทิศทาง

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