Lecture 7 : เรื่อง Linked List
ลิงค์ลิสต์ (Linked List) เป็นวิธีการเก็บข้อมูลอย่างต่อเนื่องของอิลิเมนต์ต่าง ๆ โดยมีพอยเตอร์เป็นตัวเชื่อมต่อแต่ละอิลิเมนท์ เรียกว่าโนด (Node) ซึ่งในแต่ละโนดจะประกอบไปด้วย 2 ส่วน คือData จะเก็บข้อมูลของอิลิเมนท์ และส่วนที่สอง คือ Link Field จะทำหน้าที่เก็บตำแหน่งของโนดต่อไปในลิสต์
ในส่วนของ data อาจจะเป็นรายการเดี่ยวหรือเป็นเรคคอร์ดก็ได้ในส่วนของ link จะเป็นส่วนที่เก็บตำแหน่งของโหนดถัดไป ในโหนดสุดท้ายจะเก็บค่า Nullซึ่งไม่ได้ชี้ไปยังตำแหน่งใด ๆ เป็นตัวบอกการสิ้นสุดของลิสต์
ในลิงค์ลิสต์จะมีตัวแปรสำหรับชี้ตำแหน่งลิสต์ (List pointer variable) ซึ่งเป็นที่เก็บตำแหน่งเริ่มต้นของลิสต์ ซึ่งก็คือ : โหนดแรกของลิสต์นั่นเอง ถ้าลิสต์ไม่มีข้อมูล ข้อมูลในโหนดแรกของลิสต์จะเป็น Null
โครงสร้างข้อมูลแบบลิงค์ลิสต์ : จะแบ่งเป็น 2 ส่วน คือ
1. Head Structure จะประกอบไปด้วย 3 ส่วน ได้แก่
- จำนวนโหนดในลิสต์ (Count)
-พอยเตอร์ที่ชี้ไปยังโหนดที่เข้าถึง (Pos)
-พอยเตอร์ที่ชี้ไปยังโหนดข้อมูลแรกของลิสต์ (Head)
2. Data Node Structure จะประกอบไปด้วยข้อมูล(Data) และพอยเตอร์ที่ชี้ไปยังข้อมูลตัวถัดไป
กระบวนงานและฟังก์ชั่นที่ใช้ดำเนินงานพื้นฐาน :
1. กระบวนงาน Create List
หน้าที่ : สร้างลิสต์ว่าง
ผลลัพธ์ : ลิสต์ว่าง
2. กระบวนงาน Insert Node
หน้าที่ : เพิ่มข้อมูลลงไปในลิสต์บริเวณตำแหน่งที่ต้องการ
ข้อมูลนำเข้า : ลิสต์ ข้อมูล และตำแหน่ง
ผลลัพธ์ : ลิสต์ที่มีการเปลี่ยนแปลง
3. กระบวนงาน Delete Node
หน้าที่ : ลบสมาชิกในลิสต์บริเวณตำแหน่งที่ต้องการ
ข้อมูลนำเข้า : ข้อมูลและตำแหน่ง
ผลลัพธ์ : ลิสต์ที่มีการเปลี่ยนแปลง
ผลลัพธ์ : ลิสต์ที่มีการเปลี่ยนแปลง
4. กระบวนงาน Search list
หน้าที่ : ค้นหาข้อมูลในลิสต์ที่ต้องการ
ข้อมูล : นำเข้าลิสต์
ผลลัพธ์ : ค่าจริงถ้าพบข้อมูล ค่าเท็จถ้าไม่พบข้อมูล
5. กระบวนงาน Traverse
หน้าที่ : ท่องไปในลิสต์เพื่อเข้าถึงและ
ประมวลผล : ข้อมูลนำเข้าลิสต์
ผลลัพธ์ : ขึ้นกับการประมวลผล เช่น เปลี่ยนแปลงค่าใน node ,
รวมฟิลด์ในลิสต์ ,คำนวณค่าเฉลี่ยของฟิลด์ เป็นต้น
6. กระบวนงาน Retrieve Node
หน้าที่ : หาตำแหน่งข้อมูลจากลิสต์
ข้อมูล : นำเข้าลิสต์
ผลลัพธ์ : ตำแหน่งข้อมูลที่อยู่ในลิสต์
7. ฟังก์ชั่น EmptyList
หน้าที่ : ทดสอบว่าลิสต์ว่างข้อมูลนำเข้า ลิสต์
ผลลัพธ์ : เป็นจริง ถ้าลิสต์ว่าง
เป็นเท็จ : ถ้าลิสต์ไม่ว่าง
8. ฟังก์ชั่น FullList
หน้าที่ : ทดสอบว่าลิสต์เต็มหรือไม่ข้อมูล
นำเข้า : ลิสต์
ผลลัพธ์ : เป็นจริง ถ้าหน่วยความจำเต็ม
เป็นเท็จ : ถ้าสามารถมีโหนดอื่น
9. ฟังก์ชั่น list count
หน้าที่ : นับจำนวนข้อมูลที่อยู่ในลิสต์
ข้อมูลนำ : เข้าลิสต์
ผลลัพธ์ : จำนวนข้อมูลที่อยู่ในลิสต์
Algorithm listCount (val pList )
Pre pList is a pointer to a valid list head structure
Return count for number of node in list
1. Return (pList->count)
End listCount
10. กระบวนงาน destroy list
หน้าที่ : ทำลายลิสต์
ข้อมูลนำเข้า : ลิสต์
ผลลัพธ์ : ไม่มีลิสต์
Linked List แบบซับซ้อน :
1. Circular Linked List เป็นลิงค์ลิสต์ที่สมาชิกตัวสุดท้ายมีตัวชี้ (list) ชี้ไปที่สมาชิกตัวแรกของลิงค์ลิสต์ จะมีการทำงานไปในทิศทางเดียวเท่านั้นคือเป็นแบบวงกลม
2. Double Linked List เป็นลิงค์ลิสต์ที่มีทิศทางการทำงานแบบ 2 ทิศทาง ในลิงค์ลิสต์แบบ 2 ทิศทาง ส่วนข้อมูลจะมีตัวชี้ไปที่ข้อมูล
ก่อนหน้า (backward pointer)
และตัวชี้ข้อมูลถัดไป (forward pointer)
ไม่มีความคิดเห็น:
แสดงความคิดเห็น