在双向链表的中间插入-Python [英] Inserting in the middle of a doubly linked list- Python

问题描述

我对stackoverflow和Python语言是陌生的，并且有一个问题.我知道如何在Python中实现单链列表，但是双链列表遇到了麻烦，更具体地说，是插入到双链列表的中间.任何人都可以通过代码帮助我做到这一点吗?谢谢

I am new to stackoverflow and the Python language and have a question. I know how to implement a singly linked list in Python but am having trouble with doubly linked list, more specifically inserting into the middle of the doubly linked list. Can anyone help me with code to do this? Thank you

推荐答案

我也是Python的新手，但希望能对您有所帮助.因此，如果我正确地提出了您的问题，请假设您有一些(经典)链表实现 像这样:

Me also, I'm new to Python, but I hope I can help you. So if I got your question correctly, suppose you have some (classic) linked list implementation like this:

# Simple LinkedList class
class LinkedList:
    def __init__(self, data, prev=None, next=None):
        self.data = data
        self.prev = prev
        self.next = next

    # Just a string representation
    def __str__(self):
        if self.next:
            return '%s %s' % (str(self.data), self.next.__str__())
        else:
            return '%s' % str(self.data)

通过在链表的末端到中间同时进行迭代，您可以轻松地将元素插入到中间，从而知道链表的末端.当迭代器相交时，添加元素:

You can easily insert an element to middle, knowing the linked list's ends, by iterating simultaneously from the ends to middle. When the iterators intersect, you add your element:

# Insert to middle logic
def insertToMiddle(data, left, right):
    # Iterate
    while True:
        # Test for intersection
        if left.next is right:
            node = LinkedList(data, left, right)
            left.next = node
            right.prev = node
            return
        elif left is right:
            node = LinkedList(data, left.prev, right.next)
            left.next = node
            right.next.prev = node
            return

        # Next iteration
        left = left.next
        right = right.prev

        # This doesn't actually execute for a right call
        if not left or not right:
            return

在下面，您可以在插入前后看到一个链表的创建及其表示形式:

Below, you can see a linked list creation, and its representation, before and after the insertion:

# Sample list creation
node1 = LinkedList(1)
node2 = LinkedList(2,node1)
node3 = LinkedList(3,node2)
node4 = LinkedList(4,node3)
node1.next = node2
node2.next = node3
node3.next = node4

# Test
print node1 
insertToMiddle(5, node1, node4)
print node1
insertToMiddle(6, node1, node4)
print node1
insertToMiddle(7, node1, node4)
print node1

输出:

1 2 3 4                #initial
1 2 5 3 4              #inserted 5
1 2 5 6 3 4            #inserted 6, notice it's right to middle
1 2 5 7 6 3 4          #inserted 7

备注:如果您的列表中元素的数量为奇数(例如2 3 4)，则在中间插入是不确定的，因此上述函数将立即添加到中间的右侧(2 3元素4)

Remark: If your list has an odd number of elements (say 2 3 4), inserting to middle is somehow undefined, so the above function will add immediately to middle's right (2 3 elem 4)

这篇关于在双向链表的中间插入-Python的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！