Propojené operace se seznamem: Posouvání, vkládání a mazání

V tomto kurzu se naučíte různé operace na propojeném seznamu. Rovněž najdete implementaci operací spojených se seznamy v C / C ++, Pythonu a Javě.

Nyní, když jste pochopili základní pojmy za propojeným seznamem a jejich typy, je čas se ponořit do běžných operací, které lze provést.

Dva důležité body k zapamatování:

  • head ukazuje na první uzel propojeného seznamu
  • next pointer of the last node is NULL, so if the next current node is NULL, we have reach the end of the linked list.

Ve všech příkladech budeme předpokládat, že propojený seznam má tři uzly 1 --->2 --->3se strukturou uzlů, jak je uvedeno níže:

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

Jak procházet propojeným seznamem

Zobrazení obsahu propojeného seznamu je velmi jednoduché. Pohybujeme dočasným uzlem na další a zobrazujeme jeho obsah.

Když je temp NULL, víme, že jsme dosáhli konce propojeného seznamu, abychom se dostali ze smyčky while.

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

Výstupem tohoto programu bude:

 Prvky seznamu jsou - 1 ---> 2 ---> 3 --->

Jak přidat prvky do propojeného seznamu

Můžete přidat prvky na začátek, střed nebo konec propojeného seznamu.

Přidejte na začátek

  • Přidělte paměť novému uzlu
  • Uložení dat
  • Změňte další nový uzel tak, aby směřoval k hlavě
  • Změňte hlavu tak, aby ukazovala na nedávno vytvořený uzel
 struct node *newNode; newNode = malloc(sizeof(struct node)); newNode->data = 4; newNode->next = head; head = newNode;

Přidat na konec

  • Přidělte paměť novému uzlu
  • Uložení dat
  • Přejít na poslední uzel
  • Změnit další z posledního uzlu na nedávno vytvořený uzel
 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;

Přidejte do středu

  • Přidělte paměť a uložte data pro nový uzel
  • Najeďte na uzel těsně před požadovanou pozicí nového uzlu
  • Změňte další ukazatele, abyste mezi ně zahrnuli nový uzel
 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;

Jak odstranit z propojeného seznamu

Můžete mazat buď od začátku, konce nebo z určité pozice.

Smazat od začátku

  • Namiřte hlavu na druhý uzel
 head = head->next;

Smazat od konce

  • Traverz na druhý poslední prvek
  • Změňte jeho další ukazatel na null
 struct node* temp = head; while(temp->next->next!=NULL)( temp = temp->next; ) temp->next = NULL;

Smazat ze středu

  • Přejděte k prvku před prvkem, který má být odstraněn
  • Změňte další ukazatele, abyste vyloučili uzel z řetězce
 for(int i=2; inext!=NULL) ( temp = temp->next; ) ) temp->next = temp->next->next;

Implementace operací LinkedList v Pythonu, Javě, 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); )

Zajímavé články...