How to create a function where I can use two linked lists?

Question

class Node:
    def __init__(self, data = None):
        self.data = data
        self.ref  = None

class LinkedList:
    def __init__ (self):
        self.head = None

    def add_beginning(self, data):
        newNode = Node(data)

        if self.head is None:
            self.head= newNode
        else:
            n = self.head
            while n.ref:
                n = n.ref
            n.ref = newNode

    def print(self):
        if self.head == None:
            print(None)
        else:
            n = self.head
            while n:
                print(n.data,"-->", end= " ")
                n =n.ref


if __name__ == "__main__":
    LL = LinkedList()

    LL.add_beginning(3)
    LL.add_beginning(2)
    LL.add_beginning(1)
    LL.add_beginning(3)
    LL.print()

    KK = LinkedList()
    KK.add_beginning(2)
    KK.add_beginning(6)
    KK.add_beginning(5)
else:
    print("error")

I don't know how to create def where I can use two linked lists e.g. go through them and compare every element? I create two objects (i.e.) KK and LL, can I use them somehow?

Answer 1

Do you mean something like this?

LL1 = LinkedList()
# add some items to LL1

LL2 = LinkedList()
# add some items to LL2

item1 = LL1.head
item2 = LL2.head

count = 1
while item1 and item2:
    print("item", count)
    print("LL1", item1.data)
    print("LL2", item2.data)
    item1 = item1.ref
    item2 = item2.ref
    count += 1

Answer 2

I think overriding the comparison operator with the __eq__ method would be best answer in your case. You would then iterate over both linked lists at the same time until the end. If two nodes have different data, the function stops and returns False. If no different nodes are found, the function returns True.

class Node:
    def __init__(self, data = None):
        self.data = data
        self.ref  = None
        

class LinkedList:
    def __init__ (self):
        self.head = None

    # add_beginning method here
    # print method here

    def __eq__(self, other):  # <-- this method
        curr1, curr2 = self.head, other.head
        while curr1 != None or curr2 != None:
            if (curr1 == None) != (curr2 == None):  # check if a list has nodes left but not the other
                return False
            if curr1.data != curr2.data:  # check if both nodes have same data
                return False
            # iterate to next node
            curr1 = curr1.ref
            curr2 = curr2.ref
        return True

Then, you can compare your linked lists with the == operator :

LL = LinkedList()

LL.add_beginning(3)
LL.add_beginning(2)
LL.add_beginning(1)
LL.add_beginning(3)

KK = LinkedList()
KK.add_beginning(2)
KK.add_beginning(6)
KK.add_beginning(5)
print(KK == LL)
>>> False

LL = LinkedList()

LL.add_beginning(3)
LL.add_beginning(2)
LL.add_beginning(1)

KK = LinkedList()
KK.add_beginning(3)
KK.add_beginning(2)
KK.add_beginning(1)
print(KK == LL)
>>> True

Answer 3

Here's how to write a function that compared two LinkedLists for equality.

def equal(list1, list2):
    """Return True if data in the Nodes in two LinkedLists are all equal."""
    cur_node1, cur_node2 = list1.head, list2.head
    while cur_node1 and cur_node2:
        if cur_node1.data != cur_node2.data:
            return False
        cur_node1, cur_node2 = cur_node1.ref, cur_node2.ref

    return not cur_node1 and not cur_node2  # True if lists were same length.

if __name__ == "__main__":
    LL = LinkedList()

    LL.add_beginning(3)
    LL.add_beginning(2)
    LL.add_beginning(1)
    LL.add_beginning(3)
    LL.print()

    KK = LinkedList()
    KK.add_beginning(3)
    KK.add_beginning(2)
    KK.add_beginning(4)
    KK.add_beginning(3)

    print("Are LL and KK equal? ->", equal(LL, KK))