Các thao tác trong danh sách được liên kết: Traverse, Insert và Delete

Trong hướng dẫn này, bạn sẽ học các thao tác khác nhau trên danh sách được liên kết. Ngoài ra, bạn sẽ tìm thấy việc triển khai các hoạt động danh sách liên kết trong C / C ++, Python và Java.

Bây giờ bạn đã hiểu các khái niệm cơ bản đằng sau danh sách liên kết và các loại của chúng, đã đến lúc đi sâu vào các hoạt động phổ biến có thể được thực hiện.

Hai điểm quan trọng cần nhớ:

  • đầu trỏ đến nút đầu tiên của danh sách được liên kết
  • con trỏ tiếp theo của nút cuối cùng là NULL, vì vậy nếu nút hiện tại tiếp theo là NULL, chúng ta đã đến cuối danh sách liên kết.

Trong tất cả các ví dụ, chúng tôi sẽ giả định rằng danh sách được liên kết có ba nút 1 --->2 --->3với cấu trúc nút như sau:

 struct node ( int data; struct node *next; );

Làm thế nào để xem qua một danh sách được liên kết

Hiển thị nội dung của danh sách liên kết rất đơn giản. Chúng tôi tiếp tục di chuyển nút tạm thời sang nút tiếp theo và hiển thị nội dung của nó.

Khi tạm thời là NULL, chúng ta biết rằng chúng ta đã đến cuối danh sách liên kết để thoát ra khỏi vòng lặp while.

 struct node *temp = head; printf("List elements are - "); while(temp != NULL) ( printf("%d --->",temp->data); temp = temp->next; )

Đầu ra của chương trình này sẽ là:

 Các phần tử trong danh sách là - 1 ---> 2 ---> 3 --->

Cách thêm phần tử vào danh sách được liên kết

Bạn có thể thêm các phần tử vào đầu, giữa hoặc cuối của danh sách được liên kết.

Thêm vào đầu

  • Phân bổ bộ nhớ cho nút mới
  • Lưu trữ dữ liệu
  • Thay đổi tiếp theo của nút mới để trỏ đến đầu
  • Thay đổi đầu để trỏ đến nút được tạo gần đây
 struct node *newNode; newNode = malloc(sizeof(struct node)); newNode->data = 4; newNode->next = head; head = newNode;

Thêm vào cuối

  • Phân bổ bộ nhớ cho nút mới
  • Lưu trữ dữ liệu
  • Đi ngang đến nút cuối cùng
  • Thay đổi tiếp theo của nút cuối cùng thành nút được tạo gần đây
 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;

Thêm vào giữa

  • Phân bổ bộ nhớ và lưu trữ dữ liệu cho nút mới
  • Di chuyển đến nút ngay trước vị trí cần thiết của nút mới
  • Thay đổi con trỏ tiếp theo để bao gồm nút mới ở giữa
 struct node *newNode; newNode = malloc(sizeof(struct node)); newNode->data = 4; struct node *temp = head; for(int i=2; i next != NULL) ( temp = temp->next; ) ) newNode->next = temp->next; temp->next = newNode;

Cách xóa khỏi danh sách được liên kết

Bạn có thể xóa từ đầu, cuối hoặc từ một vị trí cụ thể.

Xóa từ đầu

  • Hướng đầu đến nút thứ hai
 head = head->next;

Xóa khỏi kết thúc

  • Chuyển đến phần tử cuối cùng thứ hai
  • Thay đổi con trỏ tiếp theo của nó thành null
 struct node* temp = head; while(temp->next->next!=NULL)( temp = temp->next; ) temp->next = NULL;

Xóa từ giữa

  • Di chuyển đến phần tử trước khi phần tử bị xóa
  • Thay đổi các con trỏ tiếp theo để loại trừ nút khỏi chuỗi
 for(int i=2; inext!=NULL) ( temp = temp->next; ) ) temp->next = temp->next->next;

Triển khai các hoạt động LinkedList bằng Python, Java, C và C ++

