Λειτουργίες συνδεδεμένης λίστας: Διασχίστε, Εισαγάγετε και Διαγράψτε

Σε αυτό το σεμινάριο, θα μάθετε διαφορετικές λειτουργίες σε μια συνδεδεμένη λίστα. Επίσης, θα βρείτε υλοποίηση λειτουργιών συνδεδεμένων λιστών σε C / C ++, Python και Java.

Τώρα που έχετε κατανοήσει τις βασικές έννοιες πίσω από τη συνδεδεμένη λίστα και τους τύπους τους, ήρθε η ώρα να ερευνήσετε τις κοινές λειτουργίες που μπορούν να εκτελεστούν.

Δύο σημαντικά σημεία που πρέπει να θυμάστε:

  • το κεφάλι δείχνει στον πρώτο κόμβο της συνδεδεμένης λίστας
  • ο επόμενος δείκτης του τελευταίου κόμβου είναι NULL, οπότε αν ο επόμενος τρέχων κόμβος είναι NULL, έχουμε φτάσει στο τέλος της συνδεδεμένης λίστας.

Σε όλα τα παραδείγματα, θα υποθέσουμε ότι η συνδεδεμένη λίστα έχει τρεις κόμβους 1 --->2 --->3με δομή κόμβου όπως παρακάτω:

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

Πώς να διασχίσετε μια συνδεδεμένη λίστα

Η εμφάνιση των περιεχομένων μιας συνδεδεμένης λίστας είναι πολύ απλή. Συνεχίζουμε να μετακινούμε τον κόμβο temp στον επόμενο και να εμφανίζουμε τα περιεχόμενά του.

Όταν η θερμοκρασία είναι NULL, γνωρίζουμε ότι έχουμε φτάσει στο τέλος της συνδεδεμένης λίστας, ώστε να βγούμε από το loop while.

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

Το αποτέλεσμα αυτού του προγράμματος θα είναι:

 Τα στοιχεία λίστας είναι - 1 ---> 2 ---> 3 --->

Πώς να προσθέσετε στοιχεία σε μια συνδεδεμένη λίστα

Μπορείτε να προσθέσετε στοιχεία είτε στην αρχή, στη μέση ή στο τέλος της συνδεδεμένης λίστας.

Προσθέστε στην αρχή

  • Κατανομή μνήμης για νέο κόμβο
  • Αποθηκεύστε δεδομένα
  • Αλλαγή επόμενου νέου κόμβου σε σημείο προς κεφάλι
  • Αλλαγή κεφαλής σε σημείο σε κόμβο που δημιουργήθηκε πρόσφατα
 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 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; inext!=NULL) ( temp = temp->next; ) ) temp->next = temp->next->next;

Εφαρμογή LinkedList Operations σε Python, Java, C και 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); )

ενδιαφέροντα άρθρα...