4 Replies - 352 Views - Last Post: 08 February 2013 - 07:12 AM Rate Topic: -----

#1 shadowave  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 5
  • Joined: 26-October 10

Linked list within a linked list

Posted 07 February 2013 - 03:56 PM

im completely stuck on how to make a linked list within a linked list.

i know how to create a linked list:

#A linked list class
class SingleSortedLinkedList :
    #constructor
    def __init__ (self) :
        self._size = 0
        self._head = None
    
    #check for empty list
    def isEmpty(self) :
        return self._size == 0
    
    #overloaded length
    def __len__(self) :
        return self._size
    
    #prints out the data
    def traversal(self) :
        current = self._head
        while current is not None :
            print (current._data)
            current = current._next
            
    #insets (sorted) a new data item into the list
    def insert(self, item) :
        newNode = ListNode(item)
        self._size=self._size+1
        #when our list is new (or reduced to no items)
        if self._head is None :
            self._head = newNode
        #If our new node goes first:
        elif item < self._head._data :
            newNode._next = self._head
            self._head = newNode
        #not at the head, so we will be inserting later into the list    
        else: 
            node = self._head
            #loop to advance pointer until insertion spot located
            while node is not None and node._data < item :
                prev = node
                node = node._next
            if node is None:
                #at end, so newNode already points to None like it should.
                prev._next=newNode
            else:
                #otherwise, update the node
                prev._next=newNode
                newNode._next=node
                
            
            

#class for a single node            
class ListNode :
    def __init__ ( self, data) :
        self._data = data
        self._next = None



i just dont know how to modify it so that each node points to a separate linked list

Is This A Good Question/Topic? 0
  • +

Replies To: Linked list within a linked list

#2 Tayacan  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 145
  • View blog
  • Posts: 275
  • Joined: 18-January 11

Re: Linked list within a linked list

Posted 08 February 2013 - 02:09 AM

Well... Simply make an empty linked list, and then insert linked lists in it.

outer_list = SingleSortedLinkedList()

inner_list1 = SingleSortedLinkedList()
inner_list2 = SingleSortedLinkedList()

outer_list.insert(inner_list1)
outer_list.insert(inner_list2)



Of course, when your linked list is sorted, you'll need to make it so that linked lists can be compared too (otherwise, how will you know where to insert?). This can be done by overriding the __cmp__ method. How you want to compare them is up to you, of course.
Was This Post Helpful? 1
  • +
  • -

#3 Nallo  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 163
  • View blog
  • Posts: 255
  • Joined: 19-July 09

Re: Linked list within a linked list

Posted 08 February 2013 - 03:42 AM

View PostTayacan, on 08 February 2013 - 09:09 AM, said:

...
This can be done by overriding the __cmp__ method.
...


I think shadowave is using Python 3.x. cmp is not supported in python 3.x so you need to overwrite __lt__ (and maybe __eq__) for comparisons insted.

class ListNode:
    def __init__(self, data):
        self._data = data
        self._next = None
    def __lt__(self, other):
        try:
            return self._data < other._data
        except TypeError:
            #oops we need a fallback for non orderable types
            #might a bit silly to use id, as between two runs of the program
            #ordering will likely be different
            #you may want to choose something more sensible
            return id(self) < id(other)


This post has been edited by Nallo: 08 February 2013 - 07:03 AM

Was This Post Helpful? 0
  • +
  • -

#4 Tayacan  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 145
  • View blog
  • Posts: 275
  • Joined: 18-January 11

Re: Linked list within a linked list

Posted 08 February 2013 - 05:32 AM

Ah, fair enough. Heh, I'm still mostly using Python 2.

Anyway, I'd actually suggest defining __lt__ for the linked list, rather than the node. For instance, you could compare the lengths:

#A linked list class
class SingleSortedLinkedList :
    #constructor
    def __init__ (self) :
        self._size = 0
        self._head = None
    
    # ...

    # Compare linked lists by size.
    def __lt__(self,other):
        return len(self) < len(other)


Was This Post Helpful? 0
  • +
  • -

#5 Nallo  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 163
  • View blog
  • Posts: 255
  • Joined: 19-July 09

Re: Linked list within a linked list

Posted 08 February 2013 - 07:12 AM

Yup, right. It is probably best to have a __lt__ method for both the SingleSortedLinkedList and the ListNode class.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1