کنکور کامپیوتر
0
ورود | ثبت نام
نظرات
اشتراک
بالا
علاقه‌مندی

اشتراک
 

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

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

لیست پیوندی یک ساختمان دادهآموزش ساختمان داده و الگوریتمآموزش ساختمان داده و الگوریتمهر ساختمان داده یک نوع فرمت ذخیره‌سازی و مدیریت داده‌ها در کامپیوتر است، که امکان دسترسی و اصلاح کارآمد آن داده‌ها را برای یکسری از الگوریتم‌ها و کاربردها فراهم می‌کند، در این صفحه به بررسی و آموزش ساختمان داده و الگوریتم پرداخته شده است خطی است که در آن، عناصر در یک مکان پیوسته ذخیره نمی‌شوند، بلکه با استفاده از اشاره گراشاره گر چیست — اشاره گرها در برنامه نویسیاشاره گر چیست — اشاره گرها در برنامه نویسیاین صفحه عالی توضیح داده اشاره گر چیست و نحوه تعریف اشاره گرها و همین طور اشاره گرها در برنامه نویسی را بررسی کرده سپس انواع اشاره گرها و کاربرد اشاره گرها را گفته ها به هم مرتبط می‌شوند. لیست پیوندی مجموعه‌ای از گره‌های متصل را تشکیل می‌دهد که در آن هر گره، داده‌ها و آدرس گره بعدی را ذخیره می‌کند. در این مقاله با ساختمان داده لیست پیوندی و پیاده‌سازی آن در پایتونزبان برنامه نویسی پایتون چیست؟ – نحوه شروع و دلایل محبوبیتزبان برنامه نویسی پایتون چیست؟ – نحوه شروع و دلایل محبوبیتزبان برنامه نویسی پایتون (Python) چیست؟ این مقاله عالی به بررسی دلایل محبوبیت پایتون، موارد استفاده از پایتون و نحوه شروع به برنامه نویسی پایتون پرداخته، جاواجاوا چیست؟ تعریف، معنی و ویژگی های جاوا (java) از 0تا100جاوا چیست؟ تعریف، معنی و ویژگی های جاوا (java) از 0تا100جاوا یک زبان برنامه نویسی همه منظوره، مبتنی بر کلاس و شی گرا است که برای داشتن وابستگی های پیاده سازی کمتر طراحی شده است، زبان برنامه نویسی جاوا شبیه ++C است، Cزبان برنامه نویسی C – مزایا و کاربرد زبان C – فرق C و ++Cزبان برنامه نویسی C – مزایا و کاربرد زبان C – فرق C و ++Cاین مقاله عالی ابتدا توضیح می‌دهد که زبان برنامه نویسی c چیست، سپس به بررسی مزایا و معایب زبان C ، کاربردهای زبان سی ، و تفاوت بین C و ++C می‌پردازد و سی پلاس پلاسبرنامه نویسی سی پلاس پلاس چیست؟ مزایای برنامه نویسی C++‎؟برنامه نویسی سی پلاس پلاس چیست؟ مزایای برنامه نویسی C++‎؟برنامه نویسی سی پلاس پلاس چیست و چه کاربردی دارد؟ این صفحه عالی به بررسی مزایای برنامه نویسی C++ پرداخته و نمونه هایی از کدهای زبان برنامه نویسی ++C را آورده آشنا خواهید شد.

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

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

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

ما باید نقطه‌ای را به‌عنوان نقطه شروع در نظر بگیریم، بنابراین ما به آدرس اولین گره یک نام خاص به اسم Head می‌دهیم؛ همچنین، آخرین گره در لیست پیوندی قابل شناسایی است زیرا قسمت بعدی آن به Null اشاره می‌کند.

مثال لیست پیوندی

حال با یک مثال نحوه کارکرد لیست پیوندی را بررسی می‌کنیم. ابتدا باید ببینیم که هر گره از لیست پیوندی چگونه نشان داده می‌شود. هر گره شامل موارد زیر است:

داده هر گره و آدرس گره بعدی آن را در ساختاری به‌صورت زیر نمایش می‌دهیم:

struct node
{
  int data;
  struct node *next;
};

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

/* Initialize nodes */
struct node *head;
struct node *one = NULL;
struct node *two = NULL;
struct node *three = NULL;

/* Allocate memory */
one = malloc(sizeof(struct node));
two = malloc(sizeof(struct node));
three = malloc(sizeof(struct node));

/* Assign data values */
one->data = 1;
two->data = 2;
three->data=3;

/* Connect nodes */
one->next = two;
two->next = three;
three->next = NULL;

/* Save address of first node in head */
head = one;

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

نحوه ایجاد یک لیست پیوندی با داده دلخواه

