پیاده سازی لیست پیوندی با جاوا اسکریپت — از صفر تا صد

در این مقاله قصد داریم با شیوه پیاده سازی لیست پیوندی با جاوا اسکریپت آشنا شویم. این لیست پیوندی به صورت یک‌طرفه خواهد بود و همه کارکردهای آن را از صفر تا صد خودمان طراحی می‌کنیم.

لیست پیوندی یک‌طرفه چگونه است؟

لیست پیوندی یک‌طرفه یک ساختمان داده است که مانند آرایه برای ذخیره مقادیر مورد استفاده قرار می‌گیرد.

فیلم آموزش ساختمان داده ها – جامع و با نکات مهم در فرادرس

کلیک کنید

با این حال برخی تفاوت‌های کلیدی دارد. برخلاف یک آرایه، لیست پیوندی هیچ اندیسی ندارد. به جای آن لیست پیوندی شامل گره‌هایی است که با استفاده از اشاره‌گرها به عنصر بعدی اشاره می‌کنند.

هر گره شامل یک مقدار (عدد، رشته یا هر چیز دیگر) و یک اشاره‌گر به گره بعدی است. اگر گره بعدی وجود نداشته باشد، این اشاره‌گر null خواهد بود. در ادامه یک گره را پیاده‌سازی می‌کنیم که از آن برای ساختن لیست پیوندی خود استفاده خواهیم کرد:

1class Node {
2	constructor(value) {
3		this.value = value; // The value property can hold anything - String, number etc
4		this.next = null; // The next propery is initially set to null
5	}
6}

لیست پیوندی دارای مشخصه Head، مشخصه Tail و یک مشخصه اختیاری Length است که رد عناصر را نگهداری می‌کند. Head نخستین گره در لیست پیوندی است و Tail آخرین گره محسوب می‌شود.

برای این که بتوانیم به هر یک از گره‌های لیست دسترسی پیدا کنیم، باید از گره Head آغاز کنیم و لیست را با استفاده از مشخصه next گره‌ها پیمایش کنیم تا این که به گروهی که به دنبالش هستیم برسیم.

پیاده‌سازی لیست پیوندی

اکنون که با همه اصطلاحات فنی مرتبط آشنا شدیم، نوبت به پیاده‌سازی عملی لیست پیوندی رسیده است.

فیلم آموزش جاوا اسکریپت JavaScript – جامع و کاربردی در فرادرس

کلیک کنید

پیاده‌سازی پایه

کار خود را با تعریف کردن class آغاز می‌کنیم که مقادیر زیر را در سازنده می‌گیرد:

• head به گره نخست لیست اشاره می‌کند که در حال حاضر null است.
• tail به گره آخر لیست اشاره می‌کند که در حال حاضر null است.
• length طول لیست را نشان می‌دهد که در ابتدا روی مقدار 0 قرار دارد.

1class LinkedList {
2  constructor() {
3    this.head = null; // Points to the first node
4    this.tail = null; // Points to the last node
5    this.length = 0;
6  }
7}

در ادامه کارکردهای رایج مرتبط با لیست پیوندی را پیاده‌سازی می‌کنیم. همه کارکردهای پیاده‌سازی شده در ادامه درون کلاس LinkedList تعریف شده‌اند که قبلاً ایجاد کردیم.

تابع push

مانند آرایه، کارکرد push یک مقدار را می‌گیرد و به انتهای لیست انتساب می‌دهد:

1push(value) {
2    const node = new Node(value);
3    // Check if exist exists or not
4    if (!this.head) {
5      this.head = this.tail = node;
6    } else {
7      this.tail.next = node;
8      this.tail = node;
9    }
10    this.length++;
11  }

• تابع push یک مقدار را می‌گیرد و یک وهله از گره با آن می‌سازد.
• سپس بررسی می‌کند آیا مشخصه head به صورت null است یا نه. اگر چنین باشد یعنی هیچ عنصر دیگری در لیست نیست و تابع گره جدیداً ایجاد شده را به head و مشخصه tail انتساب می‌دهد.
• اما اگر مشخصه head به صورت null نباشد، یعنی عناصری در لیست موجود هستند و از این رو مشخصه next گره tail را طوری تنظیم می‌کنیم که به گره جدیداً ایجاد شده اشاره کند. همچنین tail جدید باید به گره جدیداً ایجاد شده اشاره کند.
• در نهایت مشخصه length یک واحد افزایش می‌یابد.

