Appending a doubly circular linked list to the end of another doubly circular list (Python)

user_16886429 0
Viewed 82

So I have an assignment that ask me to append a doubly circular linked list to the end of another doubly circular list. For example, I have two doubly circular linked lists which are [0,1,2,3] and [10,11,12,13]. The output should be [0,1,2,3,10,11,12,13], and we also have to make it reversed which is [13,12,11,10,3,2,1,0]

My assignment provides two py files. The first one is called "linked_list.py". It's for creating a doubly circular linked list. I cannot modify this file.

class Node:
    def __init__(self, x):
        self.data = x
        self.next = None
        self.pre = None

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

    def insertHead(self, x):
        self.head = Node(x)
        self.head.next = self.head
        self.head.pre = self.head

    def insert(self, y, x):
        tmp = self.head
        nodex = Node(x)
        while True:
            if tmp.data == y:
                break
            tmp = tmp.next
        nodex.next = tmp.next
        nodex.pre = tmp
        tmp.next.pre = nodex
        tmp.next = nodex

    def printForward(self):
        print("Forward :",end=" ")
        tmp = self.head
        print(tmp.data,end=" ")
        tmp = tmp.next
        while tmp!=self.head:
            print(tmp.data,end=" ")
            tmp=tmp.next
        print()

    def printBackward(self):
        print("Backward :",end=" ")
        tmp = self.head.pre
        print(tmp.data,end=" ")
        tmp = tmp.pre
        while tmp!=self.head.pre:
            print(tmp.data,end=" ")
            tmp=tmp.pre
        print()

The second code is "combine.py"

from linked_list import Node, DoubleLinkedList

def combine(l1, l2):
    
#This is the main part of this assignment, write a function that can combine two doubly circular linked lists. 
#There's no need to return value since we directly modify LL1 as our final result

if __name__=="__main__":
    LL1 = DoubleLinkedList()
    LL1.insertHead(0)
    LL1.insert(0, 1)
    LL1.insert(1, 2)
    LL1.insert(2, 3) #LL1 = [0,1,2,3]
    print(LL1)

    LL2 = DoubleLinkedList()
    LL2.insertHead(10)
    LL2.insert(10, 11)
    LL2.insert(11, 12)
    LL2.insert(12, 13) #LL2 = [10,11,12,13]
    print(LL2)

    combine(LL1, LL2)
    LL1.printForward()  # This function can print the combined linked list
    LL1.printBackward() # This function can reverse the 
    
    # Forward output : 0 1 2 3 10 11 12 13
    # Backward output : 13 12 11 10 3 2 1 0

At first I was thinking about using the same method as appending normal linked list but I realized that the last node of circular linked list will point at the first node. Then I got confused by the whole assignment. How can I make one doubly circular linked list get appended to the end of another doubly circular linked list? Some detailed explanations are appreciated. Thanks in advance.

doubly-linked-list circular-list linked-list python
1 Answers

Basically, you will need to append the complete l2 chain between head and head.pre of l1. In order to do so, I see two different methods:

  1. The naive one (complexity: O(n))

Simply reuse the methods that were nicely provided to you. In the end, you are just asked to add multiple values at the end of l1:

def combine(l1, l2):
    l1_tail_val = l1.head.pre.data
    l2_head = l2.head
    l1.insert(l1_tail_val, l2_head.data)
    l2_head = l2_head.next
    l1_tail_val = l2_head.data
    while l2_head != l2.head:
        l1.insert(l1_tail_val, l2_head.data)
        l1_tail_val = l2_head.data
        l2_head = l2_head.next

This method will need to iterate over l2 entirely, so if the list is big, it can take some time.

Edit: This is even worse than that, since in order to find the insert place, the insert method will iterate over l1, always to find that the wanted insert location is at the end. So this is closer to O(n^2) than O(n)

  1. The efficient one (complexity: O(1))

With this one, you don't have to iterate over anything, you just need to connect the nodes so that it forms a single circular list:

def combine(l1, l2):
    l1_tail = l1.head.pre
    l1_head = l1.head
    l2_tail = l2.head.pre
    l2_head = l2.head

    # Now just update the references
    # Then end of l2 should be connected to the head of l1 (same for the reverse relation)
    l1_head.pre = l2_tail
    l2_tail.next = l1_head
    
    # The start of l2 should be connected to the end of l1 (same for the reverse relation)
    l1_tail.next = l2_head
    l2_head.pre = l1_tail

This does not rely on any loop or recursion, thus giving you a constant complexity, no matter the lists lengths

user_44895810
Related