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!

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:

( 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