Sam Sam - 1 month ago 12
Python Question

Doubly-Linked List python

I am using

Python 3.0
, and I have to create the following:

1) Implement an ADT called Setplus as an ordered doubly-linked list, where the items are ordered from smallest item to the largest item in the list

So First I created a module called
Double_Node


class Double_Node:
"""
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):
return self.next_node
def set_next (self, n):
self.next_node = n
def get_prev (self):
return self.prev_node
def set_prev (self, p):
self.next_prev_node = p
def get_value (self):
return self.value
def set_value (self, d):
self.value = d


## print(self) prints the value stored in self.
## Effect: Prints value.
## __str__: Node -> Str
def __str__(self):
return str(self.value)


Then I create a class called Setplus:

class Setplus:
"""
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
def __init__(self):
self._head = None
self._tail = None

## self.empty() produces True if self is empty.
## empty: Setplus -> Bool
def empty(self):
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
while current:
if current.get_value == value:
return True
else:
current = current.get_next
return False

## self.distinct() produces True if all items are distinct.
## distinct: Setplus -> Bool
#def distinct(self):

## 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
print (counter)
else:
current = current.next
return counter

## 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


I am having trouble creating creating a contains method, count, which counts the number of values and add, which adds the node in the correct nondecreasing order.

Thanks in Advance

Answer

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 (_head and head or next and 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.