فرادرس
انواع ساختمان داده مقدماتی در تایپ اسکریپت — راهنمای جامع
ساختمان‌های داده جزء مباحث پیچیده‌ای هستند که هر برنامهنویسی در مسیر تبدیل شدن به یک توسعه‌دهنده نرم‌افزار در سطح بین‌المللی باید بر آنها تسلط یابد. متاسفانه اغلب برنامه‌نویسان وب مهارت چندانی در این زمینه ندارند. در این راهنما با روش نوشتن سه ساختمان داده مقدماتی در تایپ اسکریپت آشنا خواهیم شد. این سه ساختمان داده شامل لیست‌های پیوندی، پشته و صف جزء مواردی هستند که هر کس یک دوره درسی علوم رایانه طی کرده باشد، با آنها مواجه شده است.
تایپ اسکریپت به ما امکان می‌دهد که ساختمان‌های داده را به شکلی که عموماً در زبان‌های شیءگرا مانند ++C، جاوا و #C استفاده می‌شوند بسازیم. این شکل‌ها مشهور هستند، به خوبی مستند شده‌اند و در هر کتاب درسی یا وب سایت مربوط به ساختمان داده می‌توان آنها را یافت.
پیش‌نیازها
برای مطالعه این راهنما به یک کد ادیتور مانند ویژوال استودیو کد نیاز دارید. همچنین باید Node.js و Git را روی سیستم خود نصب کرده و با مبانی ابتدایی تایپ اسکریپت آشنا باشید.
راه‌اندازی
کد آغازین در این ریپوی گیت‌هاب (+) قرار دارد. کد کامل این راهنما را نیز می‌توانید در این ریپو (+) ببینید. یک پنجره ترمینال را باز کنید و دستورهای زیر را وارد نمایید تا کد آغازین را دریافت کرده و اجرا کنید:
git clone git@github.com:richarddprasad/ts-data-struct-starter.git cd ts-data-struct-starter npm install npm start (after a few seconds) Ctrl+C npm start
npm اسکریپت‌های start:dev و build:dev را به صورت موازی اجرا می‌کند. این دو را می‌توانید در فایل package.json ببینید. نخستین باری که دستور npm start را اجرا کنید، کد هنوز به طور کامل بیلد نشده است و از کار خواهد افتاد. به همین جهت باید آن را kill کرده و ری‌استارت کنیم. خروجی ترمینال باید مانند زیر باشد:
می‌توانیم خطاهایی که از src/queue/queue_examples.ts می‌آیند را نادیده بگیریم. این خطاها زمانی که نخستین ساختمان داده خود را پیاده‌سازی کنیم رفع می‌شوند.
مبانی ساختمان داده
ساختمان‌های داده به طور کلی در مورد سازماندهی کلکسیون‌هایی از داده‌ها به روش خاصی هستند. این سازماندهی بر مبنای شیوه حذف و اضافه داده‌ها تعریف می‌شود. می‌توانی صدها نوع ساختمان داده مختلف را تعریف کرد، اما انواع خاصی از آنها وجود دارند که بخشی اساسی از توسعه نرم افزار محسوب می‌شوند و این موارد شامل لیست‌های پیوندی، پشته‌ها، صف‌ها، صف‌های اولویت، جداول هش و درخت‌های دودویی هستند.
لیست‌های پیوندی، پشته‌ها و صف‌ها جزء ضروری‌ترین موارد این ساختمان‌های داده‌ای هستند.
عملیات مقدماتی
ساختمان‌های داده بر حسب شیوه سازماندهی داده‌ها با هم تفاوت پیدا می‌کنند. ما با ارائه مجموعه‌ی از متدهای خاص، قواعدی برای این سیستم سازماندهی تعیین می‌کنیم.
- یک متد insert برای درج یک آیتم در ساختمان داده.
- یک متد remove برای حذف یک آیتم.
- یک متد isEmpty برای تست این که آیا آیتمی وجود دارد یا نه.
این‌ها نام‌های ژنریک هستند. به طور معمول یک ساختمان داده خاص یک نام مخصوص برای یک عملیات معین دارد. برخی ساختمان‌های داده متدهای دیگری نیز دارند که مختص خودشان است.
صف
صف نخستین ساختمان داده‌ای است که در این راهنما پیاده‌سازی خواهیم کرد. صف به عنوان یک ساختمان داده «اولین ورودی-اولین خروجی» (FIFO) شناخته می‌شود و آن را می‌توان به صورت زیر نشان داد:
اصطلاح‌های صف
ابتدای صف به نام front و انتهای آن به نام rear شناخته می‌شود. نخستین عنصر (آیتم داده‌ای) که در صف درج شود، نخستین موردی است که حذف خواهد شد. آخرین عنصری که در صف درج شود، آخرین عنصری خواهد بود که از صف حذف می‌شود. همه عناصر بعدی که در صف درج شوند در rear قرار می‌گیرند.
عملیات صف
صف برخی عملیات ساده با نام‌های زیر را پیاده‌سازی می‌کند:
- Enqueuer: یک عنصر در عقب (rear) صف درج می‌کند. این عنصر به rear جدید تبدیل می‌شود.
- Dequeuer: یک عنصر در front صف درج می‌کند. عنصر بعدی به front جدید تبدیل می‌شود.
- isEmpty: بررسی می‌کند آیا صف شامل هیچ عنصری است یا نه.
در تصویر زیر یک بصری‌سازی ساده از عملیات مرتبط با صف را می‌بینید:
عملیات dequeuer روی front صف تأثیر می‌گذارد در حالی که عملیات enqueuer روی rear صف اجرا می‌شود.
به عنوان یک نمونه از صف در دنیای واقعی می‌توان به صف نانوایی اشاره کرد. نخستین کسی که در صف قرار می‌گیرد، نخستین کسی است که نان می‌گیرد و آخرین کسی که وارد صف شود، آخرین نفری خواهد بود که نان می‌خرد. بدین ترتیب خرید نان از نانوایی به لطف وجود صف به فرایندی منظم و کارآمد تبدیل می‌شود.
سیستم‌های عامل از صف‌ها برای ردگیری هر کاراکتر که روی کیبورد تایپ می‌کنید استفاده می‌کنند. یک سرور شبکه می‌تواند درخواست‌های کلاینت را در یک صف ذخیره کند و به هر یک از آنها به همان ترتیبی که وارد می‌شوند پاسخ دهد.
یک عملیات اضافی رایج دیگر صف peek نام دارد که البته می‌تواند نام‌های دیگری نیز داشته باشد.
4. peek: عنصری که در front صف قرار دارد را بدون این که حذف کند، بازیابی می‌کند.
صف ما یک پیاده‌سازی مبتنی بر آرایه است، یعنی اندازه محدودی دارد. امکان ایجاد یک پیاده‌سازی مبتنی بر لیست نیز وجود دارد که این کار را در مورد پیاده‌سازی لیست پیوندی در ادامه انجام خواهیم داد. از آنجا که صف اندازه محدودی دارد، می‌توانیم بررسی کنیم آیا پر شده یا نه.
5. isFull: بررسی می‌کند آیا صف به بیشینه تعداد آیتم‌هایی که می‌تواند نگهداری کند رسیده است یا نه.
همچنین می‌توانیم یک متد size نیز اضافه کنیم که تعداد عناصر هم اینک موجود در صف را بازیابی می‌کند. ما آن را برای صف خود پیاده‌سازی نمی‌کنیم، اما شما می‌توانید به عنوان یک تمرین این کار را انجام دهید. این کار به سادگی بازگشت دادن مقدار مشخصه length است.
پیاده‌سازی صف
پروژه را درون ویژوال استودیو کد باز کنید، سپس فایل src/queue/queue.ts را که شامل کد زیر است، باز کنید:
export class Queue {
// private queue: [];
private length: number; // number of elements currently in the queue
private readonly maxSize: number; // maximum number of elements queue can contain
public constructor(maxSize: number) {
// Make sure maxSize is at least 1
this.maxSize = maxSize > 0 ? maxSize : 10;
this.length = 0;
}
public isEmpty() {
}
public isFull() {
}
public enqueue() {
}
public dequeue() {
}
public peek() {
}
public queueContents(): void {
}
}
مشخصه queue در حال حاضر کامنت شده است. این مشکل را در ادامه رفع می‌کنیم، اما ابتدا باید کمی از مسیر منحرف شده و یک ویژگی تایپ اسکریپت به نام generics را بررسی کنیم.
بررسی مختصر ژنریک
صف ما به ذخیره‌سازی کلکسیونی از عناصر می‌پردازد. ما این عناصر را در یک آرایه (queue) ذخیره می‌کنیم. بیشترین تعداد عناصری که آرایه می‌تواند نگهداری کند را تعیین می‌کنیم و به ردگیری تعداد عناصری هم اینک در صف وجود دارد (length) می‌پردازیم.
آرایه‌های جاوا اسکریپت می‌توانند عناصری با انواع مخلوط را نگهداری کنند، اما تنها دلیل این امر آن است که آرایه‌های جاوا اسکریپت آرایه‌های معمولی نیستند، بلکه اشیای خاصی هستند که برای تقلید کارکرد یک آرایه طراحی شده‌اند. در واقع جاوا اسکریپت ابزاری برای ساخت آرایه با ماهیت متعارف ندارد. اگر علاقه‌مند هستید در این مورد اطلاعات بیشتری کسب کنید، پیشنهاد می‌کنیم این مطلب (+) را مطالعه کنید.
در زبان‌هایی که ساختمان داده آرایه واقعی وجود دارد، آرایه‌ها می‌توانند تنها عناصری از یک نوع منفرد را نگهداری کنند. ما این وضعیت را با تعیین یک نوع برای queue در جاوا اسکریپت ایجاد می‌کنیم. ما می‌توانیم انواع مختلفی مانند number یا string ایجاد کنیم. اما امکان تعیین مجموعه‌ای از انواع با استفاده از نوع union به صورت number | string | Boolean نیز وجود دارد. متاسفانه تعداد انواع بسیار زیادی است و از این رو استفاده از نوع union عملی نیست.
خوشبختانه تایپ اسکریپت این امکان را به ما داده است که از یک نوع متغیر استفاده کنیم که بعدتر مشخص می‌شود. این کار با استفاده از ژنریک انجام می‌یابد و به صورت زیر پیاده‌سازی می‌شود:
export class Queue<T> {
private queue: T[];
private length: number; // number of elements currently in the queue
private readonly maxSize: number; // maximum number of elements queue can contain
public constructor(maxSize: number) {
// Make sure maxSize is at least 1
this.maxSize = maxSize > 0 ? maxSize : 10;
this.length = 0;
this.queue = new Array<T>(this.maxSize);
}
...
}
در کد فوق تعیین می‌کنیم که کلاس یک پارامتر ژنریک می‌پذیرد: <class Queue<T. استفاده از T به عنوان نام پارامتر یک سنت رایج است. اینک آرایه queue ما یک آرایه از نوع T است. درون سازنده یک آرایه queue مقداردهی می‌کنیم که یک آرایه جدید جاوا اسکریپت از نوع T خواهد بود:
this.queue = new Array<T>(this.maxSize);
بازگشت به صف
در این بخش هر یک از عملیات مقدماتی که قبلاً اشاره کردیم را یک به یک پیاده‌سازی می‌کنیم. آنها را به ترتیب از آسان به دشوار پیاده‌سازی خواهیم کرد.
1. isEmpty
این عملیات در صورتی که length برابر با صفر باشد، مقدار true و در غیر این صورت مقدار false بازمی‌گرداند.
public isEmpty(): boolean {
return this.length === 0;
}
2. isFull
این عملیات در صورتی که length برابر با maxSize باشد، مقدار true و در غیر این صورت مقدار false بازمی‌گرداند.
public isFull(): boolean {
return this.length === this.maxSize;
}
3. Peek
این عملیات عنصر front را بدون حذف کردن بازگشت می‌دهد و در صورتی که صف خالی باشد یک استثنا ایجاد می‌کند:
public peek(): T {
if (this.isEmpty()) {
throw new Error('Queue is empty');
}
return this.queue[0];
}
4. enqueuer
در صورتی که فضا وجود داشته باشد، عنصری را در rear درج می‌کند. اگر تلاش کنید در یک صفِ پُر عنصری را درج کنیم، با خطای queue overflow مواجه خواهیم شد.
public enqueue(newItem: T): void {
if (this.isFull()) {
throw new Error('Queue overflow');
} else {
this.queue[this.length++] = newItem; // post-increment adds 1 to length after insertion
}
}
}
5. dequeuer
در این عملیات عنصر front حذف شده و بازگشت می‌یابد. این عملیات کمی چالش‌برانگیز است، زیرا باید همه عناصر درون صف را شیفت کنیم. اگر تلاش کنیم از یک صف خالی عنصری را حذف کنیم، موجب بروز خطای queue underflow خواهیم شد:
public dequeue(): T {
if (this.isEmpty()) {
throw new Error('Queue underflow');
}
const retval = this.queue[0];
for (let i = 0; i < this.length; i++) {
this.queue[i] = this.queue[i + 1];
}
this.length--; // we need to decrease length by 1
return retval;
}
حذف کردن یک عنصر از یک صف عملیاتی زمان‌بر است، زیرا باید همه چیز را جابجا کنیم. با این حال این حالت تنها در مورد صف‌های مبتنی بر آرایه مانند این صدق می‌کند. در ادامه یک صف مبتنی بر لیست پیاده‌سازی خواهیم کرد که این مشکل عملکردی را ندارد.
6. queueContents
این عملیات به طور رسمی بخشی از پیاده‌سازی صف است، اما می‌تواند برای مقاصد دیباگ نیز مفید باشد. این عملیات محتوای صف را پرینت می‌کند.
public queueContents(): void {
console.log('Queue Contents');
for (let i = 0; i < this.length; ++i) {
console.log(`queue[${i}]: ${this.queue[i]}`);
}
}
پیاده‌سازی کامل صف به صورت زیر است:
export class Queue<T> {
private queue: T[];
private length: number; // number of elements currently in the queue
private readonly maxSize: number; // maximum number of elements queue can contain
public constructor(maxSize: number) {
// Make sure maxSize is at least 1
this.maxSize = maxSize > 0 ? maxSize : 10;
this.length = 0;
this.queue = new Array<T>(this.maxSize);
}
public isEmpty(): boolean {
return this.length === 0;
}
public isFull(): boolean {
return this.length === this.maxSize;
}
public enqueue(newItem: T): void {
if (this.isFull()) {
throw new Error('Queue overflow');
} else {
this.queue[this.length++] = newItem; // post-increment adds 1 to length after insertion
}
}
public dequeue(): T {
if (this.isEmpty()) {
throw new Error('Queue underflow');
}
const retval = this.queue[0];
for (let i = 0; i < this.length; i++) {
this.queue[i] = this.queue[i + 1];
}
this.length--; // we need to decrease length by 1
return retval;
}
public peek(): T {
if (this.isEmpty()) {
throw new Error('Queue is empty');
}
return this.queue[0];
}
public queueContents(): void {
console.log('Queue Contents');
for (let i = 0; i < this.length; ++i) {
console.log(`queue[${i}]: ${this.queue[i]}`);
}
}
}
ایجاد صف
در این بخش به بررسی شیوه ایجاد صف برای نگهداری انواع مختلفی از عناصر می‌پردازیم. در ادامه نمونه‌ای از ایجاد صف اعداد را می‌بینید:
const numberQueue = new Queue<number>(100);
کد فوق یک صف ایجاد می‌کند که امکان نگهداری 100 عدد را دارد. همچنین می‌توانیم صفی از رشته‌ها بسازیم:
const stringQueue = new Queue<string>(50);
این کد صفی ایجاد می‌کند که 50 رشته را نگه می‌دارد. ما محدود به انواع داخلی جاوا اسکریپت نیستیم. در ادامه با شیوه ایجاد صفی از مشتریان آشنا می‌شوید:
interface Customer {
name: string;
age: number;
isMember: boolean; // many large grocery store chains have membership programs
rewardsCard?: string;
}
// A checkout lane with 10 customers
const checkoutLine = new Queue<Customer>(10);
در ادامه صفی از اعداد با بیشینه اندازه 100 می‌سازیم. این صف را تا انتها پر می‌کنیم تا دیگر نتوان عدد دیگری در آن درج کرد و سپس آن را تجزیه می‌کنیم:
// Create a number queue capable of storing 100 numbers
const nq = new Queue<number>(100);
// Fill the queue up with random numbers
while(!nq.isFull()) {
nq.enqueue(Math.floor(Math.random() * 1000));
}
nq.queueContents();
// Empty out the queue
while(!nq.isEmpty()) {
console.log(`${nq.dequeue()}`);
}
nq.queueContents();
این مثال‌ها در فایل پروژه src/queue/queue_examples.ts ارائه شده‌اند. می‌توانید کامنت خط زیر را در فایل index.ts بردارید تا کد اجرا شود:
import ‘./queue/quest_examples’;
اجرای تست‌ها
پیش از آن که به بخش بعدی برویم، باید اشاره کنیم که تست‌هایی نیز برای هر ساختمان داده ارائه شده است. اگر با تست unit آشنا باشید، می‌توانید مجموعه تست‌ها را اجرا کرده و تست‌های خود را نیز اضافه کنید. یک پنجره ثانویه ترمینال یا زبانه جدیدی را باز کنید و دستور زیر را برای اجرای مجموعه‌های تست وارد نمایید:
npx jest
پشته
پشته نیز مشابه صف است به جز این که عناصر مختلف به جای این که از دو انتهای مختلف ساختمان داده درج و حذف شوند، از مکان یکسانی اضافه و حذف می‌شوند. پشته یک ساختمان داده از نوع «آخرین ورودی-اولین خروجی» (LIFO) است.
پشته می‌تواند نقش مهمی در کارکرد داخلی سیستم‌های عامل و موتورهای جاوا اسکریپت ایفا کند. برای نمونه پشته برای ردگیری فراخوانی‌های تابع مورد استفاده قرار می‌گیرد.
تابع‌های بازگشتی که به یک حالت مبنا resolve نمی‌شوند، می‌توانند موجب بزرگ‌تر شدن پشته شوند تا این که به محدودیت اندازه‌اش برسد و موجب بروز خطای از کار افتادن پشته به صورت «سرریز پشته» (stack overflow) شود.
اصطلاح‌ها و عملیات پشته
آن انتهایی که عناصر را در پشته درج و حذف می‌کنیم، به نام top پشته نامیده می‌شود. پشته عملیات ابتدایی با نام‌های زیر را پیاده‌سازی می‌کند:
- push برای درج.
- pop برای حذف.
- top برای بازیابی عنصر top بدون حذف کردن آن.
پشته نیز در صورتی که مبتنی بر آرایه باشد، یک متد isEmpty و همچنین یک متد isFull دارد. پشته را می‌توان به صورت زیر بصری‌سازی کرد:
پیاده‌سازی پشته
فایل src/stack/stack.ts را باز کنید. چارچوب کد زیر را مشاهده می‌کنید:
export class Stack<T> {
private stack: T[];
private length: number;
private readonly maxSize: number;
public constructor(maxSize: number) {
this.length = 0;
this.maxSize = maxSize;
this.stack = new Array<T>(this.maxSize);
}
public isEmpty(): boolean {
return this.length === 0;
}
public isFull(): boolean {
return this.length === this.maxSize;
}
public push(newItem: T): void {
throw new Error('Implementation not provided');
}
public pop(): T {
throw new Error('Implementation not provided');
}
public top(): T {
throw new Error('Implementation not provided');
}
public stackContents(): void {
console.log('Stack Contents');
for (let i = 0; i < this.length; ++i) {
console.log(`stack[${i}]: ${this.stack[i]}`);
}
}
}
کافی است متدهای push، pop و top را پیاده‌سازی کنیم. پیاده‌سازی برای متدهای دیگر نیز از قبل ارائه شده است. پیاده‌سازی پشته ساده‌تر از صف است، زیرا نیازی به جابجایی همه عناصر در زمان حذف کردن یک عنصر موجود نداریم. با این حال، باید به موقعیت اندیس آرایه که با مشخصه length آرایه نمایش می‌یابد توجه دقیقی بکنیم.
1. push
یک عنصر به ابتدای پشته اضافه می‌کند.
public push(newItem: T): void {
if (this.isFull()) {
throw new Error('Stack overflow');
}
this.stack[this.length++] = newItem;
}
اگر تلاش کنیم به یک پشته که پر است، push کنیم، یک خطای stack overflow دریافت می‌کنیم. به شیوه استفاده از عملگر post-increment روی مشخصه length توجه کنید.
2. pop
این عملیات عنصری را از ابتدای پشته حذف می‌کند.
public pop(): T {
if (this.isEmpty()) {
throw new Error('Stack underflow');
}
const retval = this.stack[--this.length];
return retval;
}
اگر از پشته خالی pop کنیم، یک خطای stack underflow دریافت می‌کنیم. به شیوه استفاده از عملگر pre-decrement روی مشخصه length توجه کنید.
3. top
عنصر ابتدای پشته را بدون حذف کردن آن بازیابی می‌کند.
public top(): T {
if (this.isEmpty()) {
throw new Error('Stack is empty');
}
return this.stack[this.length - 1];
}
به این که ابتدای پشته در length منهای یک است توجه کنید.
یک مثال مختصر از پشته
فایل src/test/stack.test.ts را باز کنید. در نزدیکی انتهای پشته، کد موجود برای معکوس کردن رشته با استفاده از پشته را مشاهده می‌کنید:
describe('reverse a string using a stack', () => {
const text = 'Hello, World!';
// Create a stack large enough to hold our text
const stack = new Stack<string>(text.length);
test('text is reversed', () => {
// Add each character from the text to the stack
text.split('').forEach(c => stack.push(c));
let reversed: string[] = [];
// Remove each character from the stack until the stack is empty
while (!stack.isEmpty()) {
reversed = reversed.concat(stack.pop());
}
// Run our test
expect(reversed.join('')).toBe('!dlroW ,olleH');
});
});
لیست‌های پیوندی
یک آرایه سنتی غیر جاوا اسکریپتی دارای اندازه ثابت است و نمی‌تواند بزرگ‌تر یا کوچک‌تر شود. تنها روش برای تغییر اندازه یک آرایه، ایجاد یک آرایه جدید با اندازه مطلوب و کپی کردن محتوای آرایه قدیمی به آرایه جدید است. برای درک دلیل این وضعیت باید با شیوه تخصیص حافظه آشنا باشیم که فراتر از حوصله این مقاله است.
لیست‌های پیوندی جایگزینی برای آرایه‌ها هستند و مزیت اصلی آنها نسبت به آرایه‌ها این است که می‌توانند به سادگی بزرگ‌تر یا کوچک‌تر شوند. تنها عیب آن این است که لیست‌های پیوندی از نظر دسترسی به داده‌ها کندتر از آرایه‌ها هستند. موقعیت هر عنصر مفروض در یک آرایه را می‌توان به سادگی به صورت زیر محاسبه کرد:
عناصر در یک لیست پیوندی به صورت یک بلوک مجاور در حافظه قرار دارند، اما در سراسر آن توزیع یافته‌اند. در ادامه چگونگی این وضعیت را بررسی می‌کنیم، اما نکته اصلی که باید به خاطر داشته باشید این است که موقعیت یک عنصر در لیست پیوندی را نمی‌توانیم محاسبه کنیم. بنابراین باید کل لیست را پیمایش کنیم تا این که به دنبال عنصری که مد نظرمان است بگردیم و در بدترین حالت ممکن است عنصری که به دنبالش هستیم در انتهای لیست پیوندی قرار داشته باشد.
پوشش داده
پیش از آن که یک لیست پیوندی را پیاده‌سازی کنیم، باید یک کلاس برای پوشش داده‌ها ایجاد کنیم. این کلاس به طور معمول به نام Node شناخته می‌شود و علاوه بر نگهداری داده‌ها شامل ارجاعی به Node دیگر نیز است. فایل src/linked_list/node.ts را باز کرده و محتوای آن را بررسی کنید:
// DS = Data Structure
export namespace DS {
export class Node<T> {
public item: T | null;
public next: Node<T> | null;
public constructor(item: T | null = null) {
this.item = item;
this.next = null;
}
}
}
در ادامه به توضیح کد فوق می‌پردازیم:
- کلاس Node را درون یک فضای نام به نام DS قرار می‌دهیم. یک شیء Node از قبل در دامنه سراسری قرار دارد، از این رو باید Node خود را در یک فضای نام مجزا قرار دهیم تا تداخلی ایجاد نشود.
- کلاس Node ما یک پارامتر ژنریک از نوع T می‌پذیرد.
- مشخصه item داده‌های ما را نگهداری می‌کند. درصورتی که هیچ آرگومانی ارائه نشده باشد، سازنده یک مقدار پیش فرض null ارائه می‌کند. این کار صرفاً به منظور سهولت کار است.
- مشخصه next یک Node را به دیگری لینک می‌کند.
- هر دو مشخصه‌های item و next به صورت public هستند. به طور معمول مشخصه‌های درون یک کلاس به صورت private یا protected هستند و getters و setters امکان دسترسی به این مشخصه‌ها را فراهم می‌سازند. در این بخش یک استثنا ایجاد می‌کنیم. یک لیست پیوندی می‌تواند میلیون‌ها گره داشته باشد و سربار استفاده از getters و setters بسیار زیاد خواهد بود. بهتر است به این مشخصه‌ها مستقیماً دسترسی پیدا کنیم تا شاهد بهبود عملکرد باشیم.
- item و next می‌توانند null نیز باشند. می‌توانیم از undefined نیز به جای null استفاده کنیم. در ادامه دلیل این که در زمان پیاده‌سازی لیست پیوندی به مقادیر null یا undefined نیز اجازه وجود می‌دهیم را توضیح خواهیم داد.
اصطلاح‌ها و عملیات لیست پیوندی
لیست پیوندی را می‌توان به روش‌های مختلفی پیاده‌سازی کرد. برای نمونه می‌توان آن را به روش تک پیوندی که ما عمل می‌کنیم پیاده‌سازی کرد. همچنین می‌توان آن را به صورت دو پیوندی پیاده‌سازی کرد که معنی آن این است علاوه بر اشاره‌گر next یک اشاره‌گر prev نیز خواهیم داشت.
ما از نسخه‌ای می‌خواهیم استفاده کنیم که از گره‌های مرده یا قراول (sentinel) برای نشان دادن ابتدا و انتهای لیست استفاده می‌کند. گره‌های قراول به ما امکان می‌دهند که کد کمتری برای مدیریت درج و حذف عناصر از لیست بنویسیم.
ابتدای لیست به نام سر (head) و انتهای آن به نام دم (tail) خوانده می‌شود. یک لیست پیوندی خالی شامل دو گره قراول به نام‌های سر و دم است که گره سر به گره دم لیست اشاره می‌کند.
لیست پیوندی عملیات insert و remove را پیاده‌سازی می‌کند، اما چندین گزینه برای این دو عملیات می‌توان پیاده‌سازی کرد. می‌توان بیش از یک پیاده‌سازی برای هر یک ارائه کرد و ما نیز چنین خواهیم کرد.
لیست پیوندی ما شامل متدهای زیر خواهد بود:
- insertFirst – عنصری را در ابتدای لیست درج می‌کند.
- insertLast – عنصری را در انتهای لیست درج می‌کند.
- removeFirst – عنصری را از ابتدای لیست حذف می‌کند.
- Remove – عنصری را با کلید مفروض حذف می‌کند.
- Contains – بررسی می‌کند آیا عنصری با کلید مفروض در لیست موجود است یا نه.
- isEmpty – بررسی می‌کند آیا لیست شامل هیچ گرهی به جز سر و دم است یا نه.
- getFirst – نخستین عنصر لیست را بدون حذف کردن آن بازیابی می‌کند.
پیاده‌سازی‌های لیست پیوندی بر حسب عملیات مقدماتی که ارائه می‌کند و همچنین نام این عملیات می‌تواند متفاوت باشد. برای نمونه remove گاهی اوقات به نام delete نامیده می‌شود. دلیل این که برخی از این متدهای خاص را انتخاب کرده‌ایم در ادامه روشن‌تر خواهد شد.
پیاده‌سازی لیست پیوندی
فایل src/linked_list/linked_list.ts را باز کنید. به چارچوب کد ارائه شده نگاه کنید. یک متد به نام listContents برای کمک به دیباگ کردن ارائه شده است.
import { DS } from './node';
export class LinkedList<T> {
private head: DS.Node<T>;
private tail: DS.Node<T>;
constructor() {
this.head = new DS.Node<T>();
this.tail = new DS.Node<T>();
this.head.next = this.tail;
}
public isEmpty(): boolean {
throw new Error('Method not implemented');
}
public insertFirst(item: T): void {
throw new Error('Method not implemented');
}
public insertLast(item: T): void {
}
public removeFirst(): T | null {
throw new Error('Method not implemented');
}
public remove(searchKey: T): T | null {
throw new Error('Method not implemented');
}
public contains(searchItem: T): boolean {
throw new Error('Method not implemented');
}
public getFirst(): T | null {
throw new Error('Method not implemented');
}
public listContents(): void {
let cur = this.head.next;
while (cur && cur !== this.tail) {
console.log(`${cur.item}`);
cur = cur.next;
}
}
}
لیست پیوندی ما تنها شامل دو مشخصه است که گره‌های قراول head و tail هستند. سازنده روابط زیر را تنظیم می‌کند:
گره‌های قراول ما هرگز هیچ داده‌ای را نگهداری نمی‌کنند، به همین جهت است که به مشخصه item اجازه داده‌ایم که null باشد.
گره دم (tail) به گره دیگری اشاره نمی‌کند، از این رو اجازه می‌دهیم که مشخصه next نیز null باشد. می‌توانیم کاری کنیم که گره دم به گره سر اشاره کند و به این ترتیب یک لیست مدور ایجاد کنیم. در ادامه عملیات دیگر را پیاده‌سازی می‌کنیم.
1. isEmpty
درصورتی که head.next به tail اشاره کند مقدار true بازگشت می‌دهد:
public isEmpty(): boolean {
return this.head.next === this.tail;
}
2. insertFirst
یک گره جدید به ابتدای لیست اضافه می‌کند:
public insertFirst(item: T): void {
// Encapsulate our item into a Node object
const newNode = new DS.Node<T>(item);
newNode.next = this.head.next;
this.head.next = newNode;
}
رسم نمودار حالت لیست پیوندی موجب می‌شود که با سادگی بیشتری کارهایی که باید انجام دهیم را مشاهده کنیم:
3. getFirst
نخستین عنصر را بدون حذف کردن آن بازیابی می‌کند:
public getFirst(): T | null {
if (this.isEmpty()) {
throw new Error('List is empty');
}
return this.head.next ? this.head.next.item : null;
}
در یک لیست غیر تهی، this.head.next هرگز نمی‌تواند null باشد. با این حال تایپ اسکریپت این را نمی‌داند و از این رو باید برخی منطق شرطی در گزاره بازگشتی خود وارد کنیم. آخرین متدی که پیاده‌سازی می‌کنیم remove است. راه حل‌های متدهای دیگر نیز ارائه شده‌اند.
4. Remove
یک گره را در کلید مفروض حذف می‌کند:
public remove(searchKey: T): T | null {
if (this.isEmpty()) {
throw new Error('List is empty');
}
// rv = retval or return value
let rv: DS.Node<T> | null = null;
// cur = current
let cur: DS.Node<T> = this.head;
// Advance our cur pointer to the node right before our matching node
while (cur.next && cur.next.item !== searchKey) {
cur = cur.next;
}
if (cur.next) {
rv = cur.next;
cur.next = cur.next.next;
rv.next = null;
}
return rv && rv.item ? rv.item : null;
}
برای حذف یک گره خاص باید از یک گره ثالث cur کمک بگیریم.
کد کامل لیست پیوندی با راه‌حل‌های متدهای باقیمانده به صورت زیر است:
import { DS } from './node';
export class LinkedList<T> {
private head: DS.Node<T>;
private tail: DS.Node<T>;
constructor() {
this.head = new DS.Node<T>();
this.tail = new DS.Node<T>();
this.head.next = this.tail;
}
public isEmpty(): boolean {
return this.head.next === this.tail;
}
public insertFirst(item: T): void {
// Encapsulate our item into a Node object
const newNode = new DS.Node<T>(item);
newNode.next = this.head.next;
this.head.next = newNode;
}
public insertLast(item: T): void {
const newNode = new DS.Node<T>(item);
let cur: DS.Node<T> | null = this.head;
// Advance our cur pointer to just before the tail node
while (cur && cur.next !== this.tail) {
cur = cur.next;
}
if (cur) {
newNode.next = this.tail;
cur.next = newNode;
}
}
public removeFirst(): T | null {
if (this.isEmpty()) {
throw new Error('List is empty');
}
let rv: DS.Node<T> | null = this.head.next;
if (rv) {
this.head.next = rv.next;
rv.next = null;
}
// We are returning the data, not the node itself
return rv ? rv.item : null;
}
public remove(searchKey: T): T | null {
if (this.isEmpty()) {
throw new Error('List is empty');
}
// rv = retval or return value
let rv: DS.Node<T> | null = null;
// cur = current
let cur: DS.Node<T> = this.head;
// Advance our cur pointer to the node right before our matching node
while (cur.next && cur.next.item !== searchKey) {
cur = cur.next;
}
if (cur.next) {
rv = cur.next;
cur.next = cur.next.next;
rv.next = null;
}
return rv && rv.item ? rv.item : null;
}
public contains(searchItem: T): boolean {
if (this.isEmpty()) {
throw new Error('List is empty');
}
let rv: boolean = false;
let cur: DS.Node<T> | null = this.head;
// Traverse the list in search of a matching item
while (cur && cur.next !== this.tail) {
if (cur.next && cur.next.item === searchItem) {
rv = true;
break;
}
cur = cur.next;
}
return rv;
}
public getFirst(): T | null {
if (this.isEmpty()) {
throw new Error('List is empty');
}
return this.head.next ? this.head.next.item : null;
}
public listContents(): void {
let cur = this.head.next;
while (cur && cur !== this.tail) {
console.log(`${cur.item}`);
cur = cur.next;
}
}
}
به عنوان تمرین می‌توانید تلاش کنید راه‌حل‌های خود را پیاده‌سازی کنید.
صف و پشته مبتنی بر لیست
همچنان که پیشتر اشاره کردیم، ما انتخاب کرده‌ایم که لیست پیوندی را با یک کلکسیون خاصی از متدها بسازیم. از سوی دیگر می‌توانیم صف و پشته‌ها را از لیست پیوندی بسازیم و متدهایی که انتخاب کردیم امکان انجام این کار را به سهولت فراهم می‌سازند. کد زیر را مطالعه کنید و ببینید آیا می‌توانید طرز کار آن را درک کنید.
صف مبتنی بر لیست
import { LinkedList } from '../linked_list/linked_list';
export class QueueList<T> {
private list: LinkedList<T>;
public constructor() {
this.list = new LinkedList<T>();
}
public isEmpty(): boolean {
return this.list.isEmpty();
}
public enqueue(item: T): void {
this.list.insertLast(item);
}
public dequeue(): T | null {
return this.list.removeFirst();
}
public peek(): T | null {
return this.list.getFirst();
}
public queueContents(): void {
this.list.listContents();
}
}
پشته مبتنی بر صف
import { LinkedList } from '../linked_list/linked_list';
export class StackList<T> {
private list: LinkedList<T>;
public constructor() {
this.list = new LinkedList<T>();
}
public isEmpty(): boolean {
return this.list.isEmpty();
}
public push(item: T): void {
this.list.insertFirst(item);
}
public pop(): T | null {
return this.list.removeFirst();
}
public top(): T | null {
return this.list.getFirst();
}
public stackContents(): void {
this.list.listContents();
}
}
در کدهای فوق دیدیم که دیگر به متد isFull برای هیچ کدام از ساختمان‌های داده نیاز نداریم. پشته‌ها و صف‌های مبتنی بر لیست می‌توانند تا اندازه نامحدودی افزایش یابند. صف ما دیگر محبور به جابجا کردن همه عناصر پس از عملیات dequeuer نیست، اما در یک عملیات enqueuer باید همه لیست را تا انتها پیمایش کنیم تا یک عنصر حدید را درج کنیم. ما می‌توانستیم پشته و صف خود را با استفاده از شیء Array داخلی جاوا اسکریپت نیز پیاده‌سازی کنیم.
لیست پیوندی ما یک بازسازی جزئی از شیء Array داخلی جاوا اسکریپت محسوب می‌شود. البته این بدان معنی نیست که آرایه‌های جاوا اسکریپت در عمل با استفاده از لیست پیوندی پیاده‌سازی شده‌اند. پیاده‌سازی زیرین ممکن است بسته به هر موتور متفاوت باشد.
سخن پایانی
امیدواریم این راهنما برای شما مفید و اگاهی بخش بوده باشد. اگر می‌خواهید در مورد ساختمان‌های داده اطلاعات بیشتری کسب کنید، پیشنهاد می‌کنیم مطالبی که در ادامه آمده است را نیز مطالعه کنید:
- مجموعه آموزش‌های برنامهنویسی
- مجموعه آموزش ساختمان داده و طراحی الگوریتم
- مجموعه آموزش‌های JavaScript (جاوا اسکریپت)
- انواع پیشرفته در TypeScript — با مثال های کاربردی
- آموزش ساختمان داده — مجموعه مقالات جامع وبلاگ فرادرس
==
