Animation einer doppelt verketteten Liste (mit Kopfknoten)

在双向链表中插入新节点与在链表中插入新节点非常相似。维护前一个节点的链接需要一些额外的工作。可以通过四种方式将节点插入双向链表：

在DLL的前面。
在两个节点之间
- 在给定节点之后。
- 在给定节点之前。
在 DLL 的末尾。

在双向链表的前面添加一个节点：

新节点始终添加到给定链表的头之前。该任务可以通过以下 5 个步骤来执行：

首先，分配一个新节点（例如 new_node ）。
现在将所需的数据放入新节点中。
使new_node 的next 指向双向链表的当前头。
使当前头的前一个指向 new_node 。
最后，将 head 指向 new_node 。

插图：

请参见下图，其中 E 被插入到双向链表的开头。

dll_add_front

下面是在链表前面插入节点的5个步骤的实现：

C

                
                  
                      // Given a reference (pointer to pointer) to the head
// of a list and an int, inserts a new node
// on the front of the list.
void push(struct Node** head_ref, int new_data)
{
    // 1. allocate node
    struct Node* new_node
        = (struct Node*)malloc(sizeof(struct Node));
 
    // 2. put in the data
    new_node->data = new_data;
 
    // 3. Make next of new node as head and previous as NULL
    new_node->next = (*head_ref);
    new_node->prev = NULL;
 
    // 4. change prev of head node to new node
    if ((*head_ref) != NULL)
        (*head_ref)->prev = new_node;
 
    // 5. move the head to point to the new node
    (*head_ref) = new_node;
}

                    

                
              

C++

                
                  
                      // Given a reference (pointer to pointer) to the head 
// of a list and an int, inserts a new node 
// on the front of the list.
void push(Node** head_ref, int new_data)
{
    // 1. allocate node
    Node* new_node = new Node();
 
    // 2. put in the data
    new_node->data = new_data;
 
    // 3. Make next of new node as head
    // and previous as NULL
    new_node->next = (*head_ref);
    new_node->prev = NULL;
 
    // 4. change prev of head node to new node
    if ((*head_ref) != NULL)
        (*head_ref)->prev = new_node;
 
    // 5. move the head to point to the new node
    (*head_ref) = new_node;
}
 
// This code is contributed by shivanisinghss2110

                    

                
              

Java

                
                  
                      // 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;
}

                    

                
              

Python3

                
                      # Adding a node at the front of the list
def push(self, new_data):
 
    # 1 & 2: Allocate the Node & Put in the data
    new_node = Node(data=new_data)
 
    # 3. Make next of new node as head and previous as NULL
    new_node.next = self.head
                          
    new_node.prev = None
 
    # 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
 
# This code is contributed by jatinreaper

C#

                
                  
                      // 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 code is contributed by aashish1995

                    

                
              

Javascript

                
                  
                      // Adding a node at the front of the list
