অগমেন্টেড লিঙ্কড লিস্ট: একটি অপরিহার্য গাইড

কিভাবে একটি লিঙ্ক তালিকা কাজ করে?

একটি লিঙ্কযুক্ত তালিকা একটি ডেটা কাঠামো যেখানে প্রতিটি ডেটার ক্ষেত্রগুলি অফসেটের পরিবর্তে পয়েন্টার দ্বারা সংযুক্ত থাকে। এটি একটি প্রধান উপাদান নিয়ে গঠিত যা প্রথম এবং শেষ উপাদানগুলি, তথাকথিত নোড উপাদানগুলিকে সঞ্চয় করে, যাতে সমস্ত প্রয়োজনীয় ব্যবহারকারীর ক্ষেত্র (যেমন একটি ফোন, মালিক, কোম্পানি ইত্যাদি) এবং পরবর্তী নোডের জন্য একটি পয়েন্টার থাকে৷ শেষ উপাদানটি NULL ক্ষেত্রের সাথে লিঙ্ক করা হয়েছে যা তালিকার শেষ নির্দেশ করে।

লিঙ্ক করা তালিকায় একটি নতুন উপাদান যোগ করা হলে, প্রধান নোডকে অবশ্যই নতুন শেষ-নোডে "টেইল" পয়েন্টার আপডেট করতে হবে এবং পূর্ববর্তী NULL-পয়েন্টারটিকে অবশ্যই নতুন টেলে আপডেট করতে হবে।

এই ডাটা স্ট্রাকচার পুরো অ্যারের রিসাইজ না করেই নতুন ডেটার একটি দক্ষ রেকর্ডিংয়ের অনুমতি দেয়। এটি শুধুমাত্র লেখার ডেটা সংরক্ষণ করার জন্য একটি কার্যকর পদ্ধতি এবং এটির জন্য উপাদানের পরিমাণ আগে থেকে জানার প্রয়োজন নেই। এটি একটি সাধারণ ডেটা স্ট্রাকচার, এবং মেমরিতে এটি এইরকম দেখায়:

উচ্ছেদ কীগুলির জন্য লিঙ্ক করা তালিকা৷

আগের একটি নিবন্ধে , আমরা প্রতিটি আইটেম মুছে ফেলার পরে গাছটি না রেখে গাছটি স্ক্যান করার জন্য একটি বাফারের প্রয়োজনীয়তা নিয়ে আলোচনা করেছি। GC সহ ভাষাগুলিতে, এটি কোনও সমস্যা নয়। যাইহোক, যখন অ্যাপ্লিকেশন কোড মেমরি পরিচালনা করে, একটি বাফার ভিত্তিক একটি লিঙ্ক তালিকার উপর ভিত্তি করে যা পুরানো উপাদান রয়েছে একটি সমাধান হতে পারে।

একটি লিঙ্ক তালিকা উপাদান দ্রুত যোগ করার অনুমতি দেয়. যাইহোক, লিঙ্ক করা তালিকায় কিছু খুঁজে পেতে ক্রমাগত স্ক্যানিং প্রয়োজন, এটি দ্রুত কী পুনরুদ্ধারের জন্য অনুপযুক্ত করে তোলে। এইভাবে, এটি ডেটা লগিং করার, অস্থায়ী বাফার তৈরি করা এবং হেড নোডগুলি থেকে ক্রমিক রিড করার জন্য ডেটা সংগঠিত করার জন্য একটি কার্যকর সমাধান।

প্রিমম্প করার জন্য উপাদানগুলি সন্ধান করা এই জাতীয় কাজের একটি উদাহরণ। প্রিম্পশন প্রায়ই বিভিন্ন ক্যাশে বাস্তবায়নে ব্যবহৃত হয়। ক্যাশে ডেটা রয়েছে যা বৃহত্তর লেটেন্সি সহ অন্যান্য মেমরি উত্স থেকে পুনরুদ্ধার করা যেতে পারে। ক্যাশে সাধারণত প্রধান মেমরিতে সংরক্ষণ করা হয়। প্রধান মেমরি সীমিত, এবং কার্যকরী ব্যবহারের জন্য, শুধুমাত্র একটি ছোট স্ন্যাপশট ডেটা প্রধান মেমরিতে সংরক্ষণ করা যেতে পারে।

