先决条件： 双链接列表集1 |介绍和插入
null
编写一个函数来删除双链接列表中的给定节点。 原始双链表
![图片[1]-删除双链接列表中的节点-yiteyi-C++库](https://media.geeksforgeeks.org/wp-content/uploads/Delete_lincked_list.jpg)
方法： 删除双链接列表中的节点可分为三大类：
- 删除头部节点后。
![图片[2]-删除双链接列表中的节点-yiteyi-C++库](https://media.geeksforgeeks.org/wp-content/uploads/20200318143640/linked11.png)
- 删除中间节点后。
![图片[3]-删除双链接列表中的节点-yiteyi-C++库](https://media.geeksforgeeks.org/wp-content/uploads/Delete_lincked_list3.jpg)
- 删除最后一个节点后。
![图片[4]-删除双链接列表中的节点-yiteyi-C++库](https://media.geeksforgeeks.org/wp-content/uploads/Delete_lincked_list4.jpg)
如果要删除的节点的指针和头部指针已知，则上述三种情况都可以分两步处理。
- 如果要删除的节点是head节点，则将下一个节点设为head。
- 如果删除了节点，请连接已删除节点的下一个和上一个节点。
![图片[5]-删除双链接列表中的节点-yiteyi-C++库](https://media.geeksforgeeks.org/wp-content/uploads/20200318150826/ezgif.com-gif-maker1.gif)
算法
- 允许删除要删除的节点 德尔 .
- 如果要删除的节点是头节点，则将头指针更改为下一个当前头。
if headnode == del then headnode = del.nextNode
- 设置 下一个 之前的 德尔 ，如果之前 德尔 存在。
if del.nextNode != none del.nextNode.previousNode = del.previousNode
- 设置 上 旁边的 德尔 ，如果紧挨着 德尔 存在。
if del.previousNode != none del.previousNode.nextNode = del.next
C++
// C++ program to delete a node from // Doubly Linked List #include <bits/stdc++.h> using namespace std; /* a node of the doubly linked list */ class Node { public : int data; Node* next; Node* prev; }; /* Function to delete a node in a Doubly Linked List. head_ref --> pointer to head node pointer. del --> pointer to node to be deleted. */ void deleteNode(Node** head_ref, Node* del) { /* base case */ if (*head_ref == NULL || del == NULL) return ; /* If node to be deleted is head node */ if (*head_ref == del) *head_ref = del->next; /* Change next only if node to be deleted is NOT the last node */ if (del->next != NULL) del->next->prev = del->prev; /* Change prev only if node to be deleted is NOT the first node */ if (del->prev != NULL) del->prev->next = del->next; /* Finally, free the memory occupied by del*/ free (del); return ; } /* UTILITY FUNCTIONS */ /* Function to insert a node at the beginning of the Doubly Linked List */ void push(Node** head_ref, int new_data) { /* allocate node */ Node* new_node = new Node(); /* put in the data */ new_node->data = new_data; /* since we are adding at the beginning, prev is always NULL */ new_node->prev = NULL; /* link the old list off the new node */ new_node->next = (*head_ref); /* change prev of head node to new node */ if ((*head_ref) != NULL) (*head_ref)->prev = new_node; /* move the head to point to the new node */ (*head_ref) = new_node; } /* Function to print nodes in a given doubly linked list This function is same as printList() of singly linked list */ void printList(Node* node) { while (node != NULL) { cout << node->data << " " ; node = node->next; } } /* Driver code*/ int main() { /* Start with the empty list */ Node* head = NULL; /* Let us create the doubly linked list 10<->8<->4<->2 */ push(&head, 2); push(&head, 4); push(&head, 8); push(&head, 10); cout << "Original Linked list " ; printList(head); /* delete nodes from the doubly linked list */ deleteNode(&head, head); /*delete first node*/ deleteNode(&head, head->next); /*delete middle node*/ deleteNode(&head, head->next); /*delete last node*/ /* Modified linked list will be NULL<-8->NULL */ cout << "Modified Linked list " ; printList(head); return 0; } // This code is contributed by rathbhupendra |
C
#include <stdio.h> #include <stdlib.h> /* a node of the doubly linked list */ struct Node { int data; struct Node* next; struct Node* prev; }; /* Function to delete a node in a Doubly Linked List. head_ref --> pointer to head node pointer. del --> pointer to node to be deleted. */ void deleteNode( struct Node** head_ref, struct Node* del) { /* base case */ if (*head_ref == NULL || del == NULL) return ; /* If node to be deleted is head node */ if (*head_ref == del) *head_ref = del->next; /* Change next only if node to be deleted is NOT the last node */ if (del->next != NULL) del->next->prev = del->prev; /* Change prev only if node to be deleted is NOT the first node */ if (del->prev != NULL) del->prev->next = del->next; /* Finally, free the memory occupied by del*/ free (del); return ; } /* UTILITY FUNCTIONS */ /* Function to insert a node at the beginning of the Doubly Linked List */ void push( struct Node** head_ref, int new_data) { /* allocate node */ struct Node* new_node = ( struct Node*) malloc ( sizeof ( struct Node)); /* put in the data */ new_node->data = new_data; /* since we are adding at the beginning, prev is always NULL */ new_node->prev = NULL; /* link the old list off the new node */ new_node->next = (*head_ref); /* change prev of head node to new node */ if ((*head_ref) != NULL) (*head_ref)->prev = new_node; /* move the head to point to the new node */ (*head_ref) = new_node; } /* Function to print nodes in a given doubly linked list This function is same as printList() of singly linked list */ void printList( struct Node* node) { while (node != NULL) { printf ( "%d " , node->data); node = node->next; } } /* Driver program to test above functions*/ int main() { /* Start with the empty list */ struct Node* head = NULL; /* Let us create the doubly linked list 10<->8<->4<->2 */ push(&head, 2); push(&head, 4); push(&head, 8); push(&head, 10); printf ( " Original Linked list " ); printList(head); /* delete nodes from the doubly linked list */ deleteNode(&head, head); /*delete first node*/ deleteNode(&head, head->next); /*delete middle node*/ deleteNode(&head, head->next); /*delete last node*/ /* Modified linked list will be NULL<-8->NULL */ printf ( " Modified Linked list " ); printList(head); getchar (); } |
JAVA
// Java program to delete a node from // Doubly Linked List // Class for Doubly Linked List public class DLL { Node head; // head of list /* Doubly Linked list Node*/ class Node { int data; Node prev; Node next; // Constructor to create a new node // next and prev is by default initialized // as null Node( int d) { data = d; } } // Adding a node at the front of the list public void push( int new_data) { // 1. allocate node // 2. put in the data Node new_Node = new Node(new_data); // 3. Make next of new node as head // and previous as NULL new_Node.next = head; new_Node.prev = null ; // 4. change prev of head node to new node if (head != null ) head.prev = new_Node; // 5. move the head to point to the new node head = new_Node; } // This function prints contents of linked list // starting from the given node public void printlist(Node node) { Node last = null ; while (node != null ) { System.out.print(node.data + " " ); last = node; node = node.next; } System.out.println(); } // Function to delete a node in a Doubly Linked List. // head_ref --> pointer to head node pointer. // del --> data of node to be deleted. void deleteNode(Node del) { // Base case if (head == null || del == null ) { return ; } // If node to be deleted is head node if (head == del) { head = del.next; } // Change next only if node to be deleted // is NOT the last node if (del.next != null ) { del.next.prev = del.prev; } // Change prev only if node to be deleted // is NOT the first node if (del.prev != null ) { del.prev.next = del.next; } // Finally, free the memory occupied by del return ; } // Driver Code public static void main(String[] args) { // Start with the empty list DLL dll = new DLL(); // Insert 2. So linked list becomes 2->NULL dll.push( 2 ); // Insert 4. So linked list becomes 4->2->NULL dll.push( 4 ); // Insert 8. So linked list becomes 8->4->2->NULL dll.push( 8 ); // Insert 10. So linked list becomes 10->8->4->2->NULL dll.push( 10 ); System.out.print( "Created DLL is: " ); dll.printlist(dll.head); // Deleting first node dll.deleteNode(dll.head); // List after deleting first node // 8->4->2 System.out.print( "List after deleting first node: " ); dll.printlist(dll.head); // Deleting middle node from 8->4->2 dll.deleteNode(dll.head.next); System.out.print( "List after Deleting middle node: " ); dll.printlist(dll.head); } } |
蟒蛇3
# Program to delete a node in a doubly-linked list # for Garbage collection import gc # A node of the doubly linked list class Node: # Constructor to create a new node def __init__( self , data): self .data = data self . next = None self .prev = None class DoublyLinkedList: # Constructor for empty Doubly Linked List def __init__( self ): self .head = None # Function to delete a node in a Doubly Linked List. # head_ref --> pointer to head node pointer. # dele --> pointer to node to be deleted def deleteNode( self , dele): # Base Case if self .head is None or dele is None : return # If node to be deleted is head node if self .head = = dele: self .head = dele. next # Change next only if node to be deleted is NOT # the last node if dele. next is not None : dele. next .prev = dele.prev # Change prev only if node to be deleted is NOT # the first node if dele.prev is not None : dele.prev. next = dele. next # Finally, free the memory occupied by dele # Call python garbage collector gc.collect() # Given a reference to the head of a list and an # integer, inserts a new node on the front of list def push( self , new_data): # 1. Allocates node # 2. Put the data in it new_node = Node(new_data) # 3. Make next of new node as head and # previous as None (already None) new_node. next = self .head # 4. change prev of head node to new_node if self .head is not None : self .head.prev = new_node # 5. move the head to point to the new node self .head = new_node def printList( self , node): while (node is not None ): print (node.data,end = ' ' ) node = node. next # Driver program to test the above functions # Start with empty list dll = DoublyLinkedList() # Let us create the doubly linked list 10<->8<->4<->2 dll.push( 2 ); dll.push( 4 ); dll.push( 8 ); dll.push( 10 ); print ( " Original Linked List" ,end = ' ' ) dll.printList(dll.head) # delete nodes from doubly linked list dll.deleteNode(dll.head) dll.deleteNode(dll.head. next ) dll.deleteNode(dll.head. next ) # Modified linked list will be NULL<-8->NULL print ( " Modified Linked List" ,end = ' ' ) dll.printList(dll.head) # This code is contributed by Nikhil Kumar Singh(nickzuck_007) |
C#
// C# program to delete a node from // Doubly Linked List using System; // Class for Doubly Linked List public class DLL { Node head; // head of list /* Doubly Linked list Node*/ public class Node { public int data; public Node prev; public Node next; // Constructor to create a new node // next and prev is by default // initialized as null public Node( int d) { data = d; } } // Adding a node at the front of the list public void push( int new_data) { // 1. allocate node // 2. put in the data Node new_Node = new Node(new_data); // 3. Make next of new node as head // and previous as NULL new_Node.next = head; new_Node.prev = null ; // 4. change prev of head node to new node if (head != null ) head.prev = new_Node; // 5. move the head to point to the new node head = new_Node; } // This function prints contents of linked list // starting from the given node public void printlist(Node node) { while (node != null ) { Console.Write(node.data + " " ); node = node.next; } Console.WriteLine(); } // Function to delete a node in a Doubly Linked List. // head_ref --> pointer to head node pointer. // del --> data of node to be deleted. void deleteNode(Node del) { // Base case if (head == null || del == null ) { return ; } // If node to be deleted is head node if (head == del) { head = del.next; } // Change next only if node to be deleted // is NOT the last node if (del.next != null ) { del.next.prev = del.prev; } // Change prev only if node to be deleted // is NOT the first node if (del.prev != null ) { del.prev.next = del.next; } // Finally, free the memory occupied by del return ; } // Driver Code public static void Main() { // Start with the empty list DLL dll = new DLL(); // Insert 2. So linked list becomes 2->NULL dll.push(2); // Insert 4. So linked list becomes 4->2->NULL dll.push(4); // Insert 8. So linked list becomes 8->4->2->NULL dll.push(8); // Insert 10. So linked list becomes 10->8->4->2->NULL dll.push(10); Console.Write( "Created DLL is: " ); dll.printlist(dll.head); // Deleting first node dll.deleteNode(dll.head); // List after deleting first node // 8->4->2 Console.Write( "List after deleting first node: " ); dll.printlist(dll.head); // Deleting middle node from 8->4->2 dll.deleteNode(dll.head.next); Console.Write( "List after Deleting middle node: " ); dll.printlist(dll.head); } } // This code is contributed by PrinciRaj1992 |
Javascript
<script> // Javascript program to delete a node from // Doubly Linked List // Class for Doubly Linked List var head; // head of list /* Doubly Linked list Node */ class Node { // Constructor to create a new node // next and prev is by default initialized // as null constructor(val) { this .data = val; this .prev = null ; this .next = null ; } } // Adding a node at the front of the list function push(new_data) { // 1. allocate node // 2. put in the data new_Node = new Node(new_data); // 3. Make next of new node as head // and previous as NULL new_Node.next = head; new_Node.prev = null ; // 4. change prev of head node to new node if (head != null ) head.prev = new_Node; // 5. move the head to point to the new node head = new_Node; } // This function prints contents of linked list // starting from the given node function printlist( node) { last = null ; while (node != null ) { document.write(node.data + " " ); last = node; node = node.next; } document.write( "<br/>" ); } // Function to delete a node in a Doubly Linked List. // head_ref --> pointer to head node pointer. // del --> data of node to be deleted. function deleteNode( del) { // Base case if (head == null || del == null ) { return ; } // If node to be deleted is head node if (head == del) { head = del.next; } // Change next only if node to be deleted // is NOT the last node if (del.next != null ) { del.next.prev = del.prev; } // Change prev only if node to be deleted // is NOT the first node if (del.prev != null ) { del.prev.next = del.next; } // Finally, free the memory occupied by del return ; } // Driver Code // Start with the empty list // Insert 2. So linked list becomes 2->NULL push(2); // Insert 4. So linked list becomes 4->2->NULL push(4); // Insert 8. So linked list becomes 8->4->2->NULL push(8); // Insert 10. So linked list becomes 10->8->4->2->NULL push(10); document.write( "Created DLL is: " ); printlist(head); // Deleting first node deleteNode(head); deleteNode(head.next); deleteNode(head.next); document.write( "Modified Linked list: " ); printlist(head); // This code is contributed by todaysgaurav </script> |
输出：
Original Linked list 10 8 4 2 Modified Linked list 8
复杂性分析：
- 时间复杂性： O（1）。 由于不需要遍历链表，因此时间复杂度是恒定的。
- 空间复杂性： O（1）。 由于不需要额外的空间，因此空间复杂度是恒定的。
如果您发现上述任何代码/算法不正确，请写下评论，或者找到更好的方法来解决相同的问题。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
