علوم کامپیوتر در جاوا اسکریپت 2019: فهرست پیوندی

در سال 2009 ، خودم را به چالش کشیدم که یک پست وبلاگ در هفته برای کل سال بنویسم. من خوانده بودم که بهترین راه برای افزایش بازدیدکنندگان از وبلاگ ، ارسال مداوم مطالب است. به دلیل تمام ایده های مقاله ای که داشتم ، یک پست در هفته به عنوان یک هدف واقع بینانه به نظر می رسید ، اما معلوم شد که از 52 ایده بسیار کم دارم. من برخی از فصل های نیمه نگارش شده را مرور کردم که در نهایت به جاوا اسکریپت حرفه ای تبدیل شد و مطالب زیادی در موضوعات کلاسیک علوم کامپیوتر ، از جمله ساختار داده ها و الگوریتم ها پیدا کردم. من آن مطالب را گرفتم و در سال 2009 و (و چند مورد در 2012) به چندین پست تبدیل کردم و بازخوردهای مثبت زیادی در مورد آنها دریافت کردم.

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

لیست پیوندی چیست ؟

یک لیست پیوندی یک ساختار داده است که چندین مقدار را به صورت خطی ذخیره می کند. هر مقدار در یک لیست پیوندی در گره مخصوص به خود قرار دارد ، یک شیء حاوی داده ها به همراه پیوندی به گره بعدی در لیست. پیوند یک اشاره گر به یک گره دیگر یا null است اگر گره بعدی وجود نداشته باشد. اگر هر گره فقط یک اشاره گر به یک گره دیگر داشته باشد (بیشتر اوقات بعدی نامیده می شود) ، این لیست به عنوان یک لیست پیوندی جداگانه (یا فقط لیست پیوندی) در نظر گرفته می شود ، در حالی که اگر هر گره دارای دو پیوند (معمولاً قبلی و بعدی) باشد ، دو بار در نظر گرفته می شود. لیست پیوندی در این پست ، من بر لیست های پیوند شده متمرکز می شوم.

چرا از لیست پیوندی استفاده می شود؟

مزیت اصلی لیست های پیوندی این است که می توانند در حین استفاده از تعداد دلخواه مقادیری داشته باشند. فقط مقدار حافظه لازم برای آن مقادیر است. حفظ حافظه در رایانه های قدیمی که حافظه کمیاب بود بسیار مهم بود. در آن زمان ، یک آرایه داخلی در C از شما می خواست که تعداد آیتم های آرایه را مشخص کنید و برنامه این مقدار حافظه را ذخیره کند. حفظ حافظه به این معناست که نمی توان از آن برای بقیه برنامه یا سایر برنامه هایی که همزمان اجرا می شوند استفاده کرد ، حتی اگر حافظه هرگز پر نشده باشد. یکی از دستگاه های کم حافظه ، به راحتی می توانید حافظه موجود را با استفاده از آرایه ها تمام کنید. لیست های پیوندی برای حل این مشکل ایجاد شد.

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

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

طراحی یک لیست پیوندی

< p> مهمترین قسمت لیست پیوندی ساختار گره آن است. هر گره باید حاوی داده ها و اشاره گر به گره بعدی در لیست باشد. در اینجا یک نمایش ساده در جاوا اسکریپت وجود دارد:

 کلاس LinkedListNode {
    سازنده (داده) {
        this.data = data؛
        this.next = null؛
    }
} 

در کلاس LinkedListNode ، ویژگی داده حاوی مقداری است که مورد فهرست پیوندی باید در آن ذخیره شود و ویژگی بعدی نشانگر مورد بعدی در لیست است. ویژگی بعدی به صورت null شروع می شود زیرا هنوز گره بعدی را نمی شناسید. سپس می توانید با استفاده از کلاس LinkedListNode یک لیست پیوندی ایجاد کنید:

 //ایجاد اولین گره
const head = جدید LinkedListNode (12) ؛ 

 //اضافه کردن یک گره دوم
