I'm trying to implement the doubly-linked list in these singly-linked list operations, but how do I properly implement the previous Node (antNode) in the functions addNode and elimNode?
Almost everything that is done in insNode is applicable in addNode function.
class ListNode:
def __init__(self, data, nextNode=None):
self.data = data
self.nextNode = nextNode
self.antNode = None
class DoublyLinkedListIterator:
def __init__(self, firstNode=None):
self.firstNode = firstNode
self.lastNode = firstNode
self.iterator = firstNode
if firstNode:
self.size = 1
else:
self.size = 0
def addNode(self, data): # Add a Node after the iterator.
"""Pre condition: Iterator defined
Pos condition: The data is inserted into a node after the
iterator. The iterator stands over this node.
"""
newNode = ListNode(data,None) # treats the empty list
newNode.nextNode = None
newNode.antNode = None
if(self.size == 0): # treats the empty list
self.iterator = newNode
self.firstNode = newNode
self.lastNode = newNode
elif self.iterator == self.lastNode:
self.lastNode.nextNode = newNode
self.iterator = newNode
self.lastNode = newNode
else:
newNode.nextNode = self.iterator.nextNode
self.iterator.nextNode = newNode
self.iterator = newNode
self.size += 1
return True
def elimNode(self): # Eliminates the element over the iterator and
# advances the iterator to the next node.
if(self.iterator == self.firstNode):
if(self.lastNode == self.firstNode):
self.lastNode = None
self.firstNode = None
self.iterator = None
else: # more than one node
#self.firstNode = self.firstNode.nextNode
self.firstNode = self.firstNode.nextNode
self.iterator.nextNode = None
self.iterator = self.firstNode
else: # iterator can be under the last or an inner element
currentNode = self.firstNode
while currentNode.nextNode != self.iterator:
currentNode = currentNode.nextNode
if self.iterator == self.lastNode:
self.lastNode = currentNode
self.iterator.nextNode = None
self.iterator = None
currentNode.nextNode = None
else:
currentNode.nextNode = self.iterator.nextNode
currentNode = self.iterator
self.iterator = self.iterator.nextNode
currentNode.nextNode = None
self.size = self.size - 1
return True
The function insNode that inserts a node before the iterator is like this with doubly linked list:
def insNode(self, data): # insert a node before the iterator
"""Pre condition: Iterator defined
Pos condition: The data is inserted into a node before the iterator.
The iterator stands over this node.
"""
newNode = ListNode(data, None) # treats the empty list
newNode.nextNode = None
newNode.antNode = None
if (self.size == 0): # treats the empty list
self.iterator = newNode
self.firstNode = newNode
self.lastNode = newNode
elif self.iterator == self.firstNode: # iterator is on the first element
newNode.nextNode = self.firstNode
self.iterator.antNode = newNode
self.firstNode = newNode
self.iterator = newNode
else: # iterator is on an inner element
newNode.antNode = self.iterator.antNode
self.iterator.antNode.nextNode = newNode
self.iterator.antNode = newNode
self.iterator = newNode
self.size += 1
return True
The answer is: yes you should do similar changes in insNode. However, much of the code is alike, so I would create a helper function to perform the actions these two methods have in common. Also, let the ListNode constructor take an optional argument also for the antNode attribute.
Not your question, but:
The elimNode method should better check that self.iterator is not None.
I find the name iterator confusing, since iterator is a very specific concept in Python, and it is not this. So I would rename that to cursor or currentNode or something. I can understand that this was given in some template code, or exercise, but then it doesn't really speak in favour of the quality of that teaching material.
I don't really see the purpose for the optional node parameter in the constructor of the main class. I would either omit it, or else let it accept a variable number of data values. That would be more practical.
Here is how it could look:
class ListNode:
def __init__(self, data, antNode=None, nextNode=None):
self.data = data
self.nextNode = nextNode
self.antNode = antNode
class DoublyLinkedListWithCursor:
def __init__(self):
self.firstNode = self.lastNode = self.currentNode = None
self.size = 0
def _insertBetween(self, data, before, after):
# Helper function for common logic in insNode and addNode methods
self.currentNode = ListNode(data, before, after)
if after:
after.antNode = self.currentNode
else:
self.lastNode = self.currentNode
if before:
before.nextNode = self.currentNode
else:
self.firstNode = self.currentNode
self.size += 1
def insNode(self, data):
self._insertBetween(data, self.currentNode.antNode if self.currentNode else self.lastNode, self.currentNode)
def addNode(self, data):
self._insertBetween(data, self.currentNode, self.currentNode.nextNode if self.currentNode else self.firstNode)
def elimNode(self):
if not self.currentNode: # Sanity check
return False
if self.currentNode.antNode:
self.currentNode.antNode.nextNode = self.currentNode.nextNode
else:
self.firstNode = self.currentNode.nextNode
if self.currentNode.nextNode:
self.currentNode.nextNode.antNode = self.currentNode.antNode
else:
self.lastNode = self.currentNode.antNode
self.currentNode = self.currentNode.nextNode
self.size -= 1
return True