12. Python 程序在双向链表的中间插入一个新节点。

17 Mar 2025 | 4 分钟阅读

在这个程序中，我们创建一个双向链表，并在链表的中间插入一个新节点。如果链表为空，则 head 和 tail 都将指向新节点。如果链表不为空，那么我们将计算链表的大小，并将其除以 2 以获得链表的中点，新节点需要在该中点插入。

Python program to insert a new node at the middle of the Doubly Linked List

考虑上面的图；需要将一个新节点添加到列表的中间。首先，我们计算大小，在本例中为 4。因此，为了获得中点，我们将其除以 2 并将其存储在变量 mid 中。节点 current 将指向 head。首先，我们遍历列表，直到 current 指向中间位置。定义另一个节点 temp，它指向 current 节点之后的节点。在 current 和 temp 之间插入新节点

算法

定义一个 Node 类，它表示列表中的一个节点。它将有三个属性：数据、previous 指向前一个节点，以及 next 指向下一个节点。
为创建双向链表定义另一个类，它有两个节点：head 和 tail。最初，head 和 tail 将指向 null。
addNode() 将向列表中添加节点。

它首先检查头节点是否为 null，然后将节点作为头节点插入。
头节点和尾节点都将指向新添加的节点。
头节点的前一个指针将指向 null，尾节点的下一个指针将指向 null。
如果头节点不为 null，则新节点将插入到列表的末尾，使得新节点的前一个指针将指向尾节点。
新节点将成为新的尾节点。尾节点的下一个指针将指向 null。

a. addInMid() 将节点添加到列表的中间

它首先检查 head 是否为 null（空列表），然后它将节点插入为 head。
头节点和尾节点都将指向新添加的节点。
如果列表不为空，那么我们计算大小并将其除以 2 以获得中点。
定义节点 current，它将指向 head 并遍历列表，直到 current 指向中间节点。
定义另一个节点 temp，它将指向 current 的下一个节点。
新节点将插入在 current 之后和 temp 之前，使得 current 指向新节点，新节点指向 temp。

a. display() 将显示列表中存在的所有节点。

定义一个新节点“current”，它将指向头节点。
打印 current.data 直到 current 指向 null。
在每次迭代中，current 将指向列表中的下一个节点。

程序

#Represent a node of doubly linked list  
class Node:  
    def __init__(self,data):  
        self.data = data;  
        self.previous = None;  
        self.next = None;  
          
class InsertMid:  
    #Represent the head and tail of the doubly linked list  
    def __init__(self):  
        self.head = None;  
        self.tail = None;  
        self.size = 0;  
          
    #addNode() will add a node to the list  
    def addNode(self, data):  
        #Create a new node  
        newNode = Node(data);  
          
        #If list is empty  
        if(self.head == None):  
            #Both head and tail will point to newNode  
            self.head = self.tail = newNode;  
            #head's previous will point to None  
            self.head.previous = None;  
            #tail's next will point to None, as it is the last node of the list  
            self.tail.next = None;  
        else:  
            #newNode will be added after tail such that tail's next will point to newNode  
            self.tail.next = newNode;  
            #newNode's previous will point to tail  
            newNode.previous = self.tail;  
            #newNode will become new tail  
            self.tail = newNode;  
            #As it is last node, tail's next will point to None  
            self.tail.next = None;  
        #Size will count the number of nodes present in the list  
        self.size = self.size + 1;  
          
    #addInMid() will add a node to the middle of the list  
    def addInMid(self, data):  
        #Create a new node  
        newNode = Node(data);  
          
        #If list is empty  
        if(self.head == None):  
            #Both head and tail will point to newNode  
            self.head = self.tail = newNode;  
            #head's previous will point to None  
            self.head.previous = None;  
            #tail's next point to None, as it is the last node of the list  
            self.tail.next = None;  
        else:  
            #current will point to head  
            current = self.head;  
              
            #Store the mid position of the list  
            mid = (self.size//2) if(self.size % 2 == 0)  else ((self.size+1)//2);  
              
            #Iterate through list till current points to mid position  
            for i in range(1, mid):  
                current = current.next;  
                  
            #Node temp will point to node next to current  
            temp = current.next;  
            temp.previous = current;  
              
            #newNode will be added between current and temp  
            current.next = newNode;  
            newNode.previous = current;  
            newNode.next = temp;  
            temp.previous = newNode;  
        self.size = self.size + 1;  
              
    #display() will print out the nodes of the list  
    def display(self):  
        #Node current will point to head  
        current = self.head;  
        if(self.head == None):  
            print("List is empty");  
            return;  
        while(current != None):  
            #Prints each node by incrementing pointer.  
            print(current.data),  
            current = current.next;  
              
        print();  
          
dList = InsertMid();  
#Add nodes to the list  
dList.addNode(1);  
dList.addNode(2);  
   
print("Original list: ");  
dList.display();  
   
#Adding node '3' in the middle  
dList.addInMid(3);  
print( "Updated List: ");  
dList.display();  
   
#Adding node '4' in the middle  
dList.addInMid(4);  
print("Updated List: ");  
dList.display();  
   
#Adding node '5' in the middle  
dList.addInMid(5);  
print("Updated List: ");  
dList.display();  

输出

Original list: 
1 2 
Updated List: 
1 3 2 
Updated List: 
1 3 4 2 
Updated List: 
1 3 5 4 2

下一个主题Python 程序

← 上一个下一个 →

12. Python 程序在双向链表的中间插入一个新节点。

算法

程序

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

Python 程序

12. Python 程序在双向链表的中间插入一个新节点。

算法

程序

相关帖子

Python 程序打印区间内的所有素数

Python 程序查找自然数之和

Python 程序打印数组中奇数位置的元素

Python 程序打印数组的元素

Python 程序创建 n 个节点的双向链表并计算节点数

Python 程序检查阿姆斯特朗数

Python 程序：两个矩阵相加

Python 程序将十进制转换为二进制、八进制和十六进制

Python 程序检查素数

Python 程序检查数字是正数、负数还是零

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器