รายการข้าม

รายละเอียดการดำเนินการ

องค์ประกอบที่ใช้สำหรับรายการข้ามจะมีมากกว่าหนึ่งตัวชี้เนื่องจากสามารถมีส่วนร่วมในมากกว่าหนึ่งรายการ
การแทรกและการลบจะดำเนินการเหมือนกับการดำเนินการรายการที่เชื่อมโยงกันยกเว้นองค์ประกอบ "สูง" ที่ต้องแทรกหรือลบออกจากรายการที่เชื่อมโยงกันมากกว่าหนึ่งรายการ O (n) การดำเนินงานซึ่งบังคับให้เราไปเยี่ยมชมทุกโหนดตามลำดับจากน้อยไปมาก (เช่นพิมพ์รายชื่อทั้งหมด) ให้โอกาสในการแสดง derandomization เบื้องหลังฉากของโครงสร้างระดับของรายการข้ามไปในทางที่ดีที่สุดนำรายการข้ามไปที่ O (log n) เวลาค้นหา (เลือกระดับของโหนดที่ จำกัด ของ i เป็น 1 บวกจำนวนครั้งที่เราสามารถแบ่ง i ถึง 2 ซ้ำ ๆ ก่อนที่มันจะกลายเป็นคี่นอกจากนี้ i = 0 สำหรับส่วนหัวอินฟินิตี้เชิงลบเนื่องจากเรามีกรณีพิเศษในการเลือก เป็นระดับที่เป็นไปได้สูงสุดสำหรับโหนดที่เป็นลบและ / หรือบวกอนันต์) อย่างไรก็ตามวิธีนี้ยังช่วยให้ใครรู้ได้ว่ามีโหนดทั้งหมดที่อยู่ในระดับสูงกว่า 1 โหนดอยู่หรือไม่และลบออกอีกทางเลือกหนึ่งคือเราสามารถสร้างโครงสร้างระดับให้เป็นแบบสุ่มโดยใช้วิธีดังต่อไปนี้
ซูโดโค้ด
make all nodes level 1
j ← 1
while the number of nodes at level j > 1 do
  for each i'th node at level j do
    if i is odd 
      if i is not the last node at level j
        randomly choose whether to promote it to level j+1
      else
        do not promote
      end if
    else if i is even and node i-1 was not promoted
      promote it to level j+1
    end if
  repeat
  j ← j + 1
repeat
ดัชนีการก้าวกระโดด
ตามที่อธิบายไว้ข้างต้น Skiplist จะสามารถแทรกและกำจัดค่าจากลำดับที่เรียงลำดับได้อย่างรวดเร็ว O (log n) มีเพียงช้า O (n) lookups ของค่าในตำแหน่งที่กำหนดในลำดับ (เช่นคืนค่า 500th) ; อย่างไรก็ตามด้วยการปรับเปลี่ยนเล็กน้อยของการค้นหาแบบสุ่มจะสามารถปรับปรุงการค้นหาให้เป็น O (log n)
สำหรับทุกลิงก์ให้เก็บความกว้างของลิงก์ด้วย ความกว้างถูกกำหนดเป็นจำนวนลิงก์ของชั้นล่างที่กำลังสำรวจโดยลิงก์ "ช่องทางด่วน" แต่ละชั้นสูงกว่า ตัวอย่างเช่นนี่คือความกว้างของลิงก์ในตัวอย่างที่ด้านบนของหน้า:
   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
สังเกตว่าความกว้างของลิงก์ระดับที่สูงขึ้นคือผลรวมของลิงก์คอมโพเนนต์ด้านล่าง (เช่นความกว้าง 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)
 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