Doubly linked lists in Python

Question

I'm working on a project where I manipulate a lot of sorted lists of elements, and I need to be able to remove any of these quickly. Since I don't need any kind of indexation, I thought that the doubly linked list structure would be best. I couldn't find any good pre-made module so I made my own:

class Node: # nodes for doubly-linked lists
 def __init__(self, val, dll):
 self.val = val
 self.next = None
 self.prev = None
 self.dll = dll
class DLList: # doubly-linked lists
 def __init__(self):
 self.first = None
 self.last = None
 self.len = 0
# def __iter__(self):
# self.curr = self.first
# return self
# 
# def __next__(self):
# if self.curr == None:
# raise StopIteration
# self.curr = self.curr.next
# if self.curr == None:
# raise StopIteration
# return self.curr
 def append(self, val): # add a node with value val at the end of the list
 node = Node(val, self)
 node.prev = self.last
 self.last = node
 if self.first == None: # <=> if self was empty
 self.first = node
 self.len += 1
 def appendleft(self, val): # same as previous, but at the beginning of the list
 node = Node(val, self)
 node.next = self.first
 self.first = node
 if self.last == None:
 self.last = node
 self.len += 1
 def nodeat(self, i): # gives the ith node (starting at 0)
 if i == -1:
 return None
 if i > self.len or i < -1:
 raise IndexError('index out of range')
 curr = self.first
 for j in range(i):
 curr = curr.next
 return curr
 def remove(self, node): # remove a given node in the list
 if node.dll != self: #cannot remove a node that is not in the list
 raise ValueError('node not in list')
 p = node.prev
 n = node.next
 v = node.val
 node.dll = None
 if p != None:
 p.next = n
 else:
 self.first = n
 if n != None:
 n.prev = p
 else:
 self.last = p
 self.len -= 1
 return v
 def add(self, val, i): # add a node at the ith place in the list
 node = Node(val, self)
 if i > self.len:
 raise IndexError('index out of range')
 self.len += 1
 previ = self.nodeat(i)
 node.prev = previ.prev
 node.next = previ
 previ.prev = node
 def clear(self): # empty the list
 self.first = None
 self.last = None
 self.len = 0
 def extend(self, iterable): # add the elements of iterable in order at the end of the list
 for i in iterable:
 self.append(i)
 self.len += 1
 def extendleft(self, iterable): # same as previous, but at the beginning (and in reverse order)
 for i in iterable:
 self.appendleft(i)
 self.len += 1
 def dll_to_list(self): # return a python list with the elements of the doubly-linked list
 res = []
 curr = self.first
 while curr != None:
 res.append(curr.val)
 curr = curr.next
 return res
 def is_empty(self): # check whether the list is empty
 return self.len == 0

Since I would lose time checking that the item I want to remove is in the list by browsing it, I added a pointer toward the list a Node is in inside the node, so that I can check that I'm not removing things from the wrong list.

Those lists are stocked in a Python dictionary, and at some point I started getting 'node not in list' errors. Does anyone know how it could appear? I never use anything but the methods listed here to manipulate the lists...

Otherwise, does anyone know about a well-coded module that I could use in place of this one?

Thanks!

• Blckknght: Without seeing the code that's trying to do the removals, I don't think we can possibly guess why you're getting the error you describe. The code you have shown would raise that error if you tried to remove the same node twice, so I'd guess you're doing that somehow. I'd also note that it is very unusual to have a container like a list serve as its own iterator (usually containers are only iterable, not iterators themselves).
• Nono le Mog: Yeah, it's for work so I'm not comfortable putting the complete code up here, but you make a good point. For the iterator, it didn't work so I scrapped it and I forgot to remove this bit of code... I'll learn how to do it properly another time!

Answer 1

A doubly linked list has links going both directions.

Example:

def append(self, val): # add a node with value val at the end of the list
 node = Node(val, self) # new node, ok
 node.prev = self.last # ok, the new nodes prev is the last node of your list
 self.last = node # ok, your new node is now the last of your list 
 if self.first == None: # yeah, ok, if its empty its also the first one now
 self.first = node
 self.len += 1

but ... you do not set the back-direction:

 node.prev.next = node # before node.prev = self.last 

Similar in your other appends. You have to always clear/reset/set all the links in both directions if you add/remove things into a doubly-linked-list:

append-drawing

( Red are all the changed variabels on append )

Essentially your list is not complete - if you operate / iterate on it, things will go missing in unexpected ways

• Nono le Mog: That's... incredibly stupid and I can't believe it didn't come up sooner! I'm not sure it caused my issue because the error message was very specific, but I'm sure glad you caught that one... It does explain some other weird things that I have noticed, though. Thank you very much!
• Patrick Artner: Not quite sure what warrented the downvote ... on a post that this old. If you have feedback how to better the answer quality, procide feedback. Thanks.