تابع Pop

تابع Pop مانند آرایه یک عنصر یا گره را از انتهای لیست حذف می‌کند. با این حال لازم است که کل لیست پیمایش شود، چون هیچ اندیسی وجود ندارد.

بدین ترتیب کل لیست را پیمایش می‌کنیم تا این که به گره ماقبل آخر برسیم. سپس مشخصه next را روی null تنظیم می‌کنیم تا به tail جدید ما تبدیل شود. کد آن به صورت زیر است:

1pop() {
2    if (this.length === 0) return undefined;
3    let current = this.head, previous = this.head;
4    while(current.next) {
5      previous = current;
6      current = current.next;
7    }
8    this.tail = previous;
9    this.tail.next = null;
10    this.length--;
11    if (this.length === 0) this.head = this.tail = null;
12    return current;
13  }

• این تابع در صورتی که لیست خالی باشد undefined خواهد بود. البته می‌توانید مقدار null نیز بازگشت دهید.
• سپس حلقه‌ای روی لیست تعریف می‌شود تا این که به tail برسد. همچنین رد آیتم قبلی نگهداری می‌شود تا به عنوان tail جدید ثبت شود.
• زمانی که به tail برسیم، گره ماقبل آخر که رد آن را نگه داشته‌ایم، به عنوان tail جدید ثبت می‌شود.
• سپس length یک واحد کاهش می‌یابد.
• در نهایت آیتم حذف‌شده بازگشت می‌یابد.
• حالت خاص – باید بررسی کنیم در صورتی که همه آیتم‌های لیست حذف شده باشند، گره head و tail مقدار null بگیرند.

تابع Unshift

این یک تابع ساده است که یک عنصر به ابتدای لیست اضافه می‌کند. ابتدا یک گره با مقداری که به تابع ارسال شده است، ایجاد می‌شود. اگر لیست خالی باشد، گره‌های head و tail طوری تنظیم می‌شوند که به این گره اشاره کنند. در غیر این صورت head کنونی طوری تنظیم می‌شود که به مشخصه next این گره اشاره کند و این گره را به عنوان head جدید تنظیم می‌کند. در نهایت مقدار مشخصه length یک واحد افزایش می‌یابد.

1unshift(value) {
2    const node = new Node(value);
3    if (this.length === 0) {
4      this.head = this.tail = node;
5    } else {
6      node.next = this.head;
7      this.head = node;
8    }
9    this.length++;
10  }

تابع Shift

این تابع نیز کاملاً ساده است. تابع Shift نخستین عنصر لیست را حذف کرده و بازگشت می‌دهد.

1shift() {
2    if (this.length === 0) return undefined;
3    const currentHead = this.head;
4    this.head = this.head.next;
5    this.length--;
6    return currentHead;
7  }

در کد فوق در صورتی که لیست خالی باشد، تابع مقدار undefined بازگشت می‌دهد. البته می‌توان مقدار null نیز بازگشت داد. Head کنونی ذخیره می‌شود و head جدید به مشخصه next در head کنونی اشاره می‌کند. مشخصه length یک واحد کاهش می‌یابد. در نهایت عنصر حذف‌شده بازگشت می‌یابد.

تابع Get

تابع Get یک عدد (به عنوان اندیس) می‌گیرد و روی لیست حلقه‌ای تعریف می‌کند تا این که گره موجود در آن اندیس را یافته و بازگشت دهد.

1get(index) {
2    if (index >= this.length || index < 0) return undefined;
3    let currentHead = this.head;
4    while(index > 0) {
5      currentHead = currentHead.next
6      index--;
7    }
8    return currentHead;
9  }

اگر اندیس ارسالی خارج از کران لیست باشد، مقدار undefined بازگشت می‌یابد. البته می‌توان مقدار null نیز بازگشت داد.

سپس حلقه تکرار روی لیست تعریف می‌شود تا این که به آن اندیس خاص برسد و گرهی که در آن اندیس است را بازگشت می‌دهیم.

تابع Set

تابع Set یک اندیس و یک مقدار می‌گیرد. سپس آن مقدار را به اندیس مشخص‌شده انتساب می‌دهد.

1set(index, value) {
2    const node = this.get(index);
3    if (node) {
4      node.value = value;
5      return true;
6    }
7    return false;
8  }

