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

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

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

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

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

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

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

• داده آن گره
• آدرس گره بعدی

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

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

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;

/* 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

# 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;
    }
  }
}

// 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);
}

// 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;
  }
}

// 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 اشاره می‌کند و یک ساختار حلقوی ایجاد می‌کند. این نوع لیست پیوندی می‌تواند به‌صورت یک طرفه یا دو طرفه باشد.

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

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

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

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

• دسترسی تصادفی: برخلاف آرایهآموزش آرایه در ساختمان داده به زبان ساده و از 0 تا 100در این مقاله موارد زیر بررسی شده است : 1- آرایه چیست 2- انواع اندیس گذاری در آرایه 3- انواع آرایه 4- محاسبه آدرس در آرایه 5- محاسبه شماره در آرایه 6- آرایه در برنامه نویسی 7- مزایای استفاده از آرایه‌ها، لیست‌های پیوندی اجازه دسترسی مستقیم به عناصر با استفاده از Index را نمی‌دهند. پیمایش برای رسیدن به یک گره خاص مورد نیاز است.
• حافظه اضافی: لیست‌های پیوندی در مقایسه با آرایه‌ها به حافظه اضافی برای ذخیره اشاره‌گرها نیاز دارند.

جمع ‌بندی

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

مطالب مرتبط

همه مقالات

متغیر در برنامه نویسی چیست ⚡️انواع متغیر در برنامه نویسی

مفهوم وراثت یا ارث بری (Inheritance) در برنامه نویسی

پایتون یا سی شارپ؟ – آینده پایتون بهتر است یا سی شارپ

زبان های برنامه نویسی هوش مصنوعی