Reverse double linked list in python 2.7 Problem is straightforward, reverse a double linkedlist, any advice on functional bug, performance in terms of algorithm time complexity and code style are highly appreciated.

Code written in Python 2.7.

class DoubleLinkedListNode:
    def __init__(self, value, next_node):
        self.value = value
        self.pre_node = None
        if next_node:
            next_node.pre_node = self
        self.next_node = next_node
    def reverse_list(self):
        new_list = self
        cur = new_list.next_node
        new_list.next_node = None
        new_list.pre_node = None
        while cur:
            node = cur.next_node
            new_list.pre_node = cur
            cur.next_node = new_list
            new_list = cur
            cur = node
        return new_list
    def print_list(self):
        cur = self
        result = []
        while cur:
            result.append(cur.value)
            cur = cur.next_node
        return result

if __name__ == "__main__":
    head = DoubleLinkedListNode(1, DoubleLinkedListNode(2, DoubleLinkedListNode(3, DoubleLinkedListNode(4, DoubleLinkedListNode(5, None)))))
    print head.print_list()
    new_head = head.reverse_list()
    print new_head.print_list()
Firstly, the line

new_list.pre_node = None


doesn't do anything and can be removed. Secondly, your code can't handle circular double-linked lists.

Circular lists

When called on a circular double-linked list:


Print_list goes into an endless loop.
Reverse_list terminates late, giving a partially reversed list.


Your code could be easily improved to handle these issues. Preventing an endless loop requires keeping track of the identity of each node. Below, I've done this by incrementing a global variable node_count, but there are more Pythonic ways to keep a count of instances of objects.

The unique id is used to track when the cursor id matches self.id, terminating the while loops in print_list and reverse_list at the appropriate time for circular lists.

Lastly, PEP8 specifies methods within a class should be separated by a single line.

See below:

class DoubleLinkedListNode:

    def __init__(self, value, next_node):
        global node_count                         # added unique node id
        self.id = node_count
        node_count += 1
        self.value = value
        self.pre_node = None                      # removed unnecessary line
        if next_node:
            next_node.pre_node = self
        self.next_node = next_node

    def reverse_list(self):
        new_list = self
        cur = new_list.next_node
        new_list.next_node = None
        while cur:
            node = cur.next_node
            new_list.pre_node = cur
                cur.next_node = new_list
            if cur.id == self.id and not node: break    # for circular lists
            new_list = cur
            cur = node
        return new_list

    def print_list(self):
        cur = self
        result = []
        while cur:
            result.append([cur.value])
            next_id = cur.next_node.id if cur.next_node else None
            if next_id == self.id: break               # for circular lists
            cur = cur.next_node
        return result

if __name__ == "__main__":
    node_count = 0
    head = DoubleLinkedListNode(1, DoubleLinkedListNode(2, DoubleLinkedListNode(3, DoubleLinkedListNode(4, DoubleLinkedListNode(5, None)))))
    print(head.print_list())
    new_head = head.reverse_list()
    print(new_head.print_list())


(Bonus: For simple testing, here's my method to make the lists circular. Add it to the DoubleLinkedListNode class.)

    def circularize(self):
        cur = self
        while cur.next_node:
            cur = cur.next_node
        cur.next_node = self


Complexity

Reversing lists, double-linked or not, scales according to \$\mathcal{O}(n)\$, where n is the length of the list.

The only way to speed it up significantly is to make each list an object, with a Boolean direction flag. Any process moving through the list first refers to the direction flag, which either calls next_node or pre_node depending on how it's set. All that's needed to reverse the list is to reverse the direction flag.

Update:

Below is an example of how \$\mathcal{O}(1)\$ reversal of double-linked lists might be implemented using a direction flag. Points relevant to OP's code are:


A dedicated reverse_list method is not really necessary.
An __iter__ method is more useful than a dedicated print_list method (thanks ChatterOne).
Circular lists are also reversed neatly this way (note that __iter__ cycles endlessly for circular lists).


See below:

class DoubleLinkedListNode:
    def __init__(self, value, plus_node, dir=None):
        self.value = value
        self.minus_node = None
        if plus_node:
            plus_node.minus_node = self
            if dir == None:
                self.dir = plus_node.dir
        if dir != None: 
            self.dir = dir
        self.plus_node = plus_node

    def __iter__(self):
        self.cur = self
        return self

    def __next__(self):
        if self.cur:
            current = self.cur
            if self.cur.dir:
                if self.cur.dir[0] &gt; 0:
                    self.cur = self.cur.plus_node
                elif self.cur.dir[0] &lt; 0:
                    self.cur = self.cur.minus_node
            return current
        else:
            raise StopIteration

if __name__ == "__main__":
    tail = DoubleLinkedListNode(5, None, [1]) # [1] sets direction for all nodes in list.
    head = DoubleLinkedListNode(1, DoubleLinkedListNode(2, DoubleLinkedListNode(3, DoubleLinkedListNode(4, tail))))
    for i in head: print(i.value)  # Prints node values forwards from head.
    head.dir[0] = -1               # Reverses direction for all nodes in the list.
    for i in tail: print(i.value)  # Prints node values in reverse from tail.