এটির জন্য আমাদের মেমরিকে আরও স্মার্টভাবে ব্যবহার করতে হবে, খুব কমই অনুরোধ করা ডেটার জন্য মেমরির ব্যবহার এড়িয়ে চলুন এবং খুব কমই অনুরোধ করা হলে এই জাতীয় ডেটা অপসারণ করুন।

ক্যাশে ক্ষেত্রগুলি উচ্ছেদ করার জন্য একটি কার্যকর পদ্ধতি হল সর্বনিম্ন সম্প্রতি ব্যবহৃত (LRU) পদ্ধতি। এখানে নীচে LRU উপস্থাপনা আছে:

এই ক্ষেত্রে, অ্যাপ্লিকেশনটিতে সম্প্রতি ব্যবহৃত বস্তুগুলি সংরক্ষণ করার জন্য কমপক্ষে একটি লিঙ্কযুক্ত তালিকা অন্তর্ভুক্ত রয়েছে এবং দ্রুত অনুসন্ধানের জন্য অন্যান্য ডেটা স্ট্রাকচার (হ্যাশ টেবিলের মতো) রয়েছে। নোডগুলি পরস্পর সংযুক্ত।

যখন একজন ব্যবহারকারী হ্যাশ টেবিল থেকে ডেটা পুনরুদ্ধার করে, লিঙ্ক করা তালিকাটি এই ডেটাটিকে টেইলে সরিয়ে রিফ্রেশ করে। ফলস্বরূপ, বেশ কয়েকটি অপারেশনের পরে, লেজে সম্প্রতি ব্যবহৃত ডেটা থাকে, যখন মাথা খুব কমই অনুরোধ করা ডেটা ধারণ করে।

মেমরি ওভারফ্লো ক্ষেত্রে, অ্যাপ্লিকেশন পর্যাপ্ত মেমরি প্রকাশ করতে প্রথম N উপাদানগুলি স্ক্যান করতে পারে। এটি একটি সহজ ক্রিয়াকলাপ কারণ লিঙ্কযুক্ত তালিকাটি অনুক্রমিক স্ক্যানগুলির সাথে খাপ খায়৷ খুব কমই ব্যবহৃত ডেটা সহ মেমরি প্রকাশ করা হবে এবং নতুন আরও ঘন ঘন নোডগুলি ক্যাশে সংরক্ষণ করা যেতে পারে।

 #include <stdlib.h> #include <stdio.h> typedef struct lnode_t { struct lnode_t *next; struct lnode_t *prev; void *ptr; } lnode_t; typedef struct list_t { lnode_t *head; lnode_t *tail; } list_t; lnode_t* lru_insert(list_t *list, char *ptr) { if (!list->head) { list->head = list->tail = calloc(1, sizeof(lnode_t)); list->head->ptr = ptr; return list->head; } lnode_t *saved_tail = list->tail; lnode_t *new = calloc(1, sizeof(sizeof(lnode_t))); new->ptr = ptr; saved_tail->next = new; new->prev = saved_tail; list->tail = new; return new; } void lru_update(list_t *list, lnode_t *lnode) { if (list->tail == lnode) { return; } lnode_t *saved_tail = list->tail; saved_tail->next = lnode; if (!lnode->prev) list->head = lnode->next; lnode->next = NULL; lnode->prev = saved_tail; list->tail = lnode; } void lru_evict(list_t *list, int items, void (*func)(void* arg, void *ptr), void* arg) { lnode_t *lnode = list->head; while(items-- && lnode) { func(arg, lnode->ptr); lnode_t *prev = lnode->prev; lnode_t *next = lnode->next; if (prev) prev->next = next; if (next) next->prev = prev; free(lnode); lnode = next; } if (!lnode) list->head = list->tail = NULL; } void print_deleted_obj(void *arg, void *ptr) { printf("evicted: %p\n", ptr); deleteThisInTheOtherStructure(arg, ptr); } int main() { list_t *list = calloc(1, sizeof(list_t)); lnode_t *test = lru_insert(list, "some data"); lru_insert(list, "another data"); lru_update(list, test); lru_evict(list, 1, print_deleted_obj, otherStructure); }

