একটি এড়িয়ে যাওয়ার তালিকায়, এই বিন্দু থেকে অনুসন্ধান চালিয়ে যাওয়ার মাধ্যমে b উপাদান ধারণকারী একটি নোড থেকে একটি উপাদান অনুসন্ধান করতে পারেন৷
মনে রাখবেন যে যদি a
ব্যাকওয়ার্ড কেসটি স্কিপ লিস্টে সাধারন সার্চের সাথে সিমেট্রিক, কিন্তু ফরোয়ার্ড কেস আসলে আরো জটিল।
সাধারণত, একটি এড়িয়ে যাওয়ার তালিকায় অনুসন্ধান দ্রুত হবে বলে আশা করা হয় কারণ তালিকার শুরুতে সেন্টিনেলটিকে সবচেয়ে লম্বা নোড হিসাবে বিবেচনা করা হয়।
যাইহোক, আমাদের আঙুল উচ্চতা 1 এর একটি নোডের সাথে যুক্ত হতে পারে। এই কারণে, অনুসন্ধান করার চেষ্টা করার সময় আমরা খুব কমই আরোহণ করতে পারি; এমন কিছু যা সাধারণত ঘটে না।
বাদ দেওয়া তালিকাগুলির সবচেয়ে গুরুত্বপূর্ণ বৈশিষ্ট্যগুলি হল তাদের প্রত্যাশিত রৈখিক স্থান প্রয়োজন, প্রত্যাশিত O(লগ n) স্তর অন্তর্ভুক্ত, প্রত্যাশিত O(লগ n) সময়ে অনুসন্ধান সমর্থন এবং প্রত্যাশিত O(1) এ একটি নির্দিষ্ট অবস্থানে সন্নিবেশ এবং মুছে ফেলা সমর্থন করে ) সময়।
এটি স্কিপ তালিকার বিভিন্ন বৈশিষ্ট্য এবং এক্সটেনশন সম্পর্কে বিশদভাবে বর্ণনা করা হয়েছে, যাতে প্রত্যাশিত O(লগ ডি) সময়ে স্কিপ তালিকাগুলি কীভাবে আঙুলের অনুসন্ধানগুলিকে সমর্থন করে তার জন্য ছদ্ম-কোড সহ। পশ্চাৎমুখী আঙুল অনুসন্ধানের সুবিধার্থে, নোড V-এ একটি আঙুল একটি প্রত্যাশিত O(log n) স্পেস ফিঙ্গার ডেটা স্ট্রাকচার হিসাবে সংরক্ষণ করা হয় যে প্রতিটি স্তরের জন্য আমি V এর বাম দিকে নোডে একটি পয়েন্টার সংরক্ষণ করি যেখানে স্তর i পয়েন্টারটি নির্দেশ করে। V বা V-এর ডানদিকে একটি নোড। একটি আঙুল সরানোর জন্য পয়েন্টারগুলির এই তালিকাটি অনুরূপভাবে আপডেট করা প্রয়োজন।
একটি পশ্চাদগামী আঙুল অনুসন্ধান প্রথমে আঙুলের ডেটা কাঠামোর সর্বনিম্ন নোড সনাক্ত করে সম্পন্ন করা হয় যা অনুসন্ধান কী y-এর বাম দিকে থাকে, যেখানে আঙুলের ডেটা কাঠামোর নোডগুলিকে ক্রমবর্ধমান স্তরের ক্রম অনুসারে বিবেচনা করা হয়৷
তারপরে অনুসন্ধানটি একটি স্ট্যান্ডার্ড স্কিপ তালিকা অনুসন্ধানের মতো চিহ্নিত নোড থেকে নীচের দিকে এগিয়ে যায়৷