function push(new_data)
{
    // 1. allocate node 
    // 2. put in the data
    let 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 code is contributed by saurabh_jaiswal.

                    

                
              

时间复杂度： O(1)
辅助空间： O(1)

在两个节点之间添加一个节点：

又分为以下两部分：

在双向链表中的给定节点之后添加一个节点：

我们将获得一个指向节点的指针 prev_node ，并且新节点将插入到给定节点之后。这可以通过以下 6 个步骤来完成：

首先创建一个新节点（例如 new_node ）。
现在将数据插入新节点。
将new_node 的下一个指向 prev_node 的下一个。
将prev_node 的下一个指向 new_node 。
将new_node 的前一个指向 prev_node 。
将新节点的前一个指针更改为 new_node 。

插图：

请参见下图，其中“ E ”被插入到“ B ”之后。

dll_add_middle

下面是在链表中给定节点之后插入节点的 7 个步骤的实现：

C

                
                  
                      // Given a node as prev_node, insert a new node 
// after the given node
                          
void insertAfter(struct Node* prev_node, int new_data)
{
    // Check if the given prev_node is NULL
    if (prev_node == NULL) {
        printf("the given previous node cannot be NULL");
        return;
    }
 
    // 1. allocate new node
    struct Node* new_node
        = (struct Node*)malloc(sizeof(struct Node));
 
    // 2. put in the data
    new_node->data = new_data;
 
    // 3. Make next of new node as next of prev_node
    new_node->next = prev_node->next;
 
    // 4. Make the next of prev_node as new_node
    prev_node->next = new_node;
 
    // 5. Make prev_node as previous of new_node
    new_node->prev = prev_node;
 
    // 6. Change previous of new_node's next node
    if (new_node->next != NULL)
                          
        new_node->next->prev = new_node;
}

                    

                
              

C++

                
                  
                      // Given a node as prev_node, insert a new node 
// after the given node
                          
void insertAfter(Node* prev_node, int
                            new_data)
{
    // Check if the given prev_node is NULL
    if (prev_node == NULL) {
        cout << "the given previous node cannot be NULL";
                          
        return;
    }
 
    // 1. allocate new node
    Node* new_node = new Node();
 
    // 2. put in the data
    new_node->data = new_data;
 
    // 3. Make next of new node as next of prev_node
    new_node->next = prev_node->next;
 
    // 4. Make the next of prev_node as new_node
    prev_node->next = new_node;
 
    // 5. Make prev_node as previous of new_node
    new_node->prev = prev_node;
 
    // 6. Change previous of new_node's next node
    if (new_node->next != NULL)
                          
        new_node->next->prev = new_node;
}
 
// This code is contributed by shivanisinghss2110.

                    

                
              

Java

                
                  
                      // Given a node as prev_node, insert a new node 
// after the given node
                          
public void InsertAfter(Node prev_Node, int new_data)
{
    // Check if the given prev_node is NULL
    if
                            (prev_Node == null) {
        System.out.println(
            "The given previous node cannot be NULL ");
        return;
    }
 
    // 1. allocate node
    // 2. put in the data 
    Node new_node = new Node(new_data);
 
    // 3. Make next of new node as next of prev_node
    new_node.next = prev_Node.next;
 
    // 4. Make the next of prev_node as new_node
    prev_Node.next = new_node;
 
    // 5. Make prev_node as previous of new_node
    new_node.prev = prev_Node;
 
    // 6. Change previous of new_node's next node
    if
                            (new_node.next != null)
        new_node.next.prev = new_node;
}

                    

                
              

Python3

                
                      # Given a node as prev_node, insert
# a new node after the given node
 
def insertAfter(self, prev_node, new_data):
 
    # Check if the given prev_node is NULL
    if
                            prev_node is None:
        print("This node doesn't exist in DLL")
        return
 
    # 1. allocate node  & 
    # 2. put in the data
    new_node = Node(data=new_data)
 
    # 3. Make next of new node as next of prev_node
    new_node.next = prev_node.next
 
    # 4. Make the next of prev_node as new_node
    prev_node.next = new_node
 
    # 5. Make prev_node as previous of new_node
    new_node.prev = prev_node
 
    # 6. Change previous of new_node's next node
    if
                            new_node.next is not None:
        new_node.next.prev = new_node
 
#  This code is contributed by jatinreaper

C#

                
                  
                      // Given a node as prev_node, insert a new node 
// after the given node
                          
public void InsertAfter(Node prev_Node, int new_data)
{
    // Check if the given prev_node is NULL
    if
                            (prev_Node == null) {
        Console.WriteLine(
            "The given previous node cannot be NULL ");
        return;
    }
 
    // 1. allocate node
    // 2. put in the data
    Node new_node = new Node(new_data);
 
    // 3. Make next of new node as next of prev_node
    new_node.next = prev_Node.next;
 
    // 4. Make the next of prev_node as new_node
    prev_Node.next = new_node;
 
    // 5. Make prev_node as previous of new_node
    new_node.prev = prev_Node;
 
    // 6. Change previous of new_node's next node
    if
                            (new_node.next != null)
        new_node.next.prev = new_node;
}
 
// This code is contributed by aashish1995

                    

                
              

Javascript

                
                  
                      <script>
 
function InsertAfter(prev_Node,new_data)
{
        // Check if the given prev_node is NULL
    if
                            (prev_Node == null) {
        document.write("The given previous node cannot be NULL <br>");
        return;
    }
 
    // 1. allocate node 
    // 2. put in the data
    let new_node = new Node(new_data);
 
    // 3. Make next of new node as next of prev_node
    new_node.next = prev_Node.next;
 
    // 4. Make the next of prev_node as new_node
    prev_Node.next = new_node;
 
    // 5. Make prev_node as previous of new_node
    new_node.prev = prev_Node;
 
    // 6. Change previous of new_node's next node
    if
                            (new_node.next != null)
        new_node.next.prev = new_node;
}
 
 
// This code is contributed by unknown2108
 
</script>

                    

                
              

时间复杂度： O(1)
辅助空间： O(1)

在双向链表中的给定节点之前添加一个节点：

令指向该给定节点的指针为 next_node 。这可以通过以下 6 个步骤来完成。

为新节点分配内存，命名为 new_node 。
将数据放入 new_node 中。
将这个new_node 的前一个指针设置为 next_node 的前一个节点。
将next_node 的前一个指针设置为 new_node 。
将这个new_node 的下一个指针设置为 next_node 。
现在设置new_node 的前一个指针。
- 如果 new_node 的前一个节点不为 NULL，则将该前一个节点的下一个指针设置为 new_node 。
- 否则，如果 new_node 的 prev 为 NULL，则它将成为新的头节点。

插图：

请参见下图，其中“ B ”被插入到“ C ”之前。

下面是上述方法的实现。

C

                
                  
                      // Given a node as prev_node, insert a new node 
// after the given node
                          
void insertBefore(struct Node* next_node, int new_data)
{
    // Check if the given next_node is NULL
    if (next_node == NULL) {
        printf("the given next node cannot be NULL");
                          
        return;
    }
 
    // 1. Allocate new node
    struct Node* new_node
        = (struct Node*)malloc(sizeof(struct Node));
 
    // 2. Put in the data
    new_node->data = new_data;
 
    // 3. Make previous of new node as previous of next_node
    new_node->prev = next_node->prev;
 
    // 4. Make the previous of next_node as new_node
    next_node->prev = new_node;
 
    // 5. Make next_node as next of new_node
    new_node->next = next_node;
 
    // 6. Change next of new_node's previous node
    if (new_node->prev != NULL)
                          
        new_node->prev->next = new_node;
    else
        head = new_node;
}

                    

                
              

C++

                
                  
                      // Given a node as prev_node, insert a new node 
// after the given node
                          
void insertBefore(Node* next_node, int
                            new_data)
{
    // Check if the given next_node is NULL
    if (next_node == NULL) {
        printf("the given next node cannot be NULL");
                          
        return;
    }
 
    // 1. Allocate new node
    Node* new_node = new Node();
 
    // 2. Put in the data
    new_node->data = new_data;
 
    // 3. Make previous of new node as previous of next_node
    new_node->prev = next_node->prev;
 
    // 4. Make the previous of next_node as new_node
    next_node->prev = new_node;
 
    // 5. Make next_node as next of new_node
    new_node->next = next_node;
 
    // 6. Change next of new_node's previous node
    if (new_node->prev != NULL)
                          
        new_node->prev->next = new_node;
    else
        head = new_node;
}

                    

                
              

Java

                
                  
                      // Given a node as prev_node, insert a new node 
// after the given node
                          
public void InsertBefore(Node next_Node, int new_data)
{
    // Check if the given next_node is NULL
    if
                            (next_Node == null) {
        System.out.println(
            "The given next node cannot be NULL ");
                          
        return;
    }
 
    // 1. Allocate node
    // 2. Put in the data 
    Node new_node = new Node(new_data);
 
    // 3. Make previous of new node as previous of prev_node
    new_node.prev = next_Node.prev;
 
    // 4. Make the prev of next_node as new_node
    next_Node.prev = new_node;
 
    // 5. Make next_node as next of new_node
    new_node.next = next_Node;
 
    // 6. Change next of new_node's previous node
    if
                            (new_node.prev != null)
        new_node.prev.next = new_node;
    else
                          
        head = new_node;
}

                    

                
              

Python3

                
                      # Given a node as prev_node, insert
# a new node after the given node
 
def insertAfter(self, next_node, new_data):
 
    # Check if the given next_node is NULL
    if
                            next_node is None:
        print("This node doesn't exist in DLL")
        return
 
    # 1. Allocate node  & 
    # 2. Put in the data
    new_node = Node(data=new_data)
 
    # 3. Make previous of new node as previous of prev_node
    new_node.prev = next_node.prev
 
    # 4. Make the previous of next_node as new_node
    next_node.prev = new_node
 
    # 5. Make next_node as next of new_node
    new_node.next = next_node
 
    # 6. Change next of new_node's previous node
    if
                            new_node.prev is not None:
                          
        new_node.prev.next = new_node
    else:
        head = new_node
 
#  This code is contributed by jatinreaper

C#

                
                  
                      // Given a node as prev_node, insert a new node 
// after the given node
                          
public void InsertAfter(Node next_Node, int new_data)
{
    // Check if the given next_node is NULL
    if
                            (next_Node == null) {
        Console.WriteLine(
            "The given next node cannot be NULL ");
                          
        return;
    }
 
    // 1. Allocate node
    // 2. Put in the data
    Node new_node = new Node(new_data);
 
    // 3. Make previous of new node as previous of next_node
    new_node.prev = next_Node.prev;
 
    // 4. Make the previous of next_node as new_node
    next_Node.prev = new_node;
 
    // 5. Make next_node as next of new_node
    new_node.next = next_Node;
 
    // 6. Change next of new_node's previous node
    if
                            (new_node.prev != null)
        new_node.prev.next = new_node;
    else
                          
        head = new_node;
}
 
// This code is contributed by aashish1995

                    

                
              

Javascript

                
                  
                      <script>
 
function InsertAfter(next_Node,new_data)
{
        // Check if the given next_Node is NULL
    if
                            (next_Node == null) {
        document.write("The given next node cannot be NULL <br>");
        return;
    }
 
    // 1. Allocate node 
    // 2. Put in the data
    let new_node = new Node(new_data);
 
    // 3. Make previous of new node as previous of next_node
    new_node.prev = next_Node.prev;
 
    // 4. Make the previous of next_node as new_node
    next_Node.prev = new_node;
 
    // 5. Make next_node as next of new_node
    new_node.next = next_Node;
 
    // 6. Change next of new_node's previous node
    if
                            (new_node.prev != null)
        new_node.prev.next = new_node;
    else
                          
        head = new_node;
}
 
 
// This code is contributed by unknown2108
 
</script>

                    

                
              

时间复杂度： O(1)
辅助空间： O(1)

在双向链表的末尾添加一个节点：

新节点始终添加在给定链表的最后一个节点之后。这可以通过以下 7 个步骤来完成：

创建一个新节点（例如 new_node ）。
将值放入新节点。
将new_node 的next指针设置为null。
如果链表为空，则将 new_node 作为头。
否则，移动到链表的末尾。
现在使最后一个节点的下一个指针指向 new_node 。
将new_node 的前一个指针更改为链表的最后一个节点。

插图：

请参见下图，其中“ D ”被插入到链表的末尾。

dll_add_end

下面是在链表末尾插入节点的7个步骤的实现：

C

                
                  
                      // Given a reference (pointer to pointer) to the head
// of a DLL and an int, appends a new node at the end
void append(struct Node** head_ref, int new_data)
{
    // 1. allocate node
    struct Node* new_node
        = (struct Node*)malloc(sizeof(struct Node));
 
    struct Node* last = *head_ref; /* used in step 5*/
 
    // 2. put in the data
    new_node->data = new_data;
 
    // 3. This new node is going to be the last node, so
    // make next of it as NULL
    new_node->next = NULL;
 
    // 4. If the Linked List is empty, then make the new
    // node as head
    if (*head_ref == NULL) {
        new_node->prev = NULL;
        *head_ref = new_node;
        return;
    }
 
    // 5. Else traverse till the last node
    while (last->next != NULL)
        last = last->next;
 
    // 6. Change the next of last node
    last->next = new_node;
 
    // 7. Make last node as previous of new node
    new_node->prev = last;
 
    return;
}

                    

                
              

C++

                
                  
                      // Given a reference (pointer to pointer) to the head
// of a DLL and an int, appends a new node at the end
void append(Node** head_ref, int new_data)
{
    // 1. allocate node
    Node* new_node = new Node();
 
    Node* last = *head_ref; /* used in step 5*/
 
    // 2. put in the data
    new_node->data = new_data;
 
    // 3. This new node is going to be the last node, so
    // make next of it as NULL
    new_node->next = NULL;
 
    // 4. If the Linked List is empty, then make the new
    // node as head
    if (*head_ref == NULL) {
        new_node->prev = NULL;
        *head_ref = new_node;
        return;
    }
 
    // 5. Else traverse till the last node
    while (last->next != NULL)
        last = last->next;
 
    // 6. Change the next of last node
    last->next = new_node;
 
    // 7. Make last node as previous of new node
    new_node->prev = last;
 
    return;
}
 
// This code is contributed by shivanisinghss2110

                    

                
              

Java

                
                  
                      // Add a node at the end of the list
void append(int new_data)
{
    // 1. allocate node
    // 2. put in the data
    Node new_node = new Node(new_data);
 
    Node last = head; /* used in step 5*/
                          
 
    // 3. This new node is going to be the last node, so
    // make next of it as NULL
    new_node.next = null;
 
    // 4. If the Linked List is empty, then make the new
    // node as head
    if
                            (head == null) {
        new_node.prev = null;
        head = new_node;
        return;
    }
 
    // 5. Else traverse till the last node
    while
                            (last.next != null)
        last = last.next;
 
    // 6. Change the next of last node
    last.next = new_node;
 
    // 7. Make last node as previous of new node
    new_node.prev = last;
}

                    

                
              

Python3

                
                  
                      # Add a node at the end of the DLL
def append(self, new_data):
 
    # 1. allocate node 
    # 2. put in the data
    new_node = Node(data=new_data)
    last = self.head
 
    # 3. This new node is going to be the
    # last node, so make next of it as NULL
    new_node.next = None
 
    # 4. If the Linked List is empty, then
    #  make the new node as head
    if
                            self.head is None:
                          
        new_node.prev = None
        self.head =
                            new_node
        return
 
    # 5. Else traverse till the last node
    while
                            (last.next is not None):
        last = last.next
 
    # 6. Change the next of last node
    last.next = new_node
    # 7. Make last node as previous of new node */
    new_node.prev = last
 
#  This code is contributed by jatinreaper

                    

                
              

C#

                
                  
                      // Add a node at the end of the list
void append(int new_data)
{
    // 1. allocate node
    // 2. put in the data
    Node new_node = new Node(new_data);
 
    Node last = head; /* used in step 5*/
                          
 
    // 3. This new node is going
    //  to be the last node, so
    // make next of it as NULL
    new_node.next = null;
 
    // 4. If the Linked List is empty,
    // then make the new node as head
    if
                            (head == null) {
        new_node.prev = null;
        head = new_node;
        return;
    }
 
    // 5. Else traverse till the last node
    while
                            (last.next != null)
        last = last.next;
 
    // 6. Change the next of last node
    last.next = new_node;
 
    // 7. Make last node as previous of new node
    new_node.prev = last;
}
 
// This code is contributed by shivanisinghss2110

                    

                
              

Javascript

                
                  
                      <script>
// Add a node at the end of the list
function append(new_data)
{
    /* 1. allocate node 
     * 2. put in the data */
    var
                            new_node = new Node(new_data);
 
    var
                            last = head; /* used in step 5*/
                          
 
    /* 3. This new node is going to be the last node, so
     * make next of it as NULL*/
    new_node.next = null;
 
    /* 4. If the Linked List is empty, then make the new
     * node as head */
    if
                            (head == null) {
        new_node.prev = null;
        head = new_node;
        return;
    }
 
    /* 5. Else traverse till the last node */
    while
                            (last.next != null)
        last = last.next;
 
    /* 6. Change the next of last node */
    last.next = new_node;
 
    /* 7. Make last node as previous of new node */
    new_node.prev = last;
}
 
// This code is contributed by Rajput-Ji 
</script>

                    

                
              

时间复杂度： O(n)
辅助空间： O(1)