单链表结点中只有一个指向其后继的指针，使得单链表只能从前往后依次遍历。要访问某个结点的前驱(插入、删除操作时)，只能从头开始遍历，访问前驱的时间复杂度为 O(n)。
为了克服单链表的这个缺点，引入了双链表，双链表结点中有两个指针prior和next，分别指向其直接前驱和直接后继。

双链表的主要特性

双向遍历由于每个节点都有前后两个指针，因此可以在列表中双向遍历，无需像单链表那样只能从头节点开始向前遍历。
插入与删除的便捷性：在双链表中插入或删除一个节点时，只需改变相应节点的前后节点的指针指向即可，操作相对简单高效。

数据结构

data：数据域，也是节点的值
prior：指针域，指向前一个结点的指针
next：指针域，指向下一个结点的指针

#include <stdio.h>
#include <stdlib.h>
#define ElemType int
typedef struct DNode {
  int data; // 数据
  struct DNode *prior, *next; // 前驱和后继指针
} DNode, *DLinkList;
pTemp = (DNode *)malloc(sizeof(DNode));
pTemp->data = x;
pTemp->next = pHead->next;
pTemp->prior = pHea
// 完整代码：https://totuma.cn

链表结构

💡双链表在单链表结点中增加了一个指向其前驱的指针prior ，因此双链表的按值查找和按位查找的操作与单链表的相同。但双链表在插入和删除操作的实现上，与单链表有着较大的不同。这是因为“链”变化时也需要对指针 prior 做出修改，其关键是保证在修改的过程中不断链。 此外,双链表可以很方便地找到当前结点的前驱，因此，插入、除操作的时间复杂度仅为 O(1)。

双链表的基本操作实现

单链表的节点在需要时动态分配内存，这意味着不需要像数组那样在创建时预先分配一大片连续内存。因此，单链表在内存使用上更加灵活，可以有效应对内存碎片和动态增长的问题。

由于链表节点是在需要时分配的，可以避免数组因初始化大小不确定而造成的内存浪费。例如，如果数组大小初始化过大，未使用的部分将浪费内存；若初始化过小，则可能需要频繁重新分配和复制。

每个节点需要一个指针域来存储对下一个节点的引用，这意味着相比于数组，单链表在每个节点上都会有额外的内存开销。对于存储小数据的场景，这个开销相对较大，可能导致内存利用率下降。

按位序插入结点

该函数用于在双向链表中按指定位置插入一个新元素。(注意区分位置和下标：位置从1开始，下标从0开始)

在位置 i 插入元素 e，其中 i=1 表示插入到表头，i=length+1 表示插入到表尾。

重点注意下链表为空和不为空时的处理逻辑

插入时链表空和不空时的区别

按位序插入结点 | 可视化完整可视化

2.3 双链表详解 - 线性表教程使用动画可视化你的代码

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

在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)

按位序删除结点

该函数用于按位序删除节点的功能。具体来说，当参数 i 为 1 时，删除链表的 头节点；当 i 等于链表长度时，删除链表的 尾节点。

重点注意下链表为空和不为空时的处理逻辑

删除时链表空和不空时的区别

按位序删除结点 | 可视化完整可视化

2.3 双链表详解 - 线性表教程使用动画可视化你的代码

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

在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)