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

Node (ปมข้อมูล)

            การจะสร้างลิงค์ลิสต์ต้องสร้าง node ขึ้นมาก่อน โดย node จะใช้ทั้งเก็บข้อมูลและเก็บสิ่งอ้างอิงถึงอีกปม

รูป3-1

            การสร้าง node ก็สร้างคลาส LinkedNode ขึ้นมา ภายในคลาสนี้มีตัวแปรสองตัว คือ data ก็คือข้อมูลที่อยู่ใน node (ในที่นี้ให้เก็บ int) และสร้างตัวแปลประเภท LinkedNode สำหรับตัวแปร next

            คอนสตรัคเตอร์ของคลาสก็ให้รับค่าเข้ามาใส่ไว้ในตัวแปร

รูป3-2

จากรูป ลองสร้าง LinkedNode x = new LinkedNode(“hat”, x);

            จะเห็นได้ว่าข้อมูลก็จะต่อเพิ่มจากที่หัวแล้วดันข้อมูลเก่าออกไปเรื่อยๆ แต่หากต้องการให้ข้อมูลเก่าที่เพิ่มไว้อยู่ข้างหน้าแล้วข้อมูลใหม่ถูกผลักกออกไปก็สามารถใช้ x.next เข้ามาช่วยได้

ประเภทของ Linked list

Singly linked list

            เป็นลิงค์ลิสต์แบบที่ node ชี้แต่ node ถัดไปเท่านั้นไม่ได้ชี้ตัวก่อนหน้า

            รูปสำหรับลิงค์ลิสต์ที่มี size เป็น 2 มีโหนดเก็บ x และ y ในช่องทางซ้าย ส่วนช่องทางขวาเก็บตัวถัดไป ส่วนสัญลักษณ์เหมือนสายดินคือ null

รูป3-3

Doubly linked list

เป็นลิงค์ลิสต์แบบที่ node ชี้ทั้ง node ก่อนหน้าและ node ถัดไปด้วยเป็นสองทาง

รูป3-4

Linked list with Header

            เป็นการเพิ่ม node หัว เข้าซึ่ง header จะไม่มีข้อมูลอยู่ ที่ต้องเพิ่ม header ลงไปเพราะลิงค์ลิสต์จะเป็นการเพิ่มข้อมูลจากหัวเข้าไปเรื่อยๆ ต่างจากอาร์เรย์ลิสต์ที่เพิ่มข้อมูลเข้าต่อท้ายเรื่อยๆดังนั้นเวลาลบข้อมูลสำหรับลิงค์ลิสต์จะมีปัญหาเวลาลบ node แรก ตอนลบ node สำหรับลิงค์ลิสต์จะเป็นการเปลี่ยนตัวชี้ในลิงค์ลิสต์ เช่นมี node 1 2 3 จะลบ 2 ออก ก็ให้ 1 ไปชี้ 3 แทนๆที่จะชี้ 2 แต่ถามว่าเวลาลบ 1 อะไรจะมาชี้ 1 ก็เป็นเรื่องยุ่งยาก การเพิ่ม header จะช่วยแก้ปัญหาตรงนี้ได้

Singly linked list แบบมี header

รูป3-5

Doubly linked list แบบมี header

รูป3-6

Circular linked list

                เป็นลิงค์ลิสต์แบบที่ node สุดท้ายมีตัวชี้กลับมายัง node แรก และถ้าเป็น doubly linked list

 node แรกก็ชี้ node สุดท้ายด้วย

รูป3-7

เมท็อดในลิงค์ลิสต์

void add                       สำหรับเพิ่มข้อมูล

void remove                 สำหรับลบข้อมูล

nodeAt                         หาค่าของ node ลำดับที่ต้องการ

boolean contains         หาว่ามีข้อมูลที่หาในลิงค์ลิสต์หรือไม่

int size                         ขนาดของลิงค์ลิสต์

ตัวอย่างโค๊ดของ Singly linked list แบบมี header

รูป3-8

บรรทัดที่ 4 : สร้างคลาส LinkedList

บรรทัดที่ 7 : สร้างคลาส Node (อันนี้สร้างไว้รวมกัน จะแยกเป็นอีกคลาสหนึ่งก็ได้)

บรรทัดที่ 10 : ในคลาส Node มี data เก็บข้อมูลชนิด int

บรรทัดที่ 11 : สร้างตัวแปรชนิด Node เก็บ next คือ node ของ LinkedList ต้องเก็บข้อมูลของโหนดถัดไปด้วย

บรรทัดที่ 13-16 : คอนสตรัคเตอร์ของโหนด คอนสตรัคเตอร์แรกกำหนดค่าเริ่มต้นให้ตัวแปร

บรรทัดที่ 19-22 : คอนสตรัคเตอร์ที่สองรับพารามิเตอร์เป็น int โดยเมื่อรับพารามิเตอร์มาจะกำหนดเป็นข้อมูล

รูป 3-9

บรรทัดที่ 26 : สร้างตัวแปร header เป็นตัวแปรคลาส LinkedList เป็นชนิด Node

บรรทัดที่ 27 : สร้างตัวแปร size สำหรับการเก็บขนาด

บรรทัดที่ 29 : คอนสตรัคเตอร์ ของ LinkedList

บรรทัดที่ 31 : สร้าง header ขึ้นมา

บรรทัดที่ 32 : กำหนด size เริ่มต้นเป็น 0

รูป 3-10

