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

اشتراک
 
راهنمای انتخاب موضوع
انواع عملیات در لیست پیوندی
کنکور کامپیوترانواع عملیات در لیست پیوندی

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

این صفحه عالی به معرفی انواع عملیات در لیست پیوندی از جمله درج در لیست پیوندی، حذف در لیست پیوندی و جستجو در لیست پیوندی و نحوه پیاده سازی آنها پرداخته است

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

تصویر لیست پیوندی

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

درج در لیست پیوندی

می‌توان عناصر را به ابتدا، وسط یا انتهای لیست پیوند داده شده اضافه کرد.

درج در ابتدای لیست پیوندی

مراحل موردنیاز برای درج عنصر در ابتدای لیست پیوندی به‌صورت زیر است:

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

struct node *newNode;
newNode = malloc(sizeof(struct node));
newNode->data = 4;
newNode->next = head;
head = newNode;

درج در انتهای لیست پیوندی

مراحل موردنیاز برای درج عنصر در انتهای لیست پیوندی به‌صورت زیر است:

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

struct node *newNode;
newNode = malloc(sizeof(struct node));
newNode->data = 4;
newNode->next = NULL;

struct node *temp = head;
while(temp->next != NULL){
  temp = temp->next;
}

temp->next = newNode;

درج در وسط لیست پیوندی

مراحل موردنیاز برای درج عنصر در وسط لیست پیوندی به‌صورت زیر است:

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

struct node *newNode;
newNode = malloc(sizeof(struct node));
newNode->data = 4;

struct node *temp = head;

for(int i=2; i < position; i++) {
  if(temp->next != NULL) {
    temp = temp->next;
  }
}
newNode->next = temp->next;
temp->next = newNode;

عملیات حذف در لیست پیوندی

می‌توان از ابتدا، انتها یا از یک موقعیت خاص حذف کرد.

حذف از ابتدای لیست پیوندی

تنها مرحله موردنیاز برای حذف عنصر از ابتدای لیست پیوندی به‌صورت زیر است:

پیاده‌سازی آن به‌صورت زیر است:

head = head->next;

حتما بخوانید :
فیلم‌های آموزشی ساختمان داده‌

حذف از انتهای لیست پیوندی

مراحل موردنیاز برای حذف عنصر از انتهای لیست پیوندی به‌صورت زیر است:

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

struct node* temp = head;
while(temp->next->next!=NULL){
  temp = temp->next;
}
temp->next = NULL;

حذف از وسط لیست پیوندی

مراحل موردنیاز برای حذف عنصر از وسط لیست پیوندی به‌صورت زیر است:

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

for(int i=2; i< position; i++) {
  if(temp->next!=NULL) {
    temp = temp->next;
  }
}

temp->next = temp->next->next;

عملیات جستجو در لیست پیوندی

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

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

// Search a node
bool searchNode(struct Node** head_ref, int key) {
  struct Node* current = *head_ref;

  while (current != NULL) {
    if (current->data == key) return true;
      current = current->next;
  }
  return false;
}

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

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

Python

# Linked list operations in Python


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


class LinkedList:

    def __init__(self):
        self.head = None

    # Insert at the beginning
    def insertAtBeginning(self, new_data):
        new_node = Node(new_data)

        new_node.next = self.head
        self.head = new_node

    # Insert after a node
    def insertAfter(self, prev_node, new_data):

        if prev_node is None:
            print("The given previous node must inLinkedList.")
            return

        new_node = Node(new_data)
        new_node.next = prev_node.next
        prev_node.next = new_node

    # Insert at the end
    def insertAtEnd(self, new_data):
        new_node = Node(new_data)

        if self.head is None:
            self.head = new_node
            return

        last = self.head
        while (last.next):
            last = last.next

        last.next = new_node

    # Deleting a node
    def deleteNode(self, position):

        if self.head is None:
            return

        temp = self.head

        if position == 0:
            self.head = temp.next
            temp = None
            return

        # Find the key to be deleted
        for i in range(position - 1):
            temp = temp.next
            if temp is None:
                break

        # If the key is not present
        if temp is None:
            return

        if temp.next is None:
            return

        next = temp.next.next

        temp.next = None

        temp.next = next

    # Search an element
    def search(self, key):

        current = self.head

        while current is not None:
            if current.data == key:
                return True

            current = current.next

        return False

    # Sort the linked list
    def sortLinkedList(self, head):
        current = head
        index = Node(None)

        if head is None:
            return
        else:
            while current is not None:
                # index points to the node next to current
                index = current.next

                while index is not None:
                    if current.data > index.data:
                        current.data, index.data = index.data, current.data

                    index = index.next
                current = current.next

    # Print the linked list
    def printList(self):
        temp = self.head
        while (temp):
            print(str(temp.data) + " ", end="")
            temp = temp.next


