In deze tutorial leer je verschillende bewerkingen op een gekoppelde lijst. Ook vindt u de implementatie van gekoppelde lijstbewerkingen in C / C ++, Python en Java.
Nu u de basisconcepten achter de gekoppelde lijst en hun typen begrijpt, is het tijd om een duik te nemen in de algemene bewerkingen die kunnen worden uitgevoerd.
Twee belangrijke punten om te onthouden:
- head verwijst naar het eerste knooppunt van de gekoppelde lijst
- de volgende aanwijzer van het laatste knooppunt is NULL, dus als het volgende huidige knooppunt NULL is, hebben we het einde van de gekoppelde lijst bereikt.
In alle voorbeelden gaan we ervan uit dat de gekoppelde lijst drie knooppunten heeft 1 --->2 --->3met knooppuntstructuur zoals hieronder:
struct node ( int data; struct node *next; );
Hoe u door een gekoppelde lijst kunt bladeren
Het weergeven van de inhoud van een gekoppelde lijst is heel eenvoudig. We blijven het tijdelijke knooppunt naar het volgende verplaatsen en geven de inhoud weer.
Als temp NULL is, weten we dat we het einde van de gekoppelde lijst hebben bereikt, dus we komen uit de while-lus.
struct node *temp = head; printf("List elements are - "); while(temp != NULL) ( printf("%d --->",temp->data); temp = temp->next; )
De output van dit programma zal zijn:
Lijstelementen zijn - 1 ---> 2 ---> 3 --->
Elementen toevoegen aan een gekoppelde lijst
U kunt elementen toevoegen aan het begin, midden of einde van de gekoppelde lijst.
Voeg toe aan het begin
- Wijs geheugen toe voor een nieuw knooppunt
- Gegevens bewaren
- Verander het volgende van een nieuw knooppunt zodat het naar het hoofd wijst
- Verander het hoofd om naar een recent aangemaakt knooppunt te wijzen
struct node *newNode; newNode = malloc(sizeof(struct node)); newNode->data = 4; newNode->next = head; head = newNode;
Voeg toe aan het einde
- Wijs geheugen toe voor een nieuw knooppunt
- Gegevens bewaren
- Ga naar het laatste knooppunt
- Verander het volgende van de laatste knoop in een recent aangemaakt knooppunt
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;
Voeg toe aan het midden
- Wijs geheugen toe en sla gegevens op voor een nieuw knooppunt
- Ga naar het knooppunt net voor de vereiste positie van het nieuwe knooppunt
- Wijzig de volgende verwijzingen om een nieuw knooppunt ertussen op te nemen
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;
Verwijderen uit een gekoppelde lijst
U kunt vanaf het begin, het einde of een bepaalde positie verwijderen.
Verwijderen vanaf het begin
- Wijs het hoofd naar het tweede knooppunt
head = head->next;
Verwijderen van einde
- Ga naar het voorlaatste element
- Verander de volgende aanwijzer in null
struct node* temp = head; while(temp->next->next!=NULL)( temp = temp->next; ) temp->next = NULL;
Verwijderen uit midden
- Ga naar het element vóór het element dat moet worden verwijderd
- Wijzig de volgende verwijzingen om het knooppunt uit de keten te verwijderen
for(int i=2; inext!=NULL) ( temp = temp->next; ) ) temp->next = temp->next->next;
Implementeren van LinkedList-bewerkingen in Python, Java, C en 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); )
