Park-Kachen

28 กรกฎาคม 2552

DTS05-22-07-2552

สรุปสิ่งที่ได้จากการเรียน เรื่อง Linked list (ต่อ)

Circular Linked list

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

Doubly Linked list

Doubly linked list ประกอบด้วยส่วนของ Info และ พอยน์เตอร์ที่ชี้ไป 2 ทิศทาง คือ ชี้ไปยังโหนดถัดไป และชี้ไปยังโหนดก่อนหน้า ดังนั้นเราจึงสามารถทำการอ่านข้อมูลได้ 2 วิธี คือ การอ่านไปข้างหน้า และอ่านไปทางข้างหลัง

การเพิ่มข้อมูลใน doubly linked list

การเพิ่มข้อมูลใน doubly linked list จะแตกต่างจาก Singly Linked list คือ สามารถเพิ่มโหนดให้อยู่หน้าโหนดที่ระบุได

ตัวอย่างการเพิ่มข้อมูล node (Q) ให้อยู่หน้า node (P)

สแตค (Stack

สแตคเป็นโครงสร้างข้อมูลที่มีลักษณะแบบลำดับ (sequential) คือการกระทำกับข้อมูลจะกระทำที่ปลายข้างเดียวกันที่ส่วนปลายสุดของสแตค การกระทำกับข้อมูลของสแตคประกอบไปด้วยการนำเข้าข้อมูลเข้า (PUSH) ที่ส่วนบนสุดของสแตค และการนำข้อมูลออก (POP) ที่ส่วนบนสุดของสแตคเช่นกัน ในการจะ Push ข้อมูลเข้าก็ต้องตรวจสอบด้วยว่าข้อมูลในสแตคเต็มหรือไม่ หากสแตคเต็มก็จะไม่สามารถ Push หรือนำข้อมูลเข้าได้ เช่นเดียวกับการ Pop ข้อมูลออกก็ต้องตรวจสอบด้วยว่ามีข้อมูลอยู่ในสแตคหรือไม่ หากไม่มีข้อมูลอยู่ในสแตคหรือสแตคว่าง (empty stack) ก็ไม่สามารถ pop ได้การนำข้อมูลเข้า-ออก จากสแตค (push , pop) จะมีลักษณะแบบเข้าหลัง ออกก่อน (LIFO : Last In , First Out) คือ ข้อมูลที่เข้าไปในสแตคลำดับหลังสุด จะถูกนำข้อมูลออกจากสแตคเป็นลำดับแรก ยกตัวอย่างการทำงานแบบ LIFO เช่น การวางจานซ้อนกัน

รูปแสดงลักษณะของสแตค ที่ประกอบด้วยข้อมูล A , B , C , D และ E มี TOP ที่ชี้ที่สมาชิกตัวบนสุดของสแตค