একটি মন্তব্য: যখন উপাদান ব্যবহারের সংখ্যা ফ্রিকোয়েন্সিতে উল্লেখযোগ্যভাবে পৃথক হয় (উদাহরণস্বরূপ, 1 মিলিয়নের মধ্যে শীর্ষ 100 কীগুলিতে 95% অনুরোধ বিতরণ করা হয়), তখন স্প্লে ট্রি ক্যাশে সংরক্ষণের জন্য আরও উপযুক্ত হতে পারে। প্রতিটি নোড ব্যবহারের ফ্রিকোয়েন্সির উপর ভিত্তি করে এই গাছটি ভারসাম্যপূর্ণ।

স্প্লে ট্রির মূল ধারণাটি এলআরইউ-এর বিপরীত - সর্বাধিক ব্যবহৃত উপাদানগুলি মূলের কাছাকাছি অবস্থিত, এই ডেটা স্ট্রাকচারটিকে ক্যাশের প্রাথমিক কাঠামো হিসাবে আদর্শ করে তোলে।

উচ্ছেদ দুটি উপায়ে সমাধান করা যেতে পারে: মূল কাঠামোর সাথে আন্তঃসংযুক্ত একটি লিঙ্কযুক্ত তালিকা ব্যবহার করে, অথবা একটি স্প্লে ট্রিকে থ্রেডেড বাইনারি ট্রিতে পরিবর্তন করে। স্প্লে ট্রির নোডগুলি ইতিমধ্যে ব্যবহারের ফ্রিকোয়েন্সি অনুসারে অর্ডার করা হয়েছে। যদিও গাছের পাতার অতিরিক্ত থ্রেডিংয়ের জন্য বেশি CPU সময় লাগতে পারে, তাই এটি মেমরি সংরক্ষণ করতে পারে।

মেমরিতে সম্প্রতি ব্যবহৃত ডেটার ত্বরণকে আরও ভালভাবে বোঝার জন্য, আপনি এই লিঙ্কে লাইভ VM মাইগ্রেশনের একটি উদাহরণ দেখতে পারেন।

লিঙ্ক করা তালিকার স্ক্যান গতি উন্নত করুন

যেমনটি আগে উল্লেখ করা হয়েছিল, লিঙ্কযুক্ত তালিকাগুলি ডেটা লেখার জন্য দ্রুততম সমাধান সরবরাহ করে। তাদের স্ক্যানিং গতি ভাল, কিন্তু এটি অ্যারের স্ক্যান গতির চেয়ে ধীর।

আমি পূর্ববর্তী নিবন্ধে ডেটা স্থানীয়তা হিসাবে এই সমস্যাটি বর্ণনা করেছি। যাইহোক, বাইনারি গাছের মতো হওয়ায়, লিঙ্কযুক্ত তালিকার উন্নতির সম্ভাবনা রয়েছে। লিঙ্কযুক্ত তালিকাগুলি আনরোল করা আপনাকে তালিকার প্রতিটি নোডে আরও ডেটা সংরক্ষণ করতে দেয়। এইভাবে, এটি পরবর্তী পয়েন্টার নোডে মেমরি সংরক্ষণ করে, এবং কখনও কখনও এটি কর্মক্ষমতা উন্নত করে, এই শর্তে যে উপাদানটির আকার CPU ক্যাশে লাইনের সাথে ফিট করে:

