Linked List
ลิงค์ลิสต์เป็นการจัดเก็บชุดข้อมูลเชื่อมโยงต่อเนื่องกันไปตามลำดับ ซึ่งในลิสต์จะประกอบไปด้วยข้อมูลที่เรียกว่าโหนด (node) ในหนึ่งโหนดจะประกอบด้วยส่วนของข้อมูลที่ต้องการจัดเก็บ เรียกว่าส่วน Info และส่วนที่เป็นพอยน์เตอร์ที่ชี้ไปยังโหนดถัดไป (Link) หรือชี้ไปยังโหนดอื่นๆที่อยู่ในลิสต์ หากไม่มีโหนดที่อยู่ถัดไป ส่วนที่เป็นพอยน์เตอร์หรือ Link จะเก็บค่า NULL หรือ NILL ใช้สัญลักษณ์ ^
โครงสร้างข้อมูลแบบลิงค์ลิสต์
โครงสร้างข้อมูลแบบลิงค์ลิสต์จะแบ่งเป็น 2ประเภทคือ
1.Head Structrue จะประกอบไปด้วย3ส่วน ได้แก่ จำนวนโหนดในลิสต์(count) พอยเตอร์ที่ชี้ไปยังโหนดที่เข้าถึง(pos) คือ รายการเก็บข้อมูลปัจจุบันที่มีการท่องเข้าไปในลิสต์แทนด้วยpos และพอยเตอร์ที่ชี้ไปยังโหนดข้อมูลแรกของลิสต์(head)
2.Data Node Structure จะประกอบไปด้วยข้อมูล(Data) และพอยเตอร์ที่ชี้ไปยังข้อมูลตัวถัดไป ประกอบไปด้วย 2 ฟิลด์ ฟิลด์แรกเก็บในส่วนของข็อมูล ฟิลด์ที่ 2 เก็บส่วนของการเชื่อโยง ก็จะใช้พอยเตอร์เป็นตัวเชื่อมไปยังโหนดอื่นๆ
กระบวนงานและฟังชั่นที่ใช้ดำเนินงานพื้นฐาน
1. กระบวนงาน Create List
หน้าที่ สร้างลิสต์ว่าง
ผลลัพธ์ ลิสต์ว่าง
2. กระบวนงาน Insert Note การแทรกโหนดคือการเพิ่มสมาชิกใหม่ลงในรายการ เพิ่มข้อมูลลงไปในลิสต์บริเวณตำแหน่งที่ต้องการ
กระบวนนำเข้า ลิสต์ ข้อมูล และตำแหน่ง
ผลลัพธ์ ลิสต์ที่มีการเปลี่ยนแปลง
3. กระบวนงาน Delete Note
หน้าที่ ลบสมาชิกในลิสต์บริเวณตำแหน่งที่ต้องการ ในการลบโหนดโดยจะทำการลบทั้งโหนดและข็อมูลที่ไมต้องการออกไป หลักง่ายๆ ด้วยการเปลี่ยนลิงค์ของโหนดก่อนหน้าโหนดที่ต้องการลบให้ชี้ไปยังลิงค์ของโหนดที่ต้องการลบ และคืนค่าของโหนดที่ต้องการลบแก่หน่วยความจำไป
ข้อมูลนำเข้า ข้อมูลและตำแหน่ง
ผลลัพธ์ ลิสต์ที่มีการเปลี่ยนแปลง
4. กระบวนงาน Search Iist ในการ Search ต้องมี Condition
หน้าที่ ค้นหาข้อมูลในลิสต์ที่ต้องการข้อมูลนำเข้า
ผลลัพธ์ ค่าจริงถ้าพบข้อมูล ค่าเท็จถ้าไม่พบข้อมูล
5. กระบวนงาน Traverse
หน้าที่ ท่องไปในลิสต์เพื่อเข้าถึงและประมวลผลข้อมูลนำเข้าลิสต์
ผลลัพธ์ ขึ้นกับการประมวลผล เช่น เปลี่ยนแปลงค่าใน node , รวมฟิลด์ในลิสต์,คำนวนค่าเฉลี่ยของฟิลด์ เป็นต้น
6. กระบวนงาน Retrieve Nodeการแสดงขอมูลในโหนด
หน้าที่ หาตำแหน่งของข้อมูลจากลิสต์ข้อมูลนำข้าลิสต์
ผลลัพธ์ ตำแหน่งข้อมูลที่อยู่ในลิสต์ หากต้องการนำข้อมูลในโหนดขึ้นมาแสดง เพียงทราบถึงตำแหน่งของลิสต์ที่จัดเก็บข้อมูล ก็สามารถนำข้อมูลนั้นๆ มาแสดงได้
7. ฟังก์ชั่น Emptylist
หน้าที่ ทดสอบว่าลิสต์ว่างข้อมูลนำเข้าลิสต์
ผลลัพธ์ เป็นจริง ถ้าลิสต์ว่าง Count= ถ้าไม่เท่า Count# ตรวจสอบโดยการกำหนดวนลูบค่าหากตรวจสอบว่าไม่มีข้อมูลกำหนดค่าเป็นจริง
8. ฟังก์ชั่น Fulllist การตรวจสอบลิสต์เต็ม
หน้าที่ ทดสอบว่าลิสต์เต็มหรือไม่ข้อมูลนำเข้าลิสต์ ตรวจสอบว่าลิสต์นั้นเต็มหรือไม่ มีพื้นที่ว่างในหน่วยความจำสำหรับลิสต์หรือไม่
ผลลัพธ์ เป็นจริง ถ้าหน่วยความจำเต็ม เป็นเท็จ ถ้าสามารถมีโหนดอื่น
9. ฟังก์ชั่น list countการนับจำนวนลิสต์ทำใหทราบว่าในโครงสร้างของลิสต์ปัจจุบันมีจำนวนลิสต์อยู่เท่าใดและสามารถตรวจสอบได้จากหนดต้นลิสต์ เนื่องจากเก็บค่าไว้ที่ count
หน้าที่ นับจำนวนข้อมูลที่อยู่ในลิสต์
ผลลัพธ์ จำนวนข้อมูลที่อยู่ในลิสต์
10. กระบวนงาน Destroy listการยกเลิกลิสต์ลบแล้วก็ต้องคืนค่าให้หน่วยความจำเพื่อไปใช้งานอื่นต่อไป
หน้าที่ ทำลายลิสต์
ข้อมูลนำเข้า ลิสต์
ผลลัพธ์ ไม่มีลิสต์
2. Double Linked List ลิงค์ลิสต์คู่ เป็นลิงค์ลิสต์ที่มีทิศทางการทำงานแบบ 2 ทิศทาง ในลิงค์ลิสต์แบบ 2 ทิศทาง ส่วนข้อมูลจะมีตัวชี้ไปที่ข้อมูล ก่อนหน้า (backward pointer:B) และตัวชี้ข้อมูลถัดไป (forward pointer :F)
ไม่มีความคิดเห็น:
แสดงความคิดเห็น