head.next = new LinkedListNode (99) ؛ 

 //افزودن گره سوم
head.next.next = new LinkedListNode (37) ؛ 

اولین گره در یک لیست پیوندی معمولاً head نامیده می شود ، بنابراین شناسه سر در این مثال اولین گره را نشان می دهد. گره دوم به head.next اختصاص داده می شود تا یک لیست با دو مورد ایجاد کند. گره سوم با اختصاص آن به head.next.next ، که اشاره گر بعدی گره دوم در لیست است ، اضافه می شود. اشاره گر بعدی گره سوم در لیست خالی است. تصویر زیر ساختار داده حاصله را نشان می دهد.

< p> ساختار یک لیست پیوندی به شما امکان می دهد با دنبال کردن اشاره گر بعدی در هر گره ، همه داده ها را پیمایش کنید. در اینجا یک مثال ساده از نحوه پیمایش یک لیست پیوندی و چاپ هر مقدار در کنسول وجود دارد:

 let current = head؛ 

 while (current! == null) {
    console.log (current.data) ؛
    current = current.next؛
} 

این کد از جریان متغیر به عنوان اشاره گر استفاده می کند که از طریق لیست پیوندی حرکت می کند. متغیر جاری به سر لیست راه اندازی می شود و حلقه while ادامه می یابد تا جریان تهی شود. در داخل حلقه ، مقدار ذخیره شده در گره فعلی چاپ می شود و سپس اشاره گر بعدی به گره بعدی دنبال می شود.

اکثر عملیات لیست پیوندی از این الگوریتم پیمایش یا چیزی مشابه استفاده می کنند ، بنابراین درک این الگوریتم برای درک لیست های پیوندی به طور کلی مهم است.

کلاس LinkedList

اگر در حال نوشتن یک لیست پیوندی در C بودید ، ممکن است در این مرحله متوقف شوید و کار خود را کامل بدانید (اگرچه برای نمایش هر گره از ساختار به جای کلاس استفاده کنید). با این حال ، در زبان های شی گرا مانند جاوا اسکریپت ، مرسوم است که یک کلاس ایجاد کنیم تا این قابلیت را در بر گیرد. در اینجا یک مثال ساده وجود دارد:

 const head = Symbol ("head")؛ 

 کلاس LinkedList {
    سازنده () {
        این [head] = null؛
    }
} 

کلاس LinkedList یک لیست پیوندی را نشان می دهد و شامل روش هایی برای تعامل با داده های موجود در آن خواهد بود. اینonly property یک نماد به نام head است که دارای اشاره گر به اولین گره در لیست است. از یک ویژگی نماد به جای ویژگی string استفاده می شود تا مشخص شود که این ویژگی خارج از کلاس اصلاح نمی شود.

افزودن داده های جدید به لیست

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

 const head = Symbol ("head")؛ 

 کلاس LinkedList {
    سازنده () {
        این [head] = null؛
    } 

 افزودن (داده) {
        //ایجاد یک گره جدید
        const newNode = جدید LinkedListNode (داده) ؛ 

 //مورد خاص: هنوز هیچ موردی در لیست وجود ندارد
        if (this [head] === null) {

 //فقط سر را روی گره جدید تنظیم کنید
            این [سر] = newNode؛
        } دیگر {
            //با نگاه کردن به اولین گره شروع کنید
            اجازه دهید جریان = this [head]؛ 

 //پیوندهای `next` را دنبال کنید تا به انتها برسید
            while (current.next! == null) {
                current = current.next؛
            }
            
            //گره را به اشاره گر `next` اختصاص دهید
            current.next = newNode؛
            
        }
    }
} 

