I am using
Fields: value stores any value
next points to the next node in the list
prev points to the previous node in the list
## Double_Node() produces a newly constructed empty node.
## __init__: Any -> Node
def __init__(self, value, prev = None, next = None):
self.value = value
self.prev_node = prev
self.next_node = next
def get_next (self):
def set_next (self, n):
self.next_node = n
def get_prev (self):
def set_prev (self, p):
self.next_prev_node = p
def get_value (self):
def set_value (self, d):
self.value = d
## print(self) prints the value stored in self.
## Effect: Prints value.
## __str__: Node -> Str
Field: _head points to the first node in the linked list
_tail points to the last node in a linked list
## Setplus() produces a newly constructed empty setplus.
## __init__: -> Setplus
self._head = None
self._tail = None
## self.empty() produces True if self is empty.
## empty: Setplus -> Bool
return self._head == None
## value in self produces True if value is an item in self.
## __contains__: Setplus Any -> Bool
def __contains__(self, value):
current = self._head
if current.get_value == value:
current = current.get_next
## self.distinct() produces True if all items are distinct.
## distinct: Setplus -> Bool
## count(value) produces the number of occurrences of value.
## count: Setplus Any -> Int
def count(self, value):
counter = 0
current = self._head
while current != None:
if current.value == value:
counter += 1
current = current.next
## self.add(value) adds value as an item in order.
## Effects: Mutates self.
## add: Setplus Any -> None
def add(self, value):
new_node = Double_Node(value)
if self.head == None:
self.head = new_node
if self.tail != None:
slef.tail.next = new_node
self.tail = new_node
The first major issue in your code is typos and incorrect names.
There's one clear typo,
slef instead of
self in one of your functions.
There are also a bunch of places where you're using two different names for what is supposed to be the same attribute (
next_node, for instance).
You also have defined getter and setter functions in your
Double_Node class, but the only time you try to use them in
Setplus you only reference the method without calling it. The line
current = current.get_next should almost certainly be
current = current.get_next().
A brief diversion on getter and setter functions: They're usually not needed in Python classes. Just use attributes directly. If you later find you need more fancy behavior (e.g. validation of newly set values or generation of requested values on the fly), you can change the class use a
property to turn attribute access syntax into method calls. In other programming languages you usually can't change away from attribute access that way, so getter and setter methods are encouraged in order to have an extensible API from the start.
(Note that if you're a student, your instructors may be less familiar with Python than other languages, so they may want you to write getters and setters even though they're generally bad style in Python code. Consider learning how to use a
property instead and you might blow their mind later on!)
I'd get rid of the getter and setter functions in
Double_Node, simply as a matter of style. But, if you are going to keep them (perhaps because they're required for your assignment), you should then actually use them in your code!
And finally, to get to the actual question you wanted help with, inserting into the linked list in sorted order, you probably want to do something like this:
def add(self, value): new_node = Double_Node(value) if self._head == None: # inserting into empty list self._head = self._tail = new_node else: # inserting into a list that contains at least one node already current = self._head while current and current.value < value: # find a node to insert before current = current.get_next() if current: # not inserting at end of list new_node.set_next(current) current.set_prev(new_node) prev = current.get_prev() if prev: # not inserting at start new_node.set_prev(prev) prev.set_next(new_node) else: # inserting at start self._head = new_node else: # inserting at end new_node.set_prev(self._tail) self._tail.set_next(new_node) self._tail = new_node
After you've made
add insert in sorted order, your other methods can take advantage of that fact. For instance,
__contains__ can stop searching if it sees a value that's greater than the one it's looking for, and
count will find all the matching values in one contiguous group.