บรรทัดที่ 40 : สร้างคลาส contains สำหรับตรวจสอบว่ามีข้อมูลใน LinkedList ที่เหมือนกับอินพุทหรือไม่

บรรทัดที่ 42 : สร้างตัวแปร p ชนิด Node เริ่มต้นเป็น header.next ก็หมายถึงข้อมูลตัวแรก header อยู่ก่อน next

บรรทัดที่ 43 : ตรวจสอบเงื่อนไขถ้า p ไม่ใช่ null และ ยังไม่พบ data ที่เท่ากับอินพุท e ให้หาต่อ

บรรทัดที่ 45 : ให้ p เก็บข้อมูลตัวถัดไปแทน

บรรทัดที่ 48 : ส่งค่าลับไปว่า true ถ้า p ไม่ null

                                                                        รูป 3-11      

บรรทัดที่ 51 : สร้างคลาส addFirst คลาสที่จะเพิ่มข้อมูลจากตัวแรก รับพารามิเตอร์เป็นข้อมูลที่จะเพิ่ม

บรรทัดที่ 53 : สร้าง Node ใหม่ใส่อินพุทเป็นข้อมูลลงไป

บรรทัดที่ 54 : สร้างการชี้ตัวถัดไปใหม่ ในตอนแรก ตัวแรกคือตัวที่อยู่ถัดจาก header แต่พอทำการใส่ข้อมูลใหม่ไปในตำแหน่งแรก ตัวที่ใส่เข้าไปจะกลายเป็นตัวแรกแทน n เป็นตัวแรก n.next ก็จะต้องเก็บข้อมูลตัวแรกเดิมเพราะถูกผลักออกไปเป็นตัวที่ 2 เอา header.next ที่เป็นตัวแรกเดิมมาใส่ n.next

บรรทัดที่ 55 : ให้ n ไปเก็บอยู่ที่ตำแหน่งถัดจาก header ไปหนึ่งตำแหน่ง(เพราะฉะนั้น header.next =  ตำแหน่งแรกนั่นเอง)

บรรทัดที่ 56 : หลังจากที่ใส่ข้อมูลลงไปแล้วให้ size ทำการเพิ่มขนาดด้วย

รูป 3-11-1

            รูปในบรรทัดแรกคือ Linked list ที่มีอยู่แล้ว สร้างโหนดใหม่ขึ้นมา โหนดที่สร้างขึ้นมายังไม่ได้มีการโยงไปไหน(บรรทัดที่ 53) ต่อมา(บรรทัดที่ 54) ให้ส่วน next ของโหนดใหม่ไปชี้ตัวที่ header ชี้อยู่ และ(บรรทัดที่ 55) ให้ header ชี้โหนด เพิ่มข้อมูลเรียบร้อย

บรรทัดที่ 59 : สร้างคลาส addLast คลาสที่จะเพิ่มข้อมูลจากตัวท้ายสุด รับพารามิเตอร์เป็นข้อมูลที่จะเพิ่ม

บรรทัดที่ 61 : สร้าง Node ใหม่ใส่อินพุทเป็นข้อมูลลงไป

บรรทัดที่ 62  : สร้างตัวแปร p แทน header

บรรทัดที่ 63  : วนลูปหาไปเรื่อยๆโดยเริ่มจาก p หรือ header ตราบเท่าที่ยังไม่เจอข้อมูล null

บรรทัดที่ 65  : เอาข้อมูลตัวถัดไปมาเก็บใน p จนได้ ข้อมูลตัวสุดท้าย

บรรทัดที่ 67 : ได้ p เป็นข้อมูลตัวสุดท้าย ก็เพิ่มข้อมูลใหม่เข้าไปที่ next ของ p

บรรทัดที่ 68  : เมื่อเพิ่มข้อมูลแล้วก็เพิ่ม size ด้วย

รูป 3-12

บรรทัดที่ 72 : สร้างเมท็อด nodeAt ไว้สำหรับการค้นหาข้อมูลในโหนด

บรรทัดที่ 74-76 : ตรวจสอบว่าพารามิเตอร์ที่รับเข้ามาไม่ได้มีเลขน้อยกว่า 0 หรือมากกว่าขนาดของลิงค์ลิสต์ ถ้ามากกว่าให้ throw exception

บรรทัดที่ 79 : กำหนดให้โหนด p เริ่มจาก header

บรรทัดที่ 80-82 : วนลูปจากตัวแรกไปจนเท่าที่ข้อมูลยังไม่ใช่ index

บรรทัดที่ 86 : เจอข้อมูลที่ต้องการคืนค่าออกมา

รูป3-13

บรรทัดที่ 89 : สร้างเมท็อด removeAt สำหรับลบข้อมูลตำแหน่งที่ต้องการ

บรรทัดที่ 91 : สามารถใช้เมท็อดที่เพิ่งไปมาช่วยหาได้ไม่ต้องเขียนการค้นหาซ้ำ

บรรทัดที่ 93-93: ลบออกโดยการให้ next ชี้ตัวถัดไปและลดขนาดของลิสต์ลง 1

รูป 3-14

บรรทัดที่ 96 : เมท็อด get

บรรทัดที่ 102 : ขอข้อมูลตัวที่ต้องการ

บรรทัดที่ 105 : เมท็อด set

บรรทัดที่ 111 : เอาอินพุทไปใส่ตำแหน่งของข้อมูลตำแหน่งที่ต้องการ