متد add () یک آرگومان واحد ، هر قطعه ای از داده را می پذیرد و آن را به انتهای لیست اضافه می کند. اگر لیست خالی است (این [سر] خالی است) ، این سر را برابر با گره جدید اختصاص می دهید. اگر لیست خالی نیست ، باید لیست موجود را پیمایش کنید تا آخرین گره را پیدا کنید. پیمایش در یک حلقه while اتفاق می افتد که از این [head] شروع می شود و پیوندهای بعدی هر گره را دنبال می کند تا آخرین گره پیدا شود. گره آخر دارای ویژگی بعدی برابر null است ، بنابراین مهم استبرای متوقف کردن پیمایش در آن نقطه به جای زمانی که جریان خالی باشد (مانند بخش قبل). سپس می توانید گره جدید را به آن ویژگی بعدی اختصاص دهید تا داده ها را به لیست اضافه کنید. جاری. وقتی جریان خالی است ، به این معنی است که قبلی به آخرین مورد در لیست اشاره می کند. من آن رویکرد را بسیار منطقی نمی دانم وقتی می توانید فقط مقدار current.next را بررسی کنید و در آن نقطه از حلقه خارج شوید.

پیچیدگی متد add () O (n) است زیرا شما باید کل لیست را پیمایش کنید تا محل قرار دادن یک گره جدید را بیابید. شما می توانید این پیچیدگی را با ردیابی انتهای لیست (که معمولاً دم نامیده می شود) علاوه بر سر ، به O (1) کاهش دهید ، به این ترتیب می توانید بلافاصله یک گره جدید را در موقعیت صحیح وارد کنید.

بازیابی داده های فهرست

