Operasi Senarai Terpaut: Melintasi, Masukkan dan Padam

Dalam tutorial ini, anda akan mempelajari operasi yang berbeza pada senarai yang dipautkan. Anda juga akan dapat melaksanakan pelaksanaan operasi senarai terpaut di C / C ++, Python dan Java.

Sekarang setelah anda memahami konsep asas di sebalik senarai terpaut dan jenisnya, inilah masanya untuk menyelami operasi biasa yang dapat dilakukan.

Dua perkara penting yang perlu diingat:

  • menuju ke nod pertama senarai terpaut
  • penunjuk seterusnya dari simpul terakhir adalah NULL, jadi jika node semasa seterusnya adalah NULL, kita telah sampai ke akhir senarai terpaut.

Dalam semua contoh, kami akan menganggap bahawa senarai terpaut mempunyai tiga nod 1 --->2 --->3dengan struktur nod seperti di bawah:

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

Cara Melintasi Senarai Terpaut

Memaparkan kandungan senarai terpaut sangat mudah. Kami terus memindahkan node temp ke yang berikutnya dan memaparkan kandungannya.

Apabila suhu NULL, kita tahu bahawa kita telah sampai ke akhir senarai terpaut sehingga kita keluar dari loop sementara.

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

Hasil daripada program ini adalah:

 Elemen senarai ialah - 1 ---> 2 ---> 3 --->

Cara Menambah Elemen ke Senarai Terpaut

Anda boleh menambahkan elemen pada awal, tengah atau akhir senarai terpaut.

Tambah ke permulaan

  • Peruntukkan memori untuk nod baru
  • Simpan data
  • Tukar sebelah simpul baru ke arah kepala
  • Tukar kepala ke titik ke nod yang baru dibuat
 struct node *newNode; newNode = malloc(sizeof(struct node)); newNode->data = 4; newNode->next = head; head = newNode;

Tambah ke Akhir

  • Peruntukkan memori untuk nod baru
  • Simpan data
  • Melintasi simpul terakhir
  • Tukar sebelah simpul terakhir ke nod yang baru dibuat
 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;

Tambah ke Tengah

  • Peruntukkan memori dan simpan data untuk nod baru
  • Melintasi simpul sebelum kedudukan nod baru yang diperlukan
  • Tukar petunjuk seterusnya untuk memasukkan simpul baru di antara
 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;

Cara Memadam dari Senarai Terpaut

Anda boleh memadam dari awal, akhir atau dari kedudukan tertentu.

Padamkan dari awal

  • Arahkan ke nod kedua
 head = head->next;

Padamkan dari hujung

  • Melintasi elemen terakhir kedua
  • Tukar penunjuk seterusnya menjadi nol
 struct node* temp = head; while(temp->next->next!=NULL)( temp = temp->next; ) temp->next = NULL;

Padamkan dari tengah

  • Melintasi elemen sebelum elemen yang hendak dihapuskan
  • Tukar petunjuk seterusnya untuk mengecualikan nod dari rantai
 for(int i=2; inext!=NULL) ( temp = temp->next; ) ) temp->next = temp->next->next;

Melaksanakan Operasi LinkedList di Python, Java, C, dan 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); )

Artikel menarik...