মূল ধারণাটি অপরিবর্তিত রয়েছে, তবে মেমরিতে তালিকার উপস্থাপনা পরিবর্তন করা হবে।

এটা অনেক উপায়ে পরিবর্তন হবে. নীচে 2টি বিকল্প রয়েছে:

এই উন্নতিগুলি লিঙ্কযুক্ত তালিকাগুলির কার্যকারিতা বাড়ায়, তবে তারা কোডে কিছু জটিলতা যোগ করে। একটি লিঙ্কযুক্ত তালিকার সাথে ডিস্ক-অপারেশনের জন্য, একটি আনরোলড নোডে আরও উপাদান থাকতে পারে। এটি কীভাবে কাজ করে তা বোঝার একটি সহজ উপায় হল অ্যারেগুলির একটি লিঙ্কযুক্ত তালিকা কল্পনা করা।

কোডে, আমাদের struct বিবরণ পরিবর্তন করতে হবে, এবং এখন থেকে, কাঠামোর অ্যারেতে প্রতিটি উপাদান পড়তে বা লিখতে হবে:

 typedef struct lnode_t { struct lnode_t *next; struct lnode_t *prev; void *ptr[3]; } lnode_t;

তালিকা এড়িয়ে যান

স্কিপ লিস্ট হল একটি লিঙ্ক করা তালিকার সার্চ এলিমেন্টের গতি বৈশিষ্ট্য উন্নত করার একটি পদ্ধতি। এই ধরনের লিঙ্ক করা তালিকা লিঙ্ক করা তালিকা অর্ডার করার জন্য একটি কী সঞ্চয় করে এবং একটি সাধারণ স্ক্যানিং অপারেশনের চেয়ে নোডগুলিকে আরও দক্ষতার সাথে সনাক্ত করতে অতিরিক্ত পয়েন্টার অন্তর্ভুক্ত করে।

অতিরিক্ত নোডগুলি একটি স্কিপ তালিকায় নোডগুলির মধ্যে ট্র্যাভার্স করার গতি বাড়ায়। এটি একটি বাইনারি অনুসন্ধানের মত কাজ করে। বিপরীতে, নতুন উপাদান যোগ করতে আরও সময় লাগে। অতএব, বাদ দেওয়া তালিকার একটি কী থাকতে হবে। অ্যাপ্লিকেশানগুলি গতির বৈশিষ্ট্যগুলি উন্নত করতে যে কোনও সংখ্যক স্তর তৈরি করতে পারে। বেশিরভাগ ক্ষেত্রে, একটি ভাল পছন্দ হল গাছের উচ্চতার তুলনায় সামান্য কম বা প্রায় একই স্তর থাকা। (উপরের ছবিটি দেখুন)

অনুসন্ধান করার সময়, একটি অ্যাপ্লিকেশন সর্বোচ্চ স্তর থেকে শুরু হয়, যা দ্রুততম রুট। কাছাকাছি কী সনাক্ত করার পরে এটি একটি নিম্ন স্তরে নেমে আসে যতক্ষণ না পছন্দসই নোড পাওয়া যায়।

এই প্রক্রিয়ার ফলে O(log(n)) এর সময় জটিলতা দেখা দেয়। উদাহরণস্বরূপ, 16টি নোড সহ একটি স্কিপ লিস্টের জন্য 4টি স্তর, 1 মিলিয়ন নোডের জন্য 20টি স্তর এবং 4 বিলিয়ন নোডের জন্য 32টি স্তর ব্যবহার করা RB-ট্রিতে একই সময়ের জটিলতা প্রদান করে৷

নিম্নলিখিত কারণগুলির জন্য তালিকা এড়িয়ে যাওয়া ভাল:

