Inserting In The Middle Of A Doubly Linked List- 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 s

Solution 1:

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 classclassLinkedList:
    def__init__(self, data, prev=None, next=None):
        self.data = data
        self.prev = prev
        self.next = next# Just a string representationdef__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 logicdefinsertToMiddle(data, left, right):
    # IteratewhileTrue:
        # Test for intersectionif left.nextis right:
            node = LinkedList(data, left, right)
            left.next = node
            right.prev = node
            returnelif 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 callifnot left ornot 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

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

Output:

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

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)