Problems Reversing a Doubly Linked List
<p>I have to reverse a doubly linked list(DLL) between two nodes. I've done this with singly linked lists(SLL), but I find it harder to do with DLL's? It might be the having to do it between two particular nodes.
Here is the code for my DLLNode &amp; DLL. When I test this code it seems to do nothing to my DLL. Any tips on what I'm doing wrong??</p>

<p>EDIT: So I'm inputting a linked list 'a','b','c','d','e','f' and call twist('b','e'): This should result in the linked list 'a' 'b' 'e' 'd' 'c' 'f'</p>

<pre><code>class DoublyLinkedListNode:
def __init__(self, item, prevnode = None, nextnode = None):
    self._data = item
    self.setnext(nextnode)
    self.setprev(prevnode)

def data(self):
    return self._data

def next(self):
    return self._next

def prev(self):
    return self._prev

def setprev(self, prevnode):
    self._prev = prevnode

def setnext(self, nextnode):
    self._next = nextnode

class DoublyLinkedList:
def __init__(self):
    self._head = None
    self._tail = None
    self._length = 0

def _newnode(self, item, nextnode = None, prevnode = None):
    return DoublyLinkedListNode(item, nextnode, prevnode)

def addfirst(self, item):
    if self.isempty():
        return self._addtoempty(item)
    node = self._newnode(item, None, self._head)
    self._head.setprev(node)
    self._head = node
    self._length += 1

def addlast(self, item):
    if self.isempty():
        return self._addtoempty(item)
    node = self._newnode(item, self._tail, None)
    self._tail.setnext(node)
    self._tail = node
    self._length += 1

def _addtoempty(self, item):
    node = self._newnode(item, None, None)
    self._head = self._tail = node
    self._length = 1

def removefirst(self):
    if len(self) &lt;= 1:
        return self._removelastitem()
    data = self._head.data()
    self._head = self._head.next()
    self._head.setprev(None)
    self._length -= 1
    return data

def removelast(self):
    if len(self) &lt;= 1:
        return self._removelastitem()
    data = self._tail.data()
    self._tail = self._tail.prev()
    self._tail.setnext(None)
    self._length -= 1
    return data

def _removelastitem(self):
    if self.isempty():
        return None # Should probably raise an error.
    data = self._head.data()
    self._head = self._tail = None
    self._length = 0
    return data

def twist(self, endpt1, endpt2):
    current = self._head
    while current != None:
        if current.data() == endpt1:
            current.next().setnext(endpt2.next())
            endpt2.setnext(current.next())
            current.setnext(endpt2)
        else:
            current = current.next()

def isempty(self):
    return len(self) == 0

def _nodes(self):
    node = self._head
    while node is not None:
        yield node
        node = node.next()

def __iter__(self):
    for node in self._nodes():
        yield node.data()

def __len__(self):
    return self._length

def __str__(self):
    items = [str(data) for data in self]
    return ", ".join(items)
</code></pre>

<p>Here is the test I'm running:</p>

<pre><code>    def testtwist1(self):
        n = [0,1,2,3,4,5]
        L = DoublyLinkedList()
        for i in n:
            L.addlast(i)
        L.twist(2,5)
        print(L)   # returns the list 0,1,2,3,4,5
</code></pre>

<p>I don't see how this executes at all.  You've apparently set up a DLL, and then called <strong>DLL.twist('b', 'e')</strong>.  Thus, endpt1 = 'b' and endpt2 = 'e'.  You then compare endpt1 to current.data, but then you access endpt2.next.  <em>endpt2 is a single-character string</em>.</p>

<p>You never reference the <strong>prev</strong> pointers at all.</p>

<p>The only time you try to alter anything is when you hit node <strong>b</strong>.  Then you seem to try to exchange the <strong>next</strong> pointers of <strong>b</strong> and <strong>e</strong> (so <strong>b.next</strong> is <strong>f</strong>, and <strong>e.next</strong> is <strong>c</strong>, but that's all.</p>

<p>At this point, I expect that your forward links give you two lists: a->b->f and c->d->e->c (a cycle), and that the backward links are unchanged.</p>

<p>Get pencil and paper or a white board and walk through these changes, one statement at a time; that's what I do ...</p>

<hr>

<p>I recovered <strong>twist</strong> from your previous post, fixed the indentation, and ran.  As I explain above, this faults in execution:</p>

<pre><code>Traceback (most recent call last):
  File "so.py", line 113, in &lt;module&gt;
    L.twist(2,5)
  File "so.py", line 102, in twist
    current.next().setnext(endpt2.next())
AttributeError: 'int' object has no attribute 'next'
</code></pre>

<p>There is no such thing as <strong>2.next()</strong>.  I don't think you're actually getting to your <strong>print</strong> statement.  Also, <strong>print(L)</strong> will not print the node values in order; you haven't included a <strong>__repr__</strong> method for your DLL object.  <strong>__str__</strong> would do the job, but you've use the list head pointer as if it were an iterable over the forward-linked list.</p>

<p>I strongly recommend that you back up and approach this with incremental programming: write a method or a few lines, test that, and don't continue until that works as you expect.  Yes, this means that you're writing detailed tests as you go ... that's a good thing.  Keep them, and keep running them.</p>

python linked-list doubly-linked-list