Python Java C C ++ 
 # Linked list operations in Python # Create a node class Node: def __init__(self, item): self.item = item self.next = None class LinkedList: def __init__(self): self.head = None # Insert at the beginning def insertAtBeginning(self, data): new_node = Node(data) new_node.next = self.head self.head = new_node # Insert after a node def insertAfter(self, node, data): if node is None: print("The given previous node must inLinkedList.") return new_node = Node(data) new_node.next = node.next node.next = new_node # Insert at the end def insertAtEnd(self, data): new_node = Node(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 == None: return temp_node = self.head if position == 0: self.head = temp_node.next temp_node = None return # Find the key to be deleted for i in range(position - 1): temp_node = temp_node.next if temp_node is None: break # If the key is not present if temp_node is None: return if temp_node.next is None: return next = temp_node.next.next temp_node.next = None temp_node.next = next def printList(self): temp_node = self.head while (temp_node): print(str(temp_node.item) + " ", end="") temp_node = temp_node.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("After deleting an element:") llist.deleteNode(3) llist.printList()
 // Linked list operations in Java class LinkedList ( Node head; // Create a node class Node ( int item; Node next; Node(int d) ( item = d; next = null; ) ) public void insertAtBeginning(int data) ( // insert the item Node new_node = new Node(data); new_node.next = head; head = new_node; ) public void insertAfter(Node prev_node, int data) ( if (prev_node == null) ( System.out.println("The given previous node cannot be null"); return; ) Node new_node = new Node(data); new_node.next = prev_node.next; prev_node.next = new_node; ) public void insertAtEnd(int data) ( Node new_node = new Node(data); if (head == null) ( head = new Node(data); return; ) new_node.next = null; Node last = head; while (last.next != null) last = last.next; last.next = new_node; return; ) void deleteNode(int position) ( if (head == null) return; Node node = head; if (position == 0) ( head = node.next; return; ) // Find the key to be deleted for (int i = 0; node != null && i < position - 1; i++) node = node.next; // If the key is not present if (node == null || node.next == null) return; // Remove the node Node next = node.next.next; node.next = next; ) public void printList() ( Node node = head; while (node != null) ( System.out.print(node.item + " "); node = node.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("After deleting an element: "); llist.deleteNode(3); llist.printList(); ) )
 // Linked list operations in C #include #include // Create a node struct Node ( int item; struct Node* next; ); void insertAtBeginning(struct Node** ref, int data) ( // Allocate memory to a node struct Node* new_node = (struct Node*)malloc(sizeof(struct Node)); // insert the item new_node->item = data; new_node->next = (*ref); // Move head to new node (*ref) = new_node; ) // Insert a node after a node void insertAfter(struct Node* node, int data) ( if (node == NULL) ( printf("the given previous node cannot be NULL"); return; ) struct Node* new_node = (struct Node*)malloc(sizeof(struct Node)); new_node->item = data; new_node->next = node->next; node->next = new_node; ) void insertAtEnd(struct Node** ref, int data) ( struct Node* new_node = (struct Node*)malloc(sizeof(struct Node)); struct Node* last = *ref; new_node->item = data; new_node->next = NULL; if (*ref == NULL) ( *ref = new_node; return; ) while (last->next != NULL) last = last->next; last->next = new_node; return; ) void deleteNode(struct Node** ref, int key) ( struct Node *temp = *ref, *prev; if (temp != NULL && temp->item == key) ( *ref = temp->next; free(temp); return; ) // Find the key to be deleted while (temp != NULL && temp->item != 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); ) // Print the linked list void printList(struct Node* node) ( while (node != NULL) ( printf(" %d ", node->item); 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); printf("Linked list: "); printList(head); printf("After deleting an element: "); deleteNode(&head, 3); printList(head); ) 
 // Linked list operations in C++ #include #include using namespace std; // Create a node struct Node ( int item; struct Node* next; ); void insertAtBeginning(struct Node** ref, int data) ( // Allocate memory to a node struct Node* new_node = (struct Node*)malloc(sizeof(struct Node)); // insert the item new_node->item = data; new_node->next = (*ref); // Move head to new node (*ref) = new_node; ) // Insert a node after a node void insertAfter(struct Node* prev_node, int data) ( if (prev_node == NULL) ( cout  next = prev_node->next; prev_node->next = new_node; ) void insertAtEnd(struct Node** ref, int data) ( struct Node* new_node = (struct Node*)malloc(sizeof(struct Node)); struct Node* last = *ref; new_node->item = data; new_node->next = NULL; if (*ref == NULL) ( *ref = new_node; return; ) while (last->next != NULL) last = last->next; last->next = new_node; return; ) void deleteNode(struct Node** ref, int key) ( struct Node *temp = *ref, *prev; if (temp != NULL && temp->item == key) ( *ref = temp->next; free(temp); return; ) // Find the key to be deleted while (temp != NULL && temp->item != 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); ) // Print the linked list void printList(struct Node* node) ( while (node != NULL) ( cout  next, 5); cout << "Linked list: "; printList(head); cout << "After deleting an element: "; deleteNode(&head, 3); printList(head); )

thú vị bài viết...