CODEWITHSUNDEEP
pythonpython-3.xlinked-list
T.Woody
T.Woody

Reputation: 1228

What is the easiest way to turn a LinkedList class into a Circular Linked List class?

I have a LinkedList class that has close to 200 lines of code. I would like to make a new class LLCircular(LinkedList) by always making sure that any myLL.tail.next is myLL.head. I believe I would need to update append(), push(), remove(), etc. accordingly. Is there a way I can do this to keep the original LinkedList class intact? Maybe a decorator or some dunder method?

For brevity's sake, if reading the code, my push() method is just the inverse of append(). I also have a pop() and remove() method, which would need to be updated, if I just rewrite those methods. As I am trying to avoid that approach, I am not posting that part of the code.

class LinkedListNode:
   def __init__(self, value, nextNode=None, prevNode=None):
      self.value  = value
      self.next   = nextNode
      self.prev   = prevNode
   def __str__(self):
      return str(self.value)

class LinkedList:
   def __init__(self, values=None):
      self.head   = None
      self.tail   = None
      if values is not None:
         self.append(values)
   def __str__(self):
      values = [str(x) for x in self]
      return ' -> '.join(values)
   def append(self, value=None):
      if value is None:
         raise ValueError('ERROR: LinkedList.py: append() `value` PARAMETER MISSING')
      if isinstance(value, list):
         for v in value:
            self.append(v)
         return
      elif self.head is None:
         self.head   = LinkedListNode(value)
         self.tail   = self.head
      else:
         ''' We have existing nodes  '''
         ''' Head.next is same '''
         ''' Tail is new node '''
         self.tail.next = LinkedListNode(value, None, self.tail)
         self.tail      = self.tail.next
         if self.head.next is None:
            self.head.next = self.tail.prev
      return self.tail

'''class LLCircular(LinkedList):'''
    ''' ??? '''

Test Code:

foo = LinkedList([1,2,3])
foo.tail.next = foo.head #My LL is now circular
cur = foo.head
i = 0
while cur:
   print(cur)
   cur = cur.next
   i +=1
   if i>9:
      break

Upvotes: 0

Views: 70

Answers (2)

jsbueno
jsbueno

Reputation: 110311

If it is "circular" it won't need a tail or head, would it? Nor "append" makes sense - insert_after and insert_before methods should be enough - also, any node is a reference to the complete circular list, no need for different objects:

class Circular:
    def __init__(self, value=None):
        self.value = value
        self.next = self
        self.previous = self
    def insert_after(self, value):
        node = Circular(value)
        node.next = self.next
        node.previous = self
        self.next.previous = node
        self.next = node
    def insert_before(self, value):
        node = Circular(value)
        node.next = self
        node.previous = self.previous
        self.previous.next = node
        self.previous = node
    def del_next(self):
        self.next = self.next.next
        self.next.previous = self
    def __iter__(self):
        cursor = self.next
        yield self
        while cursor != self:
             yield cursor
             cursor = cursor.next
    def __len__(self):
        return sum(1 for _ in self)

Upvotes: 1

TheoretiCAL
TheoretiCAL

Reputation: 20571

What you want is to call your LinkedList base class functions using the super keyword, and then add the slight modifications to the LLCircular class function, i.e:

class LLCircular(LinkedList):
    def append(self, value=None):
        super(LLCircular, self).append(value)
        # In addition to having called the LinkedList append, now you want
        # to make sure the tail is pointing at the head
        self.tail.next = self.head
        self.head.prev = self.tail

Upvotes: 1

Related Questions