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

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

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

در این آموزش، موارد زیر را یاد خواهید گرفت:

درک فهرست پیوندی

انواع فهرست پیوندی

خلاصه ای از عملیات با پیچیدگی های زمانی و مکانی مربوطه خود در قالب جدول.

تفاوت بین آرایه و فهرست پیوندی

الگوریتم: حذف موارد تکراری از فهرست مرتب شده در PHP و جاوا اسکریپت را حل کنید.

درک فهرست پیوندی

head => به کادر اول فهرست اشاره می کند
tail => به آخرین کادر در فهرست اشاره می کند

برای دسترسی به داده های کادر اول

head.data => 6

برای دسترسی به داده های کادر دوم، ابتدا باید نشانگر (فلش) را طوری تنظیم کنیم که به کادر اشاره کند. از این رو ما به (بعدی) نیاز داریم
head.next => این به آیتم بعدی در فهرست اشاره می کند
head.next.data => 4

برای دسترسی به داده های کادر سوم، ابتدا باید نشانگر (فلش) را طوری تنظیم کنیم که به کادر اشاره کند. از این رو ما به (next.next) نیاز داریم
head.next.next => این به آیتم بعدی > بعدی در فهرست اشاره می کند
head.next.next.data => 5

گره چیست؟

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

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

نحوه پیاده سازی فهرست پیوندی با استفاده از کلاس ها

 class Node { public function __construct( public $data, public ?Node $next = null ) {} } // Creating nodes $node1 = new Node(10); $node2 = new Node(20); $node3 = new Node(30); // Linking nodes $node1->next = $node2; $node2->next = $node3; // Traversing linked list $current = $node1; while ($current != null) { echo $current->data . " "; $current = $current->next; }

نحوه پیاده سازی فهرست پیوندی با استفاده از آرایه ها

 // creating nodes as an associative array $node1 = ['data' => 10, 'next' => null]; $node2 = ['data' => 20, 'next' => null]; $node3 = ['data' => 30, 'next' => null]; // linking nodes $node1['next'] = &$node2; $node2['next'] = &$node3; // Traversing linked list $current = $node1; while ($current != null) { echo $current["data"] . " "; $current = &$current["next"]; }

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

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

عبور از یک فهرست پیوندی به معنای تکرار در هر گره از فهرست تا رسیدن به گره پایانی است.

انواع فهرست پیوندی

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

فهرست تک پیوندی

هر گره دارای داده و مرجعی به گره بعدی است.

توضیح غیر رمزی

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

قطار A اولین قسمت سفر شما را نشان می‌دهد و شما را از ایستگاه A به ایستگاه B می‌برد. وقتی به ایستگاه B می‌رسید، تابلویی وجود دارد که به شما دستور می‌دهد قطار را برای ادامه سفر تغییر دهید.

قطار B قسمت دوم سفر شما را نشان می دهد و شما را از ایستگاه B به ایستگاه C می برد. باز هم وقتی به ایستگاه C می رسید، هیچ علامتی برای قطار دیگری وجود ندارد زیرا به مقصد نهایی خود رسیده اید.

در این قیاس:

هر بخش قطار (قطار A، قطار B، و قطار C) یک گره را در فهرست پیوندی منفرد نشان می دهد.

وظیفه هر قطار شبیه به داده های ذخیره شده در هر گره است و بخشی از سفر شما را نشان می دهد.

انتقال بین قطارها در هر ایستگاه مشابه نشانگر "بعدی" در یک فهرست پیوندی است که بخش بعدی سفر شما را نشان می دهد.

در مقصد نهایی (ایستگاه C)، نیازی به نشانگر یا علامت قطار دیگر نیست زیرا پایان سفر شم است.

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

ویژگی های عملکرد فهرست پیوندی منفرد

پیمایش: پیمایش فقط در یک جهت (یعنی فقط به جلو) مجاز است. شما می توانید از طریق فهرست به جلو حرکت کنید، اما نمی توانید به راحتی به عقب بروید.

کارآیی حافظه: فهرست تک پیوندی عموماً از نظر حافظه کارآمدتر است زیرا فقط به یک مرجع در هر گره نیاز دارد.

پیچیدگی: عملیات درج و حذف آسان تر است زیرا فقط باید مراجع را در یک جهت به روز کنید.

پیچیدگی زمان و مکان

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

پیمایش

