CODEWITHSUNDEEP
pythonlinked-list
aleen1
aleen1

Reputation: 5

python-Linked list implemention

Implement and test the following linked List methods 

def intersection(self, rs):
    """
    -------------------------------------------------------
    Copies only the values common to both the current list and rs
    to a new list. Uses a looping algorithm.
    -------------------------------------------------------
    Preconditions:
        rs - another list (List)
    Postconditions:
        returns
        new_list - contains one copy of values common to current list
            and rs (List)
        Current list and rs are unchanged.
    -------------------------------------------------------
    """


class _ListNode:

    def __init__(self, value, next_):

        self._value = deepcopy(value)
        self._next = next_
        return


class List:

    def __init__(self):

        self._front = None
        self._count = 0
        return

    def is_empty(self):

        return self._front is None

    def __len__(self):

       return self._count

    def insert(self, i, value):

        if i < 0:
            # negative index
            i = self._count + i

        n = 0
        previous = None
        current = self._front


        while n < i and current is not None:

            previous = current
            current = current._next
            n += 1

        if previous is None:
            self._front = _ListNode(value, self._front)
        else:

            previous._next = _ListNode(value, current)
        self._count += 1
        return

This what I have so far, I don't now how to do implement the intersection method

Example:

If List a contains:
0, 2, 1, 3, 5, 7


and List b contains:
1, 1, 3, 3, 5, 5, 7, 7


Then a.intersection(b) returns a List containing:
7, 5, 3, 1

Upvotes: 0

Views: 121

Answers (1)

inspectorG4dget
inspectorG4dget

Reputation: 113905

Add a __contains__ to make your life a little easier

def __contains__(self, val):
    curr = self.front
    while curr is not None:
        if curr._value == val: return True
        curr = curr._next
    return False


def intersection(self, rs):
    answer = List()
    curr = self.front
    while curr is not None:
        if curr._value in rs: answer.insert(-1, curr._value)
    return answer

Intersection with recursion:

def extend(self, rs):
    curr = rs.front
    while curr is not None:
        self.insert(-1, curr._value)

def intersection(self, rs):
    if rs.front is None: return List()
    answer = self.intersection(rs.front._next)
    if rs.front._value in self: answer.insert(-1, rs.front._value)
    return answer

Upvotes: 1

Related Questions