• বাস্তবায়নের সরলতা। RB-বৃক্ষের অনুরূপ বৈশিষ্ট্য থাকা সত্ত্বেও, এটি বাস্তবায়ন এবং রক্ষণাবেক্ষণ করা অনেক সহজ।

• স্কিপ তালিকার শেষে নতুন নোড যুক্ত করার ক্ষেত্রে উচ্চ দক্ষতা।

• স্কিপ তালিকার একটি থ্রেড-নিরাপদ বাস্তবায়ন তৈরি করা গাছের চেয়ে সহজ।

আসুন এই ধারণার বাস্তবায়ন অন্বেষণ করা যাক!

স্ট্রাকচার নোড:

 typedef struct skip_node { uint64_t key; uint64_t value; struct skip_node **forward; } skip_node; typedef struct skip_t { uint64_t level; uint8_t max_level; skip_node *header; } skip_t;

নোড তৈরি করার ফাংশন:

 skip_node* create_skip_node(uint64_t key, int value, int level) { skip_node *newskip_node = (skip_node*)malloc(sizeof(skip_node)); newskip_node->key = key; newskip_node->value = value; newskip_node->forward = malloc(sizeof(skip_node)*level); for (uint64_t i = 0; i < level; i++) { newskip_node->forward[i] = NULL; } return newskip_node; } skip_t* skip_new(uint8_t max_level) { skip_t *list = (skip_t*)malloc(sizeof(skip_t)); list->level = 0; list->max_level = max_level; skip_node *header = create_skip_node(0, 0, max_level); list->header = header; for (uint64_t i = 0; i < max_level; i++) { header->forward[i] = NULL; } return list; }

সন্নিবেশের সময়, কাজটির মধ্যে রয়েছে নোডটি সংরক্ষণ করার জন্য সঠিক অবস্থান সনাক্ত করা এবং এই নোডের সাথে সংযোগ করার জন্য স্তরের সংখ্যা নির্ধারণ করা। স্তরগুলি নির্ধারণের জন্য একটি র্যান্ডম ফাংশন ব্যবহার প্রতিটি নতুন নোডের জন্য প্রক্রিয়াটিকে সহজ করতে সহায়তা করে। গড়ে, এই ফাংশনটি 50% ক্ষেত্রে দ্বিতীয় স্তরটি বরাদ্দ করে, 25% ক্ষেত্রে তৃতীয় স্তরটি, ইত্যাদি। এই পদ্ধতিটি উপাদানের ভারসাম্য বজায় রাখতে মেমরিতে অ্যাক্সেসের সময়কে কমিয়ে দেয়।

 uint64_t random_level(uint8_t max_level) { uint64_t level = 1; while (rand() < RAND_MAX / 2 && level < max_level) { level++; } return level; } void skip_insert(skip_t *list, uint64_t key, int value) { skip_node *update[list->max_level]; skip_node *current = list->header; for (uint64_t i = list->level - 1; i >= 0; i--) { while (current->forward[i] != NULL && current->forward[i]->key < key) { current = current->forward[i]; } update[i] = current; } current = current->forward[0]; if (current == NULL || current->key != key) { uint64_t newLevel = random_level(list->max_level); if (newLevel > list->level) { for (uint64_t i = list->level; i < newLevel; i++) { update[i] = list->header; } list->level = newLevel; } skip_node *newskip_node = create_skip_node(key, value, newLevel); for (uint64_t i = 0; i < newLevel; i++) { newskip_node->forward[i] = update[i]->forward[i]; update[i]->forward[i] = newskip_node; } } }

নোড অনুসন্ধান করার ফাংশন:

 skip_node* skip_search(skip_t *list, uint64_t key) { skip_node *current = list->header; for (uint64_t i = list->level - 1; i >= 0; i--) { while (current->forward[i] != NULL && current->forward[i]->key < key) { current = current->forward[i]; } } current = current->forward[0]; ++nodes_scan; if (current != NULL && current->key == key) return current; else return NULL; }