این تابع از متد get که قبلاً تعریف کردیم برای یافتن گرهی که در اندیس مشخص شده است استفاده می‌کنید. سپس در صورتی که اندیس مورد نظر پیدا شد و مقدار true بازگشت یافت، مقدار گره را انتساب می‌دهد. در غیر این صورت مقدار false بازگشت می‌یابد.

تابع Insert

این تابع مانند تابع Set یک اندیس و یک مقدار می‌گیرد. اما برخلاف تابع Set مقدار دریافتی را در اندیس مشخص شده درج می‌کند.

1insert(index, value) {
2    if (index < 0 || index > this.length) return false;
3    if (index === this.length) {
4      this.push(value);
5      return true;
6    }
7    if (index === 0) {
8      this.unshift(value);
9      return true;
10    }
11    const node = new Node(value);
12    // Get the element BEFORE the specified index
13    const previous = this.get(index - 1);
14    const temp = previous.next;
15    previous.next = node;
16    node.next = temp;
17    this.length++;
18    return true;
19  }

• اگر اندیس خارج از کران‌های لیست باشد، مقدار undefined بازگشت می‌یابد.
• اگر اندیس برابر با طول (length) لیست پیوندی باشد، مقدار ارائه‌شده به انتهای لیست اضافه می‌شود. برای سهولت کار، تابع Push که قبلاً تعریف کرده‌ایم، استفاده شده است.
• در صورتی که اندیس 0 باشد، گره با مقدار ارائه شده به ابتدای لیست، push می‌شود. در این جا برای سهولت کار از تابع unshift که قبلاً تعریف کردیم استفاده می‌کنیم.
• در غیر این صورت‌ها عنصر قبل (before) اندیس مشخص شده گرفته می‌شود و مشخصه next آن به گره جدید با مقدار تعیین‌شده انتساب می‌یابد.
• سپس مشخصه next گره جدید به مشخصه next عنصر before در اندیس مشخص شده اشاره می‌کند.
• در نهایت مقدار طول یک واحد افزایش یافته و مقدار true بازگشت می‌یابد.

تابع Remove

این تابع یک اندیس می‌گیرد و مقدار موجود در آن اندیس را حذف می‌کند.

1remove(index, value) {
2    if (index < 0 || index >= this.length) return undefined;
3    if (index === this.length) return this.pop();
4    if (index === 0) return this.shift();
5    // Get the element BEFORE the specified index
6    const previous = this.get(index - 1);
7    const nodeToRemove = previous.next;
8    previous.next = nodeToRemove.next;
9    this.length--;
10    return nodeToRemove;
11  }

• اگر اندیس خارج از کران‌های لیست باشد، مقدار undefined بازگشت می‌یابد. اگر اندیس به آخرین عنصر لیست اشاره کند، گره آخر لیست را حذف می‌کند. در این جا از تابع pop برای سهولت کار استفاده شده است.
• اگر اندیس برابر 0 باشد، گره ابتدای لیست را حذف می‌کند. در اینجا برای سهولت کار از تابع shift استفاده شده است.
• در غیر این صورت‌ها عنصر before اندیس مشخص شده دریافت می‌شود و مشخصه next آن برابر با مشخصه next گره در اندیس مشخص شده تنظیم می‌شود.
• در نهایت مقدار طول لیست 1 واحد کاهش یافته و گره حذف‌شده بازگشت می‌یابد.

سخن پایانی

در این مقاله تلاش کردیم یک ساختمان داده لیست پیوندی را از صفر تا صد در جاوا اسکریپت پیاده‌سازی کنیم. البته موارد زیادی وجود دارند که می‌توانستیم پیاده‌سازی کرده یا بهبود ببخشیم. اما با درک همین تابع‌های رایج می‌توانید بقیه بخش‌ها را خودتان تکمیل کنید. کد کامل موارد مطرح شده در این مقاله را در این ریپوی گیت‌هاب (+) ملاحظه کنید.

فیلم مجموعه آموزش جاوا اسکریپت JavaScript – مقدماتی تا پیشرفته در فرادرس

کلیک کنید

اگر این مطلب برای شما مفید بوده است، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند:

• مجموعه آموزش‌های JavaScript (جاوا اسکریپت)
• مجموعه آموزش‌های برنامه‌‌نویسی
• آموزش JavaScript ES6 (جاوا اسکریپت)
• چهار روش برای حذف مقادیر آرایه در جاوا اسکریپت — به زبان ساده
• جاوا اسکریپت چیست؟ — به زبان ساده

==