قدرت ساختمان داده لیست پیوندی ناشی از توانایی شکستن پیوندها و ایجاد یک گره در وسط آن است؛ به‌عنوان مثال، اگر می‌خواهید عنصر 4 را بین 1 و 2 قرار دهید، مراحل به صورت زیر خواهد بود:

  1. یک گره ساختار جدید ایجاد کنید و حافظهحافظه در کامپیوتر، همه چیز در مورد حافظه در معماری کامپیوترحافظه در کامپیوتر، همه چیز در مورد حافظه در معماری کامپیوتردر این مقاله به بررسی کامل حافظه در کامپیوتر، انواع حافظه در کامپیوتر، کش، روش‌های آدرس دهی کش، نگاشت آدرس و موارد دیگر می‌پردازیم را به آن اختصاص دهید.
  2. مقدار داده آن را "4" اضافه کنید.
  3. اشاره‌گر بعدی آن را به سمت گره ساختار حاوی 2 به عنوان مقدار داده بگیرید.
  4. اشاره‌گر بعدی "1" را به گره‌ای که ایجاد کردیم تغییر دهید.

مثالی از درج یک گره در میانه لیست پیوندی

انجام کاری مشابه در "1"، مستلزم تغییر موقعیت همه عناصر بعدی است!

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

Python

# Linked list implementation in Python

class Node:
  # Creating a node
  def __init__(self, item):
    self.item = item
    self.next = None

class LinkedList:

  def __init__(self):
    self.head = None

if __name__ == '__main__':

  linked_list = LinkedList()

  # Assign item values
  linked_list.head = Node(1)
  second = Node(2)
  third = Node(3)

  # Connect nodes
  linked_list.head.next = second
  second.next = third

  # Print the linked list item
  while linked_list.head != None:
    print(linked_list.head.item, end=" ")
    linked_list.head = linked_list.head.next

Java

// Linked list implementation in Java

class LinkedList {
  // Creating a node
  Node head;

  static class Node {
    int value;
    Node next;

    Node(int d) {
      value = d;
      next = null;
    }
  }

  public static void main(String[] args) {
    LinkedList linkedList = new LinkedList();

    // Assign value values
    linkedList.head = new Node(1);
    Node second = new Node(2);
    Node third = new Node(3);

    // Connect nodess
    linkedList.head.next = second;
    second.next = third;

    // printing node-value
    while (linkedList.head != null) {
      System.out.print(linkedList.head.value + " ");
      linkedList.head = linkedList.head.next;
    }
  }
}

C

// Linked list implementation in C

#include <stdio.h>
#include <stdlib.h>

// Creating a node
struct node {
  int value;
  struct node *next;
};

// print the linked list value
void printLinkedlist(struct node *p) {
  while (p != NULL) {
    printf("%d ", p->value);
    p = p->next;
  }
}

int main() {
  // Initialize nodes
  struct node *head;
  struct node *one = NULL;
  struct node *two = NULL;
  struct node *three = NULL;

  // Allocate memory
  one = malloc(sizeof(struct node));
  two = malloc(sizeof(struct node));
  three = malloc(sizeof(struct node));

  // Assign value values
  one->value = 1;
  two->value = 2;
  three->value = 3;

  // Connect nodes
  one->next = two;
  two->next = three;
  three->next = NULL;

  // printing node-value
  head = one;
  printLinkedlist(head);
}

C++

// Linked list implementation in C++

#include <bits/stdc++.h>
#include <iostream>
using namespace std;

// Creating a node
class Node {
  public:
  int value;
  Node* next;
};

int main() {
  Node* head;
  Node* one = NULL;
  Node* two = NULL;
  Node* three = NULL;

  // allocate 3 nodes in the heap
  one = new Node();
  two = new Node();
  three = new Node();

  // Assign value values
  one->value = 1;
  two->value = 2;
  three->value = 3;

  // Connect nodes
  one->next = two;
  two->next = three;
  three->next = NULL;

  // print the linked list value
  head = one;
  while (head != NULL) {
    cout value;
    head = head->next;
  }
}

عملیات های مهم لیست پیوندی

افزودن یک گره جدید

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

حذف یک گره

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

جستجوی یک مقدار خاص

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

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

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

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

از کاربردهای لیست پیوندی می‌توان به موارد زیر اشاره کرد:

انواع لیست پیوندی

لیست پیوندی انواع مختلفی دارد که در ادامه به معرفی آنها می‌پردازیم:

لیست پیوندی ساده (یک طرفه)

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

لیست پیوندی دوطرفه

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

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

لیست پیوندی حلقوی

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

مزایا و معایب لیست پیوندی

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

معایب لیست های پیوندی

جمع ‌بندی

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

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

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

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

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

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

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

مثال‌ لیست پیوندی در دنیای واقعی چیست؟

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

امتیازدهی5 1 1 1 1 1 1 1 1 1 15.00 امتیاز (1 امتیاز)
اشتراک
بارگذاری نظرات