লিঙ্ক করা তালিকা, বাদ দেওয়া তালিকা এবং RB ট্রির কার্যক্ষমতা পরীক্ষা করার জন্য একটি বেঞ্চমার্ক ফাংশন। কী হিসাবে ব্যবহৃত মান দুটির শক্তি হিসাবে সেট করা হয়। পরীক্ষার উদ্দেশ্যে মান কোন ব্যাপার না.

 skip_t *skipList = skip_new(atoi(argv[1])); list_t *llist = list_new(); tree_t *tree = calloc(1, sizeof(*tree)); size_t to_index = 50000000; struct timespec s_icalc; struct timespec e_icalc; struct timespec s_scalc; struct timespec e_scalc; clock_gettime(CLOCK_REALTIME, &s_icalc); for (uint64_t i = 0; i < to_index; ++i) tree_insert(tree, i, i*2); clock_gettime(CLOCK_REALTIME, &e_icalc); count = 0; nodes_scan = 0; clock_gettime(CLOCK_REALTIME, &s_scalc); for (uint64_t i = 0; i < to_index; ++i) { node_t *node = tree_get(tree, i); } clock_gettime(CLOCK_REALTIME, &e_scalc); clock_gettime(CLOCK_REALTIME, &s_icalc); for (uint64_t i = 0; i < to_index; ++i) skip_insert(skipList, i, i*2); clock_gettime(CLOCK_REALTIME, &e_icalc); count = 0; clock_gettime(CLOCK_REALTIME, &s_scalc); for (uint64_t i = 0; i < to_index; ++i) { skip_node* ret = skip_search(skipList, i); } clock_gettime(CLOCK_REALTIME, &e_scalc); clock_gettime(CLOCK_REALTIME, &s_icalc); for (uint64_t i = 0; i < to_index; ++i) list_add(llist, NULL, NULL); clock_gettime(CLOCK_REALTIME, &e_icalc);

ক্রমান্বয়ে ক্রমবর্ধমান কীগুলিতে এই ডেটা স্ট্রাকচার পরীক্ষা করার ফলাফল:

এটি সন্নিবেশ করার সর্বোত্তম সময় (যদি আপনি একটি সহজ লিঙ্কযুক্ত তালিকা বিবেচনা না করেন) এবং উপাদানগুলি অনুসন্ধান করার জন্য বেশ দ্রুত পদ্ধতি।

ক্রমান্বয়ে হ্রাসকারী কীগুলির উপর এই ডেটা স্ট্রাকচারগুলি পরীক্ষা করার ফলাফল:

এটি বোঝা সহজ: একটি স্কিপ তালিকার এই বাস্তবায়নে শুধুমাত্র প্রথম উপাদানটির প্রধান পয়েন্টার রয়েছে। শেষে নোড যোগ করা আরও জটিল। এই পদ্ধতি পরিবর্তন করতে, আমরা একটি দ্বিতীয় পয়েন্টার যোগ করতে পারি (লেজের দিকে) অথবা এড়িয়ে যাওয়ার তালিকা বিপরীত করতে পারি (মাথাটি বড় মান নির্দেশ করবে)। এর মানে হল একটি এড়িয়ে যাওয়ার তালিকা হল লগ ডেটা যেমন কাফকা স্ট্রিমগুলির জন্য একটি কার্যকর ডেটা কাঠামো৷ সেক্ষেত্রে, এটি আরবি গাছের চেয়ে অন্তত দ্বিগুণ দ্রুত এবং বাস্তবায়ন করা সহজ হতে পারে।