if __name__ == '__main__':

    llist = LinkedList()
    llist.insertAtEnd(1)
    llist.insertAtBeginning(2)
    llist.insertAtBeginning(3)
    llist.insertAtEnd(4)
    llist.insertAfter(llist.head.next, 5)

    print('linked list:')
    llist.printList()

    print("\nAfter deleting an element:")
    llist.deleteNode(3)
    llist.printList()

    print()
    item_to_find = 3
    if llist.search(item_to_find):
        print(str(item_to_find) + " is found")
    else:
        print(str(item_to_find) + " is not found")

    llist.sortLinkedList(llist.head)
    print("Sorted List: ")
    llist.printList()

++C

// Linked list operations in C++

#include 

#include 
using namespace std;

// Create a node
struct Node {
  int data;
  struct Node* next;
};

void insertAtBeginning(struct Node** head_ref, int new_data) {
  // Allocate memory to a node
  struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));

  // insert the data
  new_node->data = new_data;
  new_node->next = (*head_ref);

  // Move head to new node
  (*head_ref) = new_node;
}

// Insert a node after a node
void insertAfter(struct Node* prev_node, int new_data) {
  if (prev_node == NULL) {
  cout << "the given previous node cannot be NULL";
  return;
  }

  struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
  new_node->data = new_data;
  new_node->next = prev_node->next;
  prev_node->next = new_node;
}

// Insert at the end
void insertAtEnd(struct Node** head_ref, int new_data) {
  struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
  struct Node* last = *head_ref; /* used in step 5*/

  new_node->data = new_data;
  new_node->next = NULL;

  if (*head_ref == NULL) {
  *head_ref = new_node;
  return;
  }

  while (last->next != NULL) last = last->next;

  last->next = new_node;
  return;
}

// Delete a node
void deleteNode(struct Node** head_ref, int key) {
  struct Node *temp = *head_ref, *prev;

  if (temp != NULL && temp->data == key) {
  *head_ref = temp->next;
  free(temp);
  return;
  }
  // Find the key to be deleted
  while (temp != NULL && temp->data != key) {
  prev = temp;
  temp = temp->next;
  }

  // If the key is not present
  if (temp == NULL) return;

  // Remove the node
  prev->next = temp->next;

  free(temp);
}

// Search a node
bool searchNode(struct Node** head_ref, int key) {
  struct Node* current = *head_ref;

  while (current != NULL) {
  if (current->data == key) return true;
  current = current->next;
  }
  return false;
}

// Sort the linked list
void sortLinkedList(struct Node** head_ref) {
  struct Node *current = *head_ref, *index = NULL;
  int temp;

  if (head_ref == NULL) {
  return;
  } else {
  while (current != NULL) {
    // index points to the node next to current
    index = current->next;

    while (index != NULL) {
    if (current->data > index->data) {
      temp = current->data;
      current->data = index->data;
      index->data = temp;
    }
    index = index->next;
    }
    current = current->next;
  }
  }
}

// Print the linked list
void printList(struct Node* node) {
  while (node != NULL) {
  cout << node->data << " ";
  node = node->next;
  }
}

// Driver program
int main() {
  struct Node* head = NULL;

  insertAtEnd(&head, 1);
  insertAtBeginning(&head, 2);
  insertAtBeginning(&head, 3);
  insertAtEnd(&head, 4);
  insertAfter(head->next, 5);

  cout << "Linked list: ";
  printList(head);

  cout << "\nAfter deleting an element: ";
  deleteNode(&head, 3);
  printList(head);

  int item_to_find = 3;
  if (searchNode(&head, item_to_find)) {
  cout << endl << item_to_find << " is found";
  } else {
  cout << endl << item_to_find << " is not found";
  }

  sortLinkedList(&head);
  cout << "\nSorted List: ";
  printList(head);
}

Java

// Linked list operations in Java

class LinkedList {
  Node head;

  // Create a node
  class Node {
    int data;
    Node next;

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

  // Insert at the beginning
  public void insertAtBeginning(int new_data) {
    // insert the data
    Node new_node = new Node(new_data);
    new_node.next = head;
    head = new_node;
  }

  // Insert after a node
  public void insertAfter(Node prev_node, int new_data) {
    if (prev_node == null) {
      System.out.println("The given previous node cannot be null");
      return;
    }
    Node new_node = new Node(new_data);
    new_node.next = prev_node.next;
    prev_node.next = new_node;
  }

  // Insert at the end
  public void insertAtEnd(int new_data) {
    Node new_node = new Node(new_data);

    if (head == null) {
      head = new Node(new_data);
      return;
    }

    new_node.next = null;

    Node last = head;
    while (last.next != null)
      last = last.next;

    last.next = new_node;
    return;
  }

