Linked Lists

#crosscompute

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

    def search(self, x):
        current = self.head # initialize current to head
        while current != None: # loop until current not equal to None
            if current.data == x:
                return True # data found
            current = current.next 
        return False # data not found
    def print_list(self):
        node = self.head
        while node:
            print(node.data)
            node = node.next
            
    def print_nodes(self):
        node = self.head
        while node:
            print(node)
            node = node.next

class Node:
    def __init__(self, data=0, next=None):
        self.data = data
        self.next = next
        
    def insert_after(self, new_node):
        new_node.next = self.next # set current `next` as new node's `next
        self.next = new_node # set new node as current's `next`
        
    # delete node after current, assuming node is not a tail.
    def delete_after(self):
        self.next = self.next.next

# start two empty lists
L1 = LinkedList()
L2 = LinkedList()

# create nodes
L1.head = Node(2)
L1.second = Node(5)
L1.third = Node(7)

L2.head = Node(3)
L2.second = Node(11)

# link the nodes
L1.head.next = L1.second
L1.second.next = L1.third

L2.head.next = L2.second

import gc
list_of_nodes = [obj for obj in gc.get_objects() if isinstance(obj, Node)]; list_of_nodes

list_of_lists = [obj for obj in gc.get_objects() if isinstance(obj, LinkedList)]; list_of_lists

L1.print_list()

L2.print_list()

# merge two sorted singly linked lists so that the merged list is still sorted

# naive approach: traverse each list
# grab the min and link to first list
def merge_lists(L1, L2):
    dummy_head = tail = Node(...)
    node1 = L1.head
    node2 = L2.head
    while node1 and node2: # lists not empty
        if node1.data <= node2.data:
            tail.next = node1 # attach node1 to tail of new list
            node1 = node1.next # stepping node1 pointer to the next node on L1
        else:
            tail.next = node2
            node2 = node2.next
        tail = tail.next
    tail.next = node1 or node2 # takes the leftover : take tail of one of the lists and link to new list
    result = LinkedList()
    result.head = dummy_head.next
    return result

L3 = merge_lists(L1, L2)

L3.print_list()

L1.print_list()

L2.print_list()

list_of_nodes # unchanged

list_of_lists 

# ??? Shoud be 3 lists (L1, L2, L3) but only 2

L1.print_nodes()

L2.print_nodes()

L3.print_nodes()