Saistītās saraksta darbības: pārvietošana, ievietošana un dzēšana

Šajā apmācībā jūs uzzināsiet dažādas darbības saistītajā sarakstā. Jūs atradīsit arī saistīto sarakstu darbību ieviešanu C / C ++, Python un Java.

Tagad, kad esat guvis izpratni par saistītā saraksta pamatjēdzieniem un to veidiem, ir pienācis laiks ienirt kopīgajās darbībās, kuras var veikt.

Divi svarīgi punkti, kas jāatceras:

  • galva norāda uz saistītā saraksta pirmo mezglu
  • nākamais pēdējā mezgla rādītājs ir NULL, tādēļ, ja nākamais pašreizējais mezgls ir NULL, mēs esam sasnieguši saistītā saraksta beigas.

Visos piemēros mēs pieņemsim, ka saistītajā sarakstā ir trīs mezgli 1 --->2 --->3ar mezglu struktūru, kā norādīts zemāk:

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

Kā šķērsot saistīto sarakstu

Saistītā saraksta satura parādīšana ir ļoti vienkārša. Mēs turpinām pārvietot temp mezglu uz nākamo un parādīt tā saturu.

Kad temperatūra ir NULL, mēs zinām, ka esam sasnieguši saistītā saraksta beigas, tāpēc izkļūstam no while cikla.

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

Šīs programmas rezultāts būs:

 Saraksta elementi ir - 1 ---> 2 ---> 3 --->

Kā pievienot elementus saistītajam sarakstam

Elementus var pievienot saistītā saraksta sākumam, vidum vai beigām.

Pievienojiet sākumam

  • Piešķiriet atmiņu jaunam mezglam
  • Saglabāt datus
  • Mainiet nākamo jauno mezglu uz punktu pret galvu
  • Mainiet galvu uz punktu nesen izveidotam mezglam
 struct node *newNode; newNode = malloc(sizeof(struct node)); newNode->data = 4; newNode->next = head; head = newNode;

Pievienojiet beigām

  • Piešķiriet atmiņu jaunam mezglam
  • Saglabāt datus
  • Pārvietot uz pēdējo mezglu
  • Mainīt nākamo no pēdējā mezgla uz nesen izveidoto mezglu
 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;

Pievienojiet vidējam

  • Piešķiriet atmiņu un saglabājiet datus jaunajam mezglam
  • Pārvietojieties uz mezglu tieši pirms vajadzīgā jaunā mezgla stāvokļa
  • Mainiet nākamos rādītājus, lai starp tiem iekļautu jaunu mezglu
 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;

Kā izdzēst no saistītā saraksta

Dzēst var vai nu no sākuma, beigām vai no noteiktas pozīcijas.

Dzēst no sākuma

  • Virziet galvu uz otro mezglu
 head = head->next;

Dzēst no beigām

  • Traverss uz otro pēdējo elementu
  • Mainiet nākamo rādītāju uz nulli
 struct node* temp = head; while(temp->next->next!=NULL)( temp = temp->next; ) temp->next = NULL;

Dzēst no vidus

  • Pārejiet uz elementu pirms dzēšamā elementa
  • Mainiet nākamos rādītājus, lai mezglu izslēgtu no ķēdes
 for(int i=2; inext!=NULL) ( temp = temp->next; ) ) temp->next = temp->next->next;

LinkedList operāciju ieviešana Python, Java, C un 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); )

Interesanti raksti...