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

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

ไฟล์:Doubly_linked_list000.png‎

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

ไฟล์:Xor_linked_list000.png‎

จากรูป เมื่อตรวจของใน 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
	ไฟล์:Addition_linked_list000.png	

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

### Subtraction linked list

ไฟล์:Subtraction_linked_list000.png‎

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

หมวดหมู่:รายการโยง
หมวดหมู่:เลขคณิตฐานสอง