پیچیدگی زمانی O(n)، که در آن n تعداد گره های موجود در فهرست است. پیچیدگی فضا O(1)، به فضای اضافی متناسب با اندازه ورودی نیاز ندارد.

درج در ابتدا

پیچیدگی زمانی O(1)، شامل به روز رسانی مراجع در سر است. پیچیدگی فضا O(1)، به فضای اضافی متناسب با اندازه ورودی نیاز ندارد.

درج در انتها

پیچیدگی زمانی O(n)، ممکن است برای رسیدن به پایان نیاز به پیمایش کل فهرست داشته باشد. پیچیدگی فضا O(1)، به فضای اضافی متناسب با اندازه ورودی نیاز ندارد.

حذف در ابتدا

پیچیدگی زمانی O(1)، شامل به روز رسانی مراجع در سر است. پیچیدگی فضایی O(1)، ثابت.

حذف در پایان

پیچیدگی زمانی O(n)، ممکن است برای رسیدن به پایان نیاز به پیمایش کل فهرست داشته باشد. پیچیدگی فضایی O(1)، ثابت.

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

در یک فهرست دارای پیوند دوگانه، گره head معمولاً مرجع prev ندارد زیرا اولین گره است و پس گره قبلی ندارد.

با این حال، گره head دارای یک مرجع next است که به گره بعدی در فهرست اشاره می کند. هر گره دارای داده و ارجاع به هر دو گره بعدی و قبلی است.

توضیح غیر رمزی

تصور کنید کتابی دارید که در آن هر صفحه نشان دهنده کاری است که باید انجام دهید، درست مانند موارد موجود در فهرست کارهایتان.

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

صفحه 1 (تکلیف الف) نشان دهنده اولین وظیفه در کتاب است. این شامل اطلاعاتی در مورد وظیفه A است و دارای یک فلش است که به سمت جلو به صفحه 2 (وظیفه B) اشاره می کند، که نشان می دهد وظیفه B بعد از وظیفه A در کتاب آمده است. اما صفحه 1 پیکان رو به عقب ندارد زیرا صفحه اول کتاب است و صفحه قبلی ندارد.

صفحه 2 (وظیفه B) حاوی اطلاعاتی در مورد وظیفه B است و دارای فلش هایی است که هم به سمت جلو به سمت صفحه 3 (وظیفه C) و هم به سمت عقب به صفحه 1 (وظیفه A) اشاره می کند، که نشان می دهد وظیفه C بعد از کار B و وظیفه A قبل از کار B در می آید. کتاب.

صفحه 3 (وظیفه ج) نشان دهنده آخرین کار در کتاب است. این شامل اطلاعاتی در مورد وظیفه C است و دارای یک فلش به سمت عقب به سمت صفحه 2 (وظیفه B) است، که نشان می دهد وظیفه B قبل از وظیفه C در کتاب آمده است.

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

ویژگی های عملکرد فهرست های دارای پیوند دوگانه

پیمایش: فهرست های دارای پیوند دوگانه امکان پیمایش در هر دو جهت - جلو و عقب را می دهند. این پیمایش دو طرفه، پیمایش انعطاف‌پذیرتری را در فهرست امکان‌پذیر می‌سازد و به عملیات‌هایی مانند تکرار به ترتیب معکوس اجازه می‌دهد.

کارایی حافظه : فهرست ‌های دارای پیوند دوگانه معمولاً در مقایسه با فهرست ‌های پیوندی منفرد به حافظه بیشتری نیاز دارند، زیرا هر گره حاوی دو مرجع (اشاره‌گر) است - یکی برای گره بعدی و دیگری برای گره قبلی. این سربار حافظه اضافی در هر گره می تواند بر کارایی کلی حافظه تأثیر بگذارد، به خصوص برای فهرست های بزرگ.

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

پیچیدگی زمان و مکان

پیمایش

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

درج در ابتدا

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

درج در انتها

پیچیدگی زمانی برای این عملیات به زمان O(1) نیاز دارد. این به این دلیل است که شما به گره دم دسترسی مستقیم دارید، پس می توانید منابع را بدون نیاز به پیمایش کل فهرست به روز کنید. پیچیدگی فضا O(1)، به فضای اضافی متناسب با اندازه ورودی نیاز ندارد.

حذف در ابتدا

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

حذف در پایان

