รายการข้าม

ในวิทยาการคอมพิวเตอร์ การก้าวกระโดดเป็นโครงสร้างข้อมูลที่ช่วยให้สามารถค้นหาได้อย่างรวดเร็ว ภายในลำดับขององค์ประกอบ การค้นหาอย่างรวดเร็วทำได้โดยการรักษาลำดับชั้นที่เชื่อมโยงกันของ subsequences โดยที่ลำดับชั้นต่อเนื่องจะข้ามไปยังองค์ประกอบที่น้อยกว่าก่อนหน้านี้ การค้นหาจะเริ่มต้นในลำดับชั้นที่เล็กที่สุดจนกว่าจะพบองค์ประกอบสองอย่างต่อเนื่องหนึ่งส่วนมีขนาดเล็กและใหญ่กว่าหรือเท่ากับองค์ประกอบที่ค้นหา ผ่านลำดับชั้นที่เชื่อมโยงองค์ประกอบทั้งสองนี้เชื่อมโยงกับองค์ประกอบของลำดับชั้นที่เบาบางที่สุดถัดไปซึ่งการค้นหาจะดำเนินต่อไปจนกว่าเราจะค้นหาลำดับทั้งหมด องค์ประกอบที่ถูกข้ามไปอาจจะได้รับการคัดเลือกให้เป็นไปตามความเป็นไปได้ หรือ deterministically กับอดีตเป็นเรื่องธรรมดามากขึ้น
ลักษณะ.
รายละเอียดการดำเนินการ.
องค์ประกอบที่ใช้สำหรับรายการข้ามจะมีมากกว่าหนึ่งตัวชี้เนื่องจากสามารถมีส่วนร่วมในมากกว่าหนึ่งรายการ
การแทรกและการลบจะดำเนินการเหมือนกับการดำเนินการรายการที่เชื่อมโยงกันยกเว้นองค์ประกอบ "สูง" ที่ต้องแทรกหรือลบออกจากรายการที่เชื่อมโยงกันมากกว่าหนึ่งรายการ O (n) การดำเนินงานซึ่งบังคับให้เราไปเยี่ยมชมทุกโหนดตามลำดับจากน้อยไปมาก (เช่นพิมพ์รายชื่อทั้งหมด) ให้โอกาสในการแสดง derandomization เบื้องหลังฉากของโครงสร้างระดับของรายการข้ามไปในทางที่ดีที่สุดนำรายการข้ามไปที่ O (log n) เวลาค้นหา (เลือกระดับของโหนดที่ จำกัด ของ i เป็น 1 บวกจำนวนครั้งที่เราสามารถแบ่ง i ถึง 2 ซ้ำ ๆ ก่อนที่มันจะกลายเป็นคี่นอกจากนี้ i = 0 สำหรับส่วนหัวอินฟินิตี้เชิงลบเนื่องจากเรามีกรณีพิเศษในการเลือก เป็นระดับที่เป็นไปได้สูงสุดสำหรับโหนดที่เป็นลบและ / หรือบวกอนันต์) อย่างไรก็ตามวิธีนี้ยังช่วยให้ใครรู้ได้ว่ามีโหนดทั้งหมดที่อยู่ในระดับสูงกว่า 1 โหนดอยู่หรือไม่และลบออกอีกทางเลือกหนึ่งคือเราสามารถสร้างโครงสร้างระดับให้เป็นแบบสุ่มโดยใช้วิธีดังต่อไปนี้
ดัชนีการก้าวกระโดด
ตามที่อธิบายไว้ข้างต้น Skiplist จะสามารถแทรกและกำจัดค่าจากลำดับที่เรียงลำดับได้อย่างรวดเร็ว O (log n) มีเพียงช้า O (n) lookups ของค่าในตำแหน่งที่กำหนดในลำดับ (เช่นคืนค่า 500th) ; อย่างไรก็ตามด้วยการปรับเปลี่ยนเล็กน้อยของการค้นหาแบบสุ่มจะสามารถปรับปรุงการค้นหาให้เป็น O (log n)
สำหรับทุกลิงก์ให้เก็บความกว้างของลิงก์ด้วย ความกว้างถูกกำหนดเป็นจำนวนลิงก์ของชั้นล่างที่กำลังสำรวจโดยลิงก์ "ช่องทางด่วน" แต่ละชั้นสูงกว่า ตัวอย่างเช่นนี่คือความกว้างของลิงก์ในตัวอย่างที่ด้านบนของหน้า:<syntaxhighlight>
 1 10
 o---> o---------------------------------------------------------> o Top level
 1 3 2 5
 o---> o---------------> o---------> o---------------------------> o Level 3
 1 2 1 2 3 2
 o---> o---------> o---> o---------> o---------------> o---------> o Level 2
 1 1 1 1 1 1 1 1 1 1 1 
 o---> o---> o---> o---> o---> o---> o---> o---> o---> o---> o---> o Bottom level
Head 1st 2nd 3rd 4th 5th 6th 7th 8th 9th 10th NIL
 Node Node Node Node Node Node Node Node Node Node
</syntaxhighlight>สังเกตว่าความกว้างของลิงก์ระดับที่สูงขึ้นคือผลรวมของลิงก์คอมโพเนนต์ด้านล่าง (เช่นความกว้าง 10 จะครอบคลุมลิงก์ที่มีความกว้าง 3, 2 และ 5 ด้านล่าง) ดังนั้นผลรวมของความกว้างทั้งหมดจะเหมือนกันในทุกระดับ (10 +1 = 1 + 3 + 2 + 5 = 1 + 2 + 1 + 2 + 5) เมื่อต้องการจัดทำดัชนีรายการข้ามและค้นหาค่า i'th ให้ข้ามรายการข้ามขณะที่นับความกว้างของแต่ละลิงก์ ลดระดับลงเมื่อความกว้างที่จะเกิดขึ้นจะใหญ่เกินไป
ตัวอย่างเช่นหากต้องการหาโหนดในตำแหน่งที่ 5 (โหนด 5) ให้ข้ามการเชื่อมโยงของความกว้าง 1 ที่ระดับบนสุด ตอนนี้จำเป็นต้องใช้สี่ขั้นตอนเพิ่มเติม แต่ความกว้างต่อไปในระดับนี้คือสิบซึ่งใหญ่เกินไปดังนั้นจึงลดลงหนึ่งระดับ ข้ามไปหนึ่งลิงก์ของความกว้าง 3. เนื่องจากอีกก้าวหนึ่งของความกว้าง 2 จะไกลเกินไปเลื่อนลงไปที่ระดับล่าง ตอนนี้สำรวจการเชื่อมโยงขั้นสุดท้ายของความกว้าง 1 ไปถึงเป้าหมายที่เรียกใช้งานทั้งหมด 5 (1 + 3 + 1)<syntaxhighlight>
 function lookupByPositionIndex (i)
 node ← head
 i ← i + 1 # don't count the head as a step
 for level from top to bottom do
 while i ≥ node.width[level] do # if next step is not too far
 i ← i - node.width[level] # subtract the current width
 node ← node.next[level] # traverse forward at the current level
 repeat
 repeat
 return node.value
 end function
</syntaxhighlight>