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.