স্কিপ লিস্ট লিঙ্কড তালিকার সন্নিবেশের গতি কমিয়ে দেয়, তবে, অনুক্রমিক ডেটার জন্য, উপাদানগুলিতে লগারিদম অ্যাক্সেসের সময় সহ অন্যান্য ডেটা স্ট্রাকচারের তুলনায় এটি দ্রুত থাকে, বিশেষ করে যখন কীগুলি ক্রমানুসারে বৃদ্ধি পায়। তা সত্ত্বেও, কীগুলির যেকোন ক্রমিক বৃদ্ধি গাছে সন্নিবেশকে জটিল করে তোলে কারণ এটি গাছের ভারসাম্য বজায় রাখতে প্রচুর ঘূর্ণন ঘটায়।

এটি কার্যকরভাবে কাজ করে যখন সমগ্র ক্রম জুড়ে মান বৃদ্ধি (বা হ্রাস) হয়। উদাহরণস্বরূপ, যদি আমরা কীগুলি র্যান্ডমাইজ করি, ফলাফলগুলি ভিন্ন হবে:

যেমনটি দেখা যায়, মান জুড়ে বিতরণ RB গাছের গতির বৈশিষ্ট্যকে উল্লেখযোগ্যভাবে প্রভাবিত করে না, তবে এটি উল্লেখযোগ্যভাবে স্কিপ তালিকার কার্যকারিতাকে প্রভাবিত করে।

উপসংহার

আজ, আমাদের অ্যাপ্লিকেশনগুলি বিভিন্ন উপায়ে মেমরি বা ডিস্কে ডেটা সংগঠিত করতে পারে। মানচিত্র এবং তালিকাগুলি বিভিন্ন উদ্দেশ্যে বিভিন্ন ক্রমে ডেটা সাজানোর ক্ষেত্রে গুরুত্বপূর্ণ ভূমিকা পালন করে। এই কাঠামোগুলি পর্যাপ্ত কর্মক্ষমতা, সম্পদের দক্ষতা এবং সক্ষমতা নিশ্চিত করে।

মাঝে মাঝে, এটি আমাদের প্রয়োজনের জন্য যথেষ্ট নয়, এবং অ্যাপ্লিকেশনটিকে আরও সর্বোত্তম হওয়ার জন্য গুরুত্বপূর্ণ অংশগুলিতে পরিবর্তন করতে হবে। কিছু ক্ষেত্রে আরও উপযুক্ত ডেটা স্ট্রাকচার ব্যবহার করে উপকৃত হতে পারে, যেমন সঠিক মিল বা মেমরি অর্থনীতির জন্য গাছ। অন্যান্য - অ্যালগরিদমের উন্নতি থেকে, যেমন পৃথক থ্রেড কর্মক্ষমতা উন্নত করতে অ্যাসিঙ্ক্রোনাস পদ্ধতি ব্যবহার করে।

যখন অন্যান্য সমস্ত বিকল্প সেখানে নিঃশেষ হয়ে যায়, তখন অবশিষ্ট পদ্ধতিটি ডেটা কাঠামোকে মানিয়ে নেওয়া এবং ব্যবহারের পদ্ধতি সামঞ্জস্য করা। ব্যবহারিকভাবে নির্দিষ্ট কাজের জন্য এগুলিকে আরও উপযুক্ত করার জন্য ডেটা কাঠামোর কিছু পরিবর্তনের উদাহরণ রয়েছে।

যদিও একটি লিঙ্ক করা তালিকা প্রাথমিকভাবে শুধুমাত্র-রাইট এবং সিকোয়েন্স-স্ক্যানিং ডেটা স্ট্রাকচার, এটি RB ট্রির চেয়ে বেশি অপ্টিমাইজ করা যেতে পারে এবং শুধুমাত্র লেখার ক্ষেত্রে কার্যকরী থাকতে পারে। যাইহোক, নির্দিষ্ট বৈশিষ্ট্যের বৃদ্ধি অন্যদের প্রভাবিত করতে পারে। অতএব, সর্বোত্তম উপায় হ'ল যা গুরুত্বপূর্ণ তা অগ্রাধিকার দেওয়া এবং যা নয় তা বর্জন করা।