รายการโยงออร์เฉพาะ

รางการโยงXOR (อังกฤษ: XOR Linked list) เป็นโครงสร้างข้อมูลที่ใช้ในการโปรแกรมคอมพิวเตอร์ โดยใช้ประโยชน์จากการทำ XOR (จะแทนด้วยเครื่องหมาย⊕) เพื่อลดการใช้พื้นที่ของ doubly linked list โดย doubly linked list ตามปกติจะเก็บค่าที่อยู่ของ node ที่อยู่ก่อนหน้าและ node ที่อยู่ถัดไปของแต่ละ node ซึ่งต้องเสียพื้นที่ในการเก็บ2ที่

XOR linked list จะทำการเก็บข้อมูลทั้งสองอย่างในที่เดียวโดยการทำ bit wise XOR ที่อยู่ของ node ที่อยู่ก่อนหน้าและที่อยู่ของ node ที่อยู่ถัดไป

จากรูป เมื่อตรวจของใน list จากซ้ายไปขวา เมื่ออยู่ที่ C ก็จะรู้ที่อยู่ของ node ที่อยุ่ก่อนหน้าคือ B เมื่อนำที่อยู่ของ B ไป XOR กับค่า link ของ C (ฺB ⊕ D) ก็จะได้ค่าที่อยุ่ของ D ทำให้สามารถไปทางขวาต่อได้ ซึ่งการทำแบบนี้สามารถทำได้ในทางกลับกันด้วยเพื่อจะตรวจค่าใน list ไม่ว่าจะทางไหน จำเป็นต้องรู้ค่าที่อยู่ของ 2 node ที่อยู่ติดกันก่อน ไม่สามารถทำได้โดยรู้แค่ค่าเดียว และถ้าเรียงสลับกันก็จะตรวจไปในทางตรงข้าม

บางครั้งก็ไม่ควรใช้ XOR linked list:

• การ debug ทำได้ยาก เพราะเครื่องมือในการ debug จะตามสายการ XOR ไม่ได้

• เพื่อแลกกับการประหยัดพื้นที่ ทำให้ไปเพิ่มความยุ่งยากในส่วนของ code เป็นอย่างมาก ทำให้การดูแลทำได้ยาก

• XOR ของ pointer ทำไม่ได้ในบางภาษา

• ไม่สามารถอ่านค่า pointer ได้ถ้าไม่ได้มาจากการตรวจใน list เช่น ถูกชี้มาจากโครงสร้างข้อมูลอื่น

• ในขณะที่ตรวจค่าจำเป็นต้องจำที่อยู่ของ ของก่อนหน้า เพื่อจะคำนวณที่อยู่ของ node ถัดไป

คุณสมบัติ

ถ้ารู้ node ใน list แค่ node เดียวจะไม่สามารถเข้าถึงส่วนอื่นๆของ list ได้ ใช้การ XOR เพียง2ครั้งในการตรวจไปที่ node ต่อไป โดยให้ให้มีregister 2 ตัว ตัวหนึ่งเก็บค่าของที่อยู่ปัจจุบัน และอีกตัวเก็บค่าของที่อยู่ปัจจุบัน XOR กับที่อยู่ก่อนหน้า พิจารณา list ที่มี {...B C D...} จากขวาไปซ้าย และให้ R1 R2 เป็น register ให้ R1 เก็บค่าที่อยู่ปัจจุบัน (สมมติให้อยุ่ที่ C) และให้ R2 เก็บค่าของที่อยู่ปัจจุบัน XOR กับที่อยู่ก่อนหน้า (C ⊕ D) จะสามารถหาที่อยุ่ของ B ได้โดย R2⊕ค่า link ของ C (B ⊕ D) จะได้ C ⊕ D ⊕ B ⊕ D = B ⊕ C แล้วนำไป XOR กับ R1 จะได้ B ⊕ C ⊕ C= B

X R2,Link R2 <- C⊕D ⊕ B⊕D XR R1,R2 R1 <- C ⊕ B⊕C 

ที่ปลายของ list จะให้ทำเหมือนมี node ที่มีที่อยู่เป็น 0 วางติดอยู่ที่ปลายเหมือน {0 A B C...} ค่า link ที่เก็บที่ A จะเป็น 0⊕B โดยจะต้องเพิ่มคำสั่งเพื่อตรวจสอบด้วยว่าค่าที่อยู่ต่อไปเป็น 0 หรือไม่ และที่ปลายของ list สามารถทำสะท้อนได้โดยให้เก็บ link เป็น 0 (จะเหมือน node ที่อยู่ทางซ้ายกับขวาเป็น node เดียวกัน XOR ของของที่เหมือนกันจะได้ 0)

ทำงานได้อย่างไร

จากคุณสมบัติ

X⊕X=0

X⊕0=X

X⊕Y=Y⊕X

(X⊕Y) ⊕Z=X⊕ (Y⊕Z)

register R2 จะเก็บค่า XOR ของ ที่อยู่ปัจจุบันและที่อยู่ก่อนหน้าเสมอ และค่า link จะเก็บXOR ของทางซ้ายและทางขวา ทำให้ค่า XOR ของ R2 และ link ถ้าแทนซ้ายด้วย L ขวาด้วย R ปัจจุบันด้วย C และ ตัวก่อนหน้าด้วย P จะได้ค่า R2 ⊕ link = C ⊕ P ⊕ L ⊕ R

ถ้ามาจากทางซ้าย P=L จะได้เป็น C ⊕ R

ถ้ามาจากทางขวา P=R จะได้เป็น C ⊕ L

ซึ่งเป็นค่า XOR ของที่อยู่ปัจจุบัน กับที่ที่อยู่ถัดไป

รูปแบบต่างๆ

โดยใช้หลักการเดียวกับ XOR linked list สามารถนำไปใช้กับการทำอื่นๆที่สามารถทำกลับได้ โดยแทนที่ XOR ด้วยการบวก หรือ การลบ

Addition linked list

 

list ชนิดนี้จะใกล้เคียงกับ XOR Linked list ยกเว้นค่า link เป็น 0 จะไม่ได้หมายถึงการสะท้อน การหา node ต่อไปทำได้โดยนำค่า link ลบกับที่อยู่ของ node ก่อนหน้า

Subtraction linked list

 

list ชนิดนี้จะต่างจาก XOR ตรงที่ การตรวจไปข้างหน้า กับการตรวจย้อนกลับจะใช้วิธีหาที่อยู่ของ node ต่อไป ต่างกันโดยเมื่อไปข้างหน้า จะทำการ บวกค่า link กับที่อยู่ของ node ก่อนหน้า แต่ถ้าย้อนกลับจะทำการลบที่อยู่ของ node ก่อนหน้า กับค่า link ข้อดีของ list ประเภทนี้คือสามารถ relocate ได้โดยไม่ต้องแก้ค่า link ใหม่