  // Delete a node
  void deleteNode(int position) {
    if (head == null)
      return;

    Node temp = head;

    if (position == 0) {
      head = temp.next;
      return;
    }
    // Find the key to be deleted
    for (int i = 0; temp != null && i < position - 1; i++)
      temp = temp.next;

    // If the key is not present
    if (temp == null || temp.next == null)
      return;

    // Remove the node
    Node next = temp.next.next;

    temp.next = next;
  }

  // Search a node
  boolean search(Node head, int key) {
    Node current = head;
    while (current != null) {
      if (current.data == key)
        return true;
      current = current.next;
    }
    return false;
  }

  // Sort the linked list
  void sortLinkedList(Node head) {
    Node current = head;
    Node index = null;
    int temp;

    if (head == null) {
      return;
    } else {
      while (current != null) {
        // index points to the node next to current
        index = current.next;

        while (index != null) {
          if (current.data > index.data) {
            temp = current.data;
            current.data = index.data;
            index.data = temp;
          }
          index = index.next;
        }
        current = current.next;
      }
    }
  }

  // Print the linked list
  public void printList() {
    Node tnode = head;
    while (tnode != null) {
      System.out.print(tnode.data + " ");
      tnode = tnode.next;
    }

  }

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

    llist.insertAtEnd(1);
    llist.insertAtBeginning(2);
    llist.insertAtBeginning(3);
    llist.insertAtEnd(4);
    llist.insertAfter(llist.head.next, 5);

    System.out.println("Linked list: ");
    llist.printList();

    System.out.println("\nAfter deleting an element: ");
    llist.deleteNode(3);
    llist.printList();

    System.out.println();
    int item_to_find = 3;
    if (llist.search(llist.head, item_to_find))
      System.out.println(item_to_find + " is found");
    else
      System.out.println(item_to_find + " is not found");

    llist.sortLinkedList(llist.head);
    System.out.println("\nSorted List: ");
    llist.printList();
  }
}

 

جمع‌بندی

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

چه عملیاتی در یک لیست پیوندی سریع‌ترند؟

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

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

پیچیدگی زمانی عملیات‌ درج در ابتدا و حذف از ابتدا از مرتبه O(1)است. پیچیدگی زمانی عملیات‌ درج در وسط و انتها و حذف از وسط و انتها از مرتبه زمانی O(n) است. عملیات جستجو نیز از مرتبه زمانی O(n) است.

چگونه درج و حذف در لیست پیوندی سریعتر از است؟

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

امتیازدهی5 1 1 1 1 1 1 1 1 1 15.00 امتیاز (1 امتیاز)
اشتراک
برچسب‌ها :
13
12
5
16
19
14
11
22
17

مطالب مرتبط

همه مقالات
الگوریتم چیست

الگوریتم چیست

لیست زبان های برنامه نویسی + تاریخچه، کاربرد و رتبه هر یک

لیست زبان های برنامه نویسی + تاریخچه، کاربرد و رتبه هر یک

درخت تصمیم یا درخت تصمیم گیری چیست و چگونه کار می کند؟

درخت تصمیم یا درخت تصمیم گیری چیست و چگونه کار می کند؟

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

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

معرفی ارشد شبکه های کامپیوتری دانشگاه صنعتی شریف

معرفی ارشد شبکه های کامپیوتری دانشگاه صنعتی شریف

معرفی بهترین دانشگاه های ایران در رشته فناوری اطلاعات

معرفی بهترین دانشگاه های ایران در رشته فناوری اطلاعات

صحبت با هوش مصنوعی گوگل

صحبت با هوش مصنوعی گوگل

معرفی گرایش رایانش امن مقطع ارشد دانشگاه شریف

معرفی گرایش رایانش امن مقطع ارشد دانشگاه شریف

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

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

مشاهده تمامی مقالات
رتبه بندی دانشگاه های ایران + معرفی بهترین دانشگاه های ایران

رتبه بندی دانشگاه های ایران + معرفی بهترین دانشگاه های ایران

منابع کنکور ارشد کامپیوتر

منابع کنکور ارشد کامپیوتر

معرفی رشته آی تی (رشته فناوری اطلاعات)

معرفی رشته آی تی (رشته فناوری اطلاعات)

گرایش های ارشد کامپیوتر

گرایش های ارشد کامپیوتر

رشته کامپیوتر فنی حرفه ای و ادامه تحصیل این رشته در دانشگاه

رشته کامپیوتر فنی حرفه ای و ادامه تحصیل این رشته در دانشگاه

مشاهده تمامی مقالات
14
11
22
17
13
12
5
16
19
بارگذاری نظرات
تلگرام اینستاگرام