لیست های پیوندی اجازه دسترسی تصادفی به محتویات آن را نمی دهند ، اما همچنان می توانید با مرور فهرست و بازگشت داده ها ، داده ها را در هر موقعیت معین بازیابی کنید. برای انجام این کار ، متد get () را اضافه می کنید که یک فهرست مبتنی بر صفر را برای بازیابی می پذیرد ، مانند این:

 کلاس LinkedList {
    //روشهای دیگر پنهان برای وضوح 

 دریافت (فهرست) {
        
        //مطمئن شوید `index` یک مقدار مثبت است
        if (index> -1) {
            //اشاره گر مورد استفاده برای پیمایش
            اجازه دهید جریان = this [head]؛ 

 //برای پیگیری مکان شما در لیست استفاده شود
            اجازه دهید i = 0؛ 

 //از فهرست عبور کنید تا به انتها یا فهرست برسید
            while ((جاری! == null) && (i  
 متد get () ابتدا بررسی می کند که آیا شاخص مثبت است یا خیر ، در غیر این صورت تعریف نشده برمی گردد. متغیر i برای پیگیری میزان پیمایش در لیست استفاده می شود. خود حلقه همان پیمایش اساسی است که قبلاً مشاهده کردید با شرط افزوده شده که وقتی حلقه i با شاخص برابر باشد ، باید خارج شود. این بدان معناست که دو شرط وجود دارد که تحت آنها حلقه می تواند خارج شود: گره در موقعیت فهرست. این بررسی تضمین می کند که get () هرگز برای نمایه ای که در لیست یافت نمی شود خطایی ایجاد نمی کند (اگرچه شما می توانید تصمیم بگیرید که به جای بازگشت نامشخص خطا را خطا کنید. 
 
 پیچیدگی دریافت () روش از O (1) هنگام برداشتن اولین گره (نیازی به پیمایش نیست) تا O (n) هنگام حذف آخرین گره (پیمایش کل لیست مورد نیاز است) متغیر است. کاهش پیچیدگی کار دشواری است زیرا برای شناسایی مقدار صحیح بازگشت ، همیشه به جستجو نیاز است. 
 
 حذف داده ها از لیست پیوندی 
 
 حذف داده ها از لیست پیوندی کمی مشکل است زیرا باید اطمینان حاصل کنید که همه اشاره گرهای بعدی پس از حذف یک گره معتبر باقی می مانند. به عنوان مثال ، اگر می خواهید گره دوم را در یک لیست سه گره حذف کنید ، باید اطمینان حاصل کنید که ویژگی بعدی گره اول به جای گره دوم به گره سوم اشاره می کند. عبور از گره دوم به این ترتیب به طور موثر آن را از لیست حذف می کند. 
  < /img> 
 عملیات حذف در واقع دو عملیات است: 
  نمایه مشخص شده را پیدا کنید (الگوریتم مشابه در get ())   حذف گره در آن فهرست  
 یافتن شاخص مشخص شده مشابه روش get () است ، اما در این حلقه شما همچنین باید گره ای را که قبل از جریان آمده است ردیابی کنید زیرا باید اشاره گر بعدی گره قبلی را تغییر دهید. 
 
 همچنین چهار مورد خاص را باید در نظر گرفت: 
  لیست خالی است (امکان پیمایش وجود ندارد)   شاخص کمتر از صفر  است  فهرست بزرگتر از تعداد موارد موجود در لیست است   فهرست صفر است (حذف سر)  
 در سه مورد اول ، عملیات حذف نمی تواند تکمیل شود ، و بنابراین منطقی است که خطا را پرتاب کنیم ؛ چهارمین مورد خاص نیاز به بازنویسی این ویژگی [head] دارد. در اینجا نحوه اجرای یک روش remove () به شرح زیر است: 
 
 کلاس LinkedList {

    //روشهای دیگر برای شفافیت پنهان شده است

    حذف (فهرست) {
    
        //موارد خاص: لیست خالی یا `index` نامعتبر
        if ((this [head] === null) || (index <0)) {
            پرتاب RangeError جدید (`Index $ {index} در لیست وجود ندارد .`)؛
        }//case special: حذف اولین گره
        if (index === 0) {

            //ذخیره موقت داده ها از گره
            const data = این [head] .data؛

            //فقط سر را با گره بعدی در لیست جایگزین کنید
            این [سر] = این [سر]. بعد ؛

            //داده ها را در سر قبلی لیست بازگردانید
            بازگشت داده ها ؛
        }

        //اشاره گر برای عبور از لیست استفاده کنید
        اجازه جریان = این [سر] ؛

        //گره را قبل از جریان در حلقه پیگیری می کند
        let previous = null؛

        //برای پیگیری میزان عمیق بودن شما در لیست استفاده می شود
        بگذار i = 0 ؛

        //حلقه های مشابه در "get ()"
        while ((جاری! == null) && (i  
 روش remove () ابتدا دو مورد خاص را بررسی می کند ، یک لیست خالی (این [سر] خالی است) و نمایه ای کهکمتر از صفر است خطایی در هر دو حالت ایجاد می شود. 
 
 مورد خاص بعدی زمانی است که index 0 باشد ، به این معنی که شما سر لیست را حذف می کنید. سر لیست جدید باید دومین گره در لیست باشد ، بنابراین می توانید این [سر] را برابر این [سر]. بعدی قرار دهید. مهم نیست که فقط یک گره در لیست وجود داشته باشد زیرا این [head] در نهایت برابر با null می شود ، این بدان معناست که لیست پس از حذف خالی است. تنها نکته این است که داده ها را از سر اصلی در یک متغیر محلی ذخیره کنید ، داده ها ، تا بتوان آنها را برگرداند. 
 
 با توجه به سه مورد از چهار مورد خاص ، اکنون می توانید پیمایش مشابه با روش get (). همانطور که قبلاً ذکر شد ، این حلقه از این جهت متفاوت است که متغیر قبلی برای ردیابی گره ای که درست قبل از جریان ظاهر می شود ، استفاده می شود ، زیرا این اطلاعات برای حذف سریع یک گره ضروری است. مشابه get () ، هنگامی که حلقه جریان فعلی را خالی می کند ، نشان می دهد که شاخص پیدا نشده است. اگر این اتفاق بیفتد ، خطایی وارد می شود ، در غیر اینصورت previous.next روی current.next تنظیم می شود و به طور موثر جریان را از لیست حذف می کند. داده های ذخیره شده بر روی جریان به عنوان آخرین مرحله بازگردانده می شوند. هنگام حذف آخرین گره. مجموعه های جاوا اسکریپت داخلی مانند Array و Set به طور پیش فرض قابل تکرار هستند و می توانید با مشخص کردن یک متد Symbol.iterator generator در کلاس ، کلاس های خود را به صورت قابل تکرار انجام دهید. من ترجیح می دهم ابتدا یک متد () تولید کننده مقادیر (برای مطابقت با روش موجود در کلاسهای مجموعه داخلی) پیاده سازی کنم و سپس مقادیر فراخوانی Symbol.iterator () را مستقیماً داشته باشم. 
 
 روش مقادیر () فقط نیاز دارد یک پیمایش اساسی از لیست انجام دهید و داده هایی را که هر گره شامل آن است به دست آورید: 
 
 کلاس LinkedList {
    //روشهای دیگر برای شفافیت پنهان شده است
    
    *ارزش های(){
    
        اجازه دهید جریان = این [سر] ؛ 
 
 در حالی که (جاری! == null) {
            بازده فعلی. داده ها؛
            current = current.next؛
        }
    } 
 
 [Symbol.iterator] () {
        return this.values ​​()؛
    }
} 
 
 روش مقادیر () با یک ستاره (*) مشخص می شود تا نشان دهد که یک روش تولید کننده است. این روش با مرور بازدهی از لیست ، بازدهی را برای بازگرداندن هر قطعه داده ای که با آن مواجه می شود ، به کار می گیرد. (توجه داشته باشید که روش Symbol.iterator به عنوان ژنراتور علامت گذاری نمی شود زیرا در حال بازگشت یک تکرار کننده از مقادیر () generator method است.) 
 
 با استفاده از کلاس 
 
 پس از اتمام کار ، می توانید پیاده سازی لیست پیوندی را به این شکل استفاده کنید: 
 
 const list = new LinkedList ()؛ 
 
 list.add ("قرمز") ؛
list.add ("نارنجی") ؛
list.add ("زرد") ؛ 
 
 //دریافت کنیدمورد دوم در لیست
console.log (list.get (1))؛ //"نارنجی" 
 
 //همه موارد را چاپ کنید
for (رنگ ثابت لیست) {
    console.log (رنگ) ؛
} 
 
 //مورد دوم را از لیست حذف کنید console.log (list.remove (1)) ؛ //"نارنجی" 
 
 //اولین مورد جدید را در لیست دریافت کنید
console.log (list.get (1))؛ //"yellow" 
 
 //تبدیل به یک آرایه
const array1 = [... list.values ​​()]؛
const array2 = [... list]؛ 
 
 این پیاده سازی اساسی یک لیست پیوندی را می توان با ویژگی size گرد کرد تا تعداد گره های لیست و سایر روشهای آشنا مانند indexOf ( ) کد منبع کامل در GitHub در My Computer Science in JavaScript project موجود است. 
 
 نتیجه گیری 
 
 لیست های پیوندی چیزی نیست که هر روز از آنها استفاده کنید ، اما ساختار داده های بنیادی در علوم کامپیوتر مفهوم استفاده از گره هایی که به یکدیگر اشاره می کنند در بسیاری از ساختارهای داده دیگر استفاده می شود که در بسیاری از زبان های برنامه نویسی سطح بالاتر ساخته شده است. درک خوب نحوه عملکرد لیست های پیوندی برای درک خوب کلی از نحوه ایجاد و استفاده از سایر ساختارهای داده مهم است. 
 
 برای برنامه نویسی جاوا اسکریپت ، تقریباً همیشه بهتر است از کلاسهای مجموعه ای داخلی استفاده کنید. به عنوان آرایه به جای ایجاد خود. کلاسهای مجموعه داخلی قبلاً برای استفاده تولید بهینه شده اند و در محیط های اجرا به خوبی پشتیبانی می شوند. 
 
 این پست در ابتدا در وبلاگ Human Who Codes در 8 ژانویه 2019 ظاهر شد. اگر از این پست لذت بردید ، لطفاً برای حمایت از کار من اهدا کنید. 
                                

                                
                                    

                                        
                                            پیوندی