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

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

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

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

فهرست پیوندی چیست؟

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

در اینجا، می‌توانید ببینید که آدرس‌های گره‌ها لزوماً بلافاصله ترتیبی نیستند. گره اول دارای آدرس ۲۰۰ و گره دوم دارای آدرس ۸۰۱ است، به جای ۲۰۱ که ممکن است انتظار داشته باشید.

سپس گره ها چگونه به صورت خطی ذخیره می شوند؟

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

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

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

یک گره در یک فهرست پیوندی از دو بخش تشکیل شده است:

data که ارزش گره را نشان می دهد.

next که ارجاع به گره بعدی است.

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

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

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

آخرین گره گره tail نامیده می شود. از آنجایی که هیچ گرهی بعد از آخرین گره وجود ندارد، آخرین گره همیشه به null اشاره می کند.

اشاره گر null به هیچ مکان حافظه اشاره نمی کند.

نحوه ایجاد فهرست پیوندی به صورت برنامه ای

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

ایجاد گره

گره ها را به هم متصل کنید.

گره ها را اضافه کنید.

درج گره ها

حذف گره ها

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

همانطور که می دانید، یک گره از دو بخش تشکیل شده است: داده و آدرس گره بعدی.

در اینجا نحوه ایجاد کلاسی به نام Node آمده است:

 class Node { int data; Node next; Node(int data) { this.data = data; this.next = null; } }

کلاس Node یک گره را در یک فهرست پیوندی با دو متغیر نمونه نشان می‌دهد: داده (داده‌های ذخیره شده در گره را نگه می‌دارد) و next (ارجاعی به گره بعدی در فهرست دارد).

سازنده یک داده آرگومان int را برای مقداردهی اولیه متغیر داده می گیرد و متغیر بعدی را به طور پیش فرض null می کند.

اکنون، می‌توانید به سادگی گره‌ها را ایجاد کنید و با ایجاد نمونه‌های جدیدی از کلاس Node ، داده‌ها را به آنها اضافه کنید:

 // create nodes Node node1 = new Node(11); Node node2 = new Node(18); Node node3 = new Node(24);

در کد بالا سه گره ایجاد کردیم:

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

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

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

 class LinkedList { Node head; LinkedList() { this.head = null; } }

در ابتدا گره head بر روی null تنظیم می شود زیرا هنوز هیچ گره ای در فهرست پیوند شده وجود ندارد.

اکنون برای اتصال گره ها به یکدیگر در یک فهرست پیوندی، می توانید با تنظیم گره head به اولین گره فهرست ، در این مورد node1 ، شروع کنید.

 head = node1;

سپس نقطه بعدی node1 به node2 و نقطه بعدی node2 را به node3 تبدیل کنید. به این معنا که:

 node1.next = node2; node2.next = node3;

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

نحوه اضافه کردن یک گره به فهرست پیوند شده

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

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

در حال الحاق به یک فهرست پیوندی غیر خالی

چگونه یک گره را به یک فهرست پیوندی خالی اضافه کنیم

اگر هیچ گره ای در یک فهرست پیوندی وجود نداشته باشد، یک فهرست پیوندی خالی است. برای الحاق یک گره به یک فهرست پیوندی خالی، ابتدا باید مطمئن شوید که فهرست پیوندی خالی است. شما می توانید این کار را با تحلیل اینکه گره head null است انجام دهید.

اگر گره head null است، می توانید به سادگی head روی گره جدید تنظیم کنید:

 if (head == null) { head = newNode; }

چگونه یک گره را به فهرست پیوندی غیر خالی اضافه کنیم

اگر یک یا چند گره در یک فهرست پیوندی وجود داشته باشد، یک فهرست پیوندی غیرخالی است.

برای الحاق یک گره به یک فهرست پیوندی غیر خالی، آخرین پیوند گره را به گره جدید ایجاد کنید.

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

برای انجام این کار، یک اشاره گر موقت ایجاد کنید (می توانید اشاره گر را با current تماس بگیرید) که به گره سر اشاره می کند.

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

هنگامی که گره next current null است، می توانید next از گره current را به گره جدید تبدیل کنید. به این معنا که:

 while (current.next != null) { current = current.next; } current.next = newNode;

نحوه درج یک گره در فهرست پیوندی

درج یک گره به معنای گفت ن یک گره به یک شاخص داده شده است. هنگام درج یک گره دو حالت وجود دارد که باید در نظر گرفته شود:

درج یک گره در اولین شاخص.

درج یک گره در یک شاخص معین.

نحوه درج یک گره در First Index

برای درج یک گره در اولین شاخص:

next از گره جدید به گره head اشاره کنید

head روی گره جدید قرار دهید

 if (index == 0) { newNode.next = head; head = newNode; }

نحوه درج یک گره در هر موقعیتی

فرض کنید می خواهید یک گره در فهرست ۲ در فهرست پیوندی بالا اضافه کنید.

برای درج یک گره در شاخص ۲، باید گره ای را که قبل از ایندکس ۲ قرار دارد، عبور دهید.

بعد، یک گره جدید ایجاد کنید و next از گره جدید را به گره next گره current نشان دهید.

next نقطه current را به گره جدید تبدیل کنید.

این کد برای انجام همه این کارها است:

 for (int i = 0; i < index - 1 && current != null; i++) { current = current.next; } if (current != null) { newNode.next = current.next; current.next = newNode; }

نحوه حذف یک گره در فهرست پیوندی

دو راه برای حذف گره ها در فهرست پیوندی وجود دارد:

حذف گره سر

حذف یک گره در یک موقعیت مشخص

نحوه حذف هد نود

حذف head گره یک فهرست پیوندی ساده است. در صورت نیاز به دسترسی بعداً می توانید داده های گره head را در یک متغیر موقت ذخیره کنید. سپس نشانگر head طوری تنظیم کنید که به گره next بعد از گره head اشاره کند.

 if (index == 0) { deletedValue = head.data; head = head.next; }

چگونه یک گره را در یک موقعیت مشخص حذف کنیم

فرض کنید می خواهید گره موجود در نمایه ۲ را در نمودار زیر حذف کنید:

با قرار دادن گره در شاخص ۱ به گره در شاخص ۳ می توانید گره را در شاخص ۲ حذف کنید.

برای حذف یک گره باید به گره ای که می خواهید حذف کنید و گره قبل از آن دسترسی داشته باشید. دو اشاره گر موقت بگیرید (می توانید نشانگرها را previous و current صدا بزنید). اجازه دهید نقطه previous به null و current به گره head اشاره کند.

حال، current یک قدم به جلو ببرید و previous را به current ببرید تا به شاخص ۲ برسید.

next نقطه previous را به next گره current تبدیل کنید.

سپس داده های current را در یک متغیر برای استفاده در آینده ذخیره کنید.

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

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

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

 for (int i = 0; i < index && current != null; i++) { previous = current; current = current.next; } if (current != null) { deletedValue = current.data; previous.next = current.next; }

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

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

 class Node { int data; Node next; Node(int data) { this.data = data; this.next = null; } } class LinkedList { Node head; LinkedList() { this.head = null; } public void createLinkedList() { Node node1 = new Node(11); this.head = node1; Node node2 = new Node(18); node1.next = node2; Node node3 = new Node(24); node2.next = node3; } public void append(Node newNode) { Node current = this.head; if (current == null) { this.head = newNode; } else { while (current.next != null) { current = current.next; } current.next = newNode; } } public void insert(Node newNode, int index) { Node current = this.head; if (index == 0) { newNode.next = current; this.head = newNode; } else { for (int i = 0; i < index - 1 && current != null; i++) { current = current.next; } if (current != null) { newNode.next = current.next; current.next = newNode; } } } public int delete(int index) { Node current = this.head; Node previous = null; int deletedValue = -1; if (index == 0) { deletedValue = this.head.data; this.head = this.head.next; return deletedValue; } else { for (int i = 0; i < index && current != null; i++) { previous = current; current = current.next; } if (current != null) { deletedValue = current.data; previous.next = current.next; } return deletedValue; } } public void displayLinkedList() { Node current = this.head; while (current != null) { System.out.println(current.data); current = current.next; } } } class Main { public static void main(String[] args) { LinkedList l1 = new LinkedList(); Node newNode1 = new Node(22); Node newNode2 = new Node(43); Node newNode3 = new Node(5); l1.createLinkedList(); l1.append(newNode1); l1.insert(newNode2, 0); l1.insert(newNode3, 2); l1.delete(2); l1.displayLinkedList(); } }

بسته بندی

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

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

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

به احتمال زیاد شما یک فهرست پیوندی برای برنامه های خود ایجاد نمی کنید، زیرا تقریباً هر زبان برنامه نویسی دارای یک فهرست پیوندی داخلی است.

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