پیچیدگی زمانی برای این عملیات به زمان O(1) نیاز دارد. این به این دلیل است که شما به گره دم دسترسی مستقیم دارید، پس می توانید منابع را بدون نیاز به پیمایش کل فهرست به روز کنید. پیچیدگی فضا O(1)، به فضای اضافی متناسب با اندازه ورودی نیاز ندارد.

فهرست پیوندی دایره ای

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

توضیح غیر رمزی

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

درست مانند یک فهرست دایره ای پیوندی، حلقه پیمایش مداوم را بدون نقطه پایانی تضمین می کند و مسافران (داده ها) را می توان در هر ایستگاه (گره) اضافه یا حذف کرد.

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

ویژگی های عملکرد فهرست های پیوندی دایره ای

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

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

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

پیچیدگی زمان و مکان

پیمایش

پیچیدگی زمانی: O(n) – از آنجایی که برای رسیدن به پایان باید از تمام گره های فهرست عبور کنید.

پیچیدگی فضا: O(1) - فقط مقدار ثابتی از فضای اضافی برای عبور یک متغیر موقت از فهرست مورد نیاز است.

درج در ابتدا

پیچیدگی زمانی: O(1) - درج در ابتدا به سادگی شامل به روز رسانی مراجع در سر است.

پیچیدگی فضا: O(1) - فضای اضافی مورد نیاز نیست.

درج در انتها

پیچیدگی زمانی: O(n) - ممکن است برای رسیدن به انتهایی که باید درج انجام شود، کل فهرست را طی کنید.

پیچیدگی فضا: O(1) - فضای اضافی مورد نیاز نیست.

حذف در ابتدا

پیچیدگی زمانی O(1)، شامل به روز رسانی مراجع در سر است.

پیچیدگی فضایی O(1)، ثابت.

حذف در پایان

پیچیدگی زمانی O(n)، ممکن است برای رسیدن به پایان نیاز به پیمایش کل فهرست داشته باشد.

پیچیدگی فضایی O(1)، ثابت.

خلاصه عملیات برای پیچیدگی زمانی

خلاصه ای از عملیات برای پیچیدگی فضایی

تفاوت بین آرایه و فهرست پیوندی

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

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

چگونه مشکل حذف موارد تکراری از فهرست مرتب شده را حل کنیم

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

راه حل در PHP

 /** * Definition for a singly-linked list. * class ListNode { * public $val = 0; * public $next = null; * function __construct($val = 0, $next = null) { * $this->val = $val; * $this->next = $next; * } * } */ class Solution { /** * @param ListNode $head * @return ListNode */ function deleteDuplicates($head) { $node = $head; while($node !== null && $node->next !== null) { if ($node->val == $node->next->val) { $node->next = $node->next->next; }else { $node = $node->next; } } return $head; } }

راه حل در جاوا اسکریپت

 /** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */ /** * @param {ListNode} head * @return {ListNode} */ var deleteDuplicates = function(head) { let node = head; while(node?.next) { if (node.val === node.next.val) { node.next = node.next.next } else { node = node.next } } return head };

توضیح کد

با توجه به روش deleteDuplicates :

node به سر فهرست پیوند داده شده مقداردهی اولیه می شود.

یک حلقه while از طریق فهرست پیوندی تا انتها یا تا زمانی که خاصیت next گره فعلی null شود، تکرار می شود.

در داخل حلقه، تحلیل می کند که آیا مقدار گره فعلی برابر با مقدار گره بعدی است یا خیر. اگر آنها برابر باشند، با تنظیم ویژگی next گره فعلی به ویژگی بعدی گره بعدی، گره next پرش می کند.

اگر مقادیر برابر نباشند، با به روز رسانی مقدار node به node->next به گره بعدی منتقل می شود.

در نهایت، متد سر فهرست پیوندی اصلاح شده را برمی گرداند.

اپراتور امن تهی ( ?. ) مورد استفاده در راه حل کد JS نیز از PHP 8.0 در دسترس است.

این کد با تنظیم نشانگرها، موارد تکراری را از یک فهرست تک پیوندی حذف می کند و دارای پیچیدگی زمانی O ( n ) و پیچیدگی فضایی O (1) است که n تعداد گره ها در فهرست پیوند شده است.

ارجاع

لیست پیوندی چگونه کار می کند

نتیجه

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

به یادگیری ادامه دهید، و کدنویسی شاد!

می توانید من را در لینکدین و توییتر پیدا کنید.

خبرکاو