സ്കിപ്‌ ലിസ്റ്റ്

ഇംഗ്ലീഷ് വിലാസം

https://ml.wikipedia.org/wiki/Skip_list

എളുപ്പത്തിൽ തിരച്ചിൽ നടത്താൻ സഹായിക്കുന്ന വിധം ക്രമീകരിക്കപ്പെട്ടതും ക്രമത്തിലാക്കിയ അംഗങ്ങളോട് കൂടിയതുമായ ഒരു ലിസ്റ്റ് ഡാറ്റാ സ്ട്രക്‌ച്ചർ ആണ് സ്കിപ്‌ ലിസ്റ്റ്. 1990-ൽ സാക്ഷാൽക്കരിക്കപ്പെട്ട ഈ ഡാറ്റാ സ്ട്രക്‌ച്ചർ താരതമ്യേന പുതുതാണ്. പ്രധാനമായും ഇതിന്റെ സ്വീകാര്യത എളുപ്പത്തിൽ തിരച്ചിൽ നടത്തുന്നതിനോടൊപ്പം ഓരോ അംഗങ്ങളെയും ക്രമപ്രകാരം പ്രക്രിയകൾക്ക് വിധേയമാക്കാനും സഹായിക്കുന്നു എന്നതാണ്. ഒരു മാതൃകാപരമായ സ്കിപ്‌ ലിസ്റ്റ് ബൈനറി സെർച്ച്‌ ട്രീകളുടെ അത്ര (അതായത് ലോഗരിതം നിരക്കിൽ) കാര്യക്ഷമമാണ്^[1].

സ്കിപ്‌ ലിസ്റ ആന്തരികമായി പല ശ്രേണികളിലുള്ള ഒരു കൂട്ടം ലിങ്ക്ഡ് ലിസ്റ്റുകളുടെ കൂട്ടമാണെന്നു പറയാം. അതായത് ക്രമീകരിക്കപ്പെട്ട ഒരു പ്രാഥമിക ലിസ്റ്റിനു പുറമേ മറ്റു ലിസ്റ്റുകൾ ഇടക്കുള്ള ചില അംഗങ്ങളെ ഒഴിവാക്കിക്കൊണ്ട് മുന്നിലുള്ള അംഗങ്ങളിലേക്ക് ബന്ധം സ്ഥാപിക്കുന്നു. ശ്രേണിയുടെ നില കൂടുന്തോറും ഇടയ്ക്കു ഒഴിവാക്കപ്പെടുന്ന അംഗങ്ങളുടെ എണ്ണവും കൂടും. പ്രാഥമിക ലിസ്റ്റ് എല്ലാ അംഗങ്ങളെയും ക്രമത്തിൽ ബന്ധിപ്പിച്ചിരിക്കും.

തിരച്ചിൽ തുടങ്ങുമ്പോൾ ആദ്യം ചെയ്യുന്നത് തിരച്ചിൽ തുടങ്ങുന്ന അങ്ങത്തിന്റെ ഏറ്റവും ഉയർന്ന ശ്രേണിയിലെ അടുത്ത അംഗത്തെ നോക്കിയാണ്. തിരയേണ്ട മൂല്യം ആ അംഗത്തെക്കാൾ കൂടുതലാണെങ്കിൽ തിരച്ചിൽ ലിസ്റ്റിന്റെ ആ അംഗത്തിന് ശേഷമുള്ള ഭാഗത്തേക്ക് (അതായത് വലത്തേക്ക്) ചുരുക്കാം. മൂല്യം കുറവ് ആണെങ്കിൽ ഇടത്തേക്കും. ഈ അവസ്ഥയിൽ നമ്മൾ തൊട്ടു താഴെ നിലകളിൽ പോയി ഇതേ ക്രിയകൾ ആവർത്തിക്കും. ഉദാഹരണത്തിന് ഉകളിൽ കൊടുത്ത പ്രമാണപ്രകാരമുള്ള ലിസ്റ്റിൽ 5 എന്ന മൂല്യം തിരയുമ്പോൾ.

1. ആദ്യ അംഗത്തിന്റെ മൂല്യം 1 അഞ്ചിനെക്കാൾ ചെറുത്. ഏറ്റവും മുകളിലെ ശ്രേണിയിൽ അടുത്തത് 4.
2. അംഗത്തിന്റെ 4 അഞ്ചിനെക്കാൾ ചെറുത്. മുകളിലെ ശ്രേണിയിൽ അടുത്തത് 6. അഞ്ചിനെക്കാൾ വലുതായതിനാൽ അടുത്ത ശ്രേണിയിൽ പോകുന്നു.
3. വീണ്ടും 6. അഞ്ചിനെക്കാൾ വലുതായതിനാൽ അടുത്ത ശ്രേണിയിൽ പോകുന്നു.
4. അഞ്ചിലേക്കെത്തുന്നു.