In diesem Tutorial lernen Sie verschiedene Vorgänge in einer verknüpften Liste kennen. Außerdem finden Sie die Implementierung verknüpfter Listenoperationen in C / C ++, Python und Java.
Nachdem Sie die grundlegenden Konzepte der verknüpften Liste und ihre Typen verstanden haben, ist es an der Zeit, sich mit den allgemeinen Vorgängen zu befassen, die ausgeführt werden können.
Zwei wichtige Punkte, an die Sie sich erinnern sollten:
- head zeigt auf den ersten Knoten der verknüpften Liste
- Der nächste Zeiger des letzten Knotens ist NULL. Wenn also der nächste aktuelle Knoten NULL ist, haben wir das Ende der verknüpften Liste erreicht.
In allen Beispielen wird davon ausgegangen, dass die verknüpfte Liste drei Knoten 1 --->2 --->3mit der folgenden Knotenstruktur aufweist:
struct node ( int data; struct node *next; );
So durchlaufen Sie eine verknüpfte Liste
Das Anzeigen des Inhalts einer verknüpften Liste ist sehr einfach. Wir verschieben den temporären Knoten weiter zum nächsten und zeigen seinen Inhalt an.
Wenn temp NULL ist, wissen wir, dass wir das Ende der verknüpften Liste erreicht haben, sodass wir aus der while-Schleife herauskommen.
struct node *temp = head; printf("List elements are - "); while(temp != NULL) ( printf("%d --->",temp->data); temp = temp->next; )
Die Ausgabe dieses Programms lautet:
Listenelemente sind - 1 ---> 2 ---> 3 --->
So fügen Sie einer verknüpften Liste Elemente hinzu
Sie können Elemente entweder am Anfang, in der Mitte oder am Ende der verknüpften Liste hinzufügen.
Zum Anfang hinzufügen
- Ordnen Sie Speicher für neuen Knoten zu
- Daten speichern
- Ändern Sie den nächsten neuen Knoten so, dass er auf Kopf zeigt
- Ändern Sie den Kopf so, dass er auf den kürzlich erstellten Knoten zeigt
struct node *newNode; newNode = malloc(sizeof(struct node)); newNode->data = 4; newNode->next = head; head = newNode;
Zum Ende hinzufügen
- Ordnen Sie Speicher für neuen Knoten zu
- Daten speichern
- Zum letzten Knoten fahren
- Ändern Sie den vorletzten Knoten in den zuletzt erstellten Knoten
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;
Zur Mitte hinzufügen
- Ordnen Sie Speicher zu und speichern Sie Daten für neuen Knoten
- Fahren Sie kurz vor der gewünschten Position des neuen Knotens zum Knoten
- Ändern Sie die nächsten Zeiger so, dass dazwischen ein neuer Knoten eingefügt wird
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;
So löschen Sie aus einer verknüpften Liste
Sie können entweder am Anfang, am Ende oder an einer bestimmten Position löschen.
Von Anfang an löschen
- Zeigen Sie mit dem Kopf auf den zweiten Knoten
head = head->next;
Vom Ende löschen
- Zum vorletzten Element fahren
- Ändern Sie den nächsten Zeiger auf null
struct node* temp = head; while(temp->next->next!=NULL)( temp = temp->next; ) temp->next = NULL;
Aus der Mitte löschen
- Vor dem zu löschenden Element zum Element wechseln
- Ändern Sie die nächsten Zeiger, um den Knoten von der Kette auszuschließen
for(int i=2; inext!=NULL) ( temp = temp->next; ) ) temp->next = temp->next->next;
Implementieren von LinkedList-Operationen in Python, Java, C und 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); )
