Reverse double linked list in python 2.7

Question

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

Answer 1

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] > 0:
 self.cur = self.cur.plus_node
 elif self.cur.dir[0] < 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.

• ChatterOne: You can probably expand your answer easily by adding an __iter__ and using the direction flag that you suggested to yield either the next or the previous node.
• Lin Ma: Love your code and your ideas to use direction flag, and also handle circular double linkedlist. Mark your reply as answer.
• Lin Ma: @ChatterOne, nice catch! vote up.