Prepojené operácie so zoznamom: Traverz, vloženie a odstránenie

V tomto tutoriáli sa dozviete rôzne operácie spojené so zoznamom. Nájdete tiež implementáciu operácií spojených zoznamov v C / C ++, Python a Java.

Teraz, keď ste pochopili základné pojmy za prepojeným zoznamom a ich typy, je čas ponoriť sa do bežných operácií, ktoré je možné vykonať.

Je potrebné pamätať na dva dôležité body:

  • head ukazuje na prvý uzol prepojeného zoznamu
  • ďalší ukazovateľ posledného uzla je NULL, takže ak má ďalší aktuálny uzol NULL, dostali sme sa na koniec prepojeného zoznamu.

Vo všetkých príkladoch budeme predpokladať, že prepojený zoznam má tri uzly 1 --->2 --->3so štruktúrou uzlov, ako je uvedené nižšie:

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

Ako prechádzať prepojeným zoznamom

Zobrazenie obsahu prepojeného zoznamu je veľmi jednoduché. Tempový uzol neustále posúvame k ďalšiemu a zobrazujeme jeho obsah.

Keď je teplota NULL, vieme, že sme sa dostali na koniec prepojeného zoznamu, takže sa dostaneme zo slučky while.

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

Výstupom tohto programu bude:

 Prvky zoznamu sú - 1 ---> 2 ---> 3 --->

Ako pridať prvky do prepojeného zoznamu

Prvky môžete pridať na začiatok, do stredu alebo na koniec prepojeného zoznamu.

Pridajte na začiatok

  • Prideliť pamäť pre nový uzol
  • Uložiť dáta
  • Zmeňte nasledujúci nový uzol tak, aby smeroval na hlavičku
  • Zmeňte hlavičku tak, aby ukazovala na nedávno vytvorený uzol
 struct node *newNode; newNode = malloc(sizeof(struct node)); newNode->data = 4; newNode->next = head; head = newNode;

Pridajte na koniec

  • Prideliť pamäť pre nový uzol
  • Uložiť dáta
  • Prejdite na posledný uzol
  • Zmeniť ďalší z posledného uzla na nedávno vytvorený uzol
 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;

Pridajte do stredu

  • Pridelte pamäť a uložte údaje pre nový uzol
  • Prejdite na uzol tesne pred požadovanou pozíciou nového uzla
  • Zmeňte ďalšie ukazovatele tak, aby medzi ne patril nový uzol
 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;

Ako odstrániť z prepojeného zoznamu

Môžete mazať buď od začiatku, konca alebo od konkrétnej pozície.

Odstrániť od začiatku

  • Nasmerujte hlavu na druhý uzol
 head = head->next;

Odstrániť od konca

  • Traverz na druhý posledný prvok
  • Zmeňte jeho nasledujúci ukazovateľ na nulový
 struct node* temp = head; while(temp->next->next!=NULL)( temp = temp->next; ) temp->next = NULL;

Vymazať od stredu

  • Prejdite na prvok pred prvkom, ktorý sa má vymazať
  • Zmenou ďalších ukazovateľov vylúčite uzol z reťazca
 for(int i=2; inext!=NULL) ( temp = temp->next; ) ) temp->next = temp->next->next;

Implementácia operácií LinkedList v Pythone, Jave, C a 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); )

Zaujímavé články...