Sorting a double linked list

  • (2 Pages)
  • +
  • 1
  • 2

17 Replies - 2275 Views - Last Post: 29 March 2013 - 01:50 AM Rate Topic: -----

#1 medaa  Icon User is offline

  • D.I.C Head

Reputation: 6
  • View blog
  • Posts: 106
  • Joined: 24-October 12

Sorting a double linked list

Posted 25 March 2013 - 02:17 PM

Im trying to sort a doubly linked list, but Im having a problem implementing the sort function:

Here are all the functions:

from d_linked_node import d_linked_node
from item import item

class d_linked_list:
    
    def __init__(self):
        self.__head=None
        self.__tail=None
        self.__size=0        

            
    def search(self, item):
        current = self.__head
        found = False
        while current != None and not found:
            if current.getData() == item:
                found= True
            else:
                current = current.getNext()
        return found
        
    def index(self, item):
        current = self.__head
        found = False
        index = 0
        while current != None and not found:
            if current.getData() == item:
                found= True
            else:
                current = current.getNext()
                index = index + 1
        if not found:
                index = -1
        return index        
         
    def add(self, item):
        temp = d_linked_node(item,None,None)
        if (self.__tail == None):
            self.__head = temp
            self.__size += 1            
            self.__tail = temp
        else:
            temp.setNext(self.__head)            
            self.__head.setPrevious(temp)
            self.__head = temp
            self.__size += 1
        
    def remove(self, item):
        if (self.search(item)):
            inde = self.index(item)
            self.__size -= 1
            temp = self.__head
            if (inde == 0):
                self.__head = temp.getNext()
                if(self.__head == None):
                    self.__tail = None
                else:
                    self.__head.setPrevious(None)
            else:
                for i in range(inde):
                    temp = temp.getNext()
                a = temp.getPrevious()
                a.setNext(temp.getNext())
                if (a.getNext() == None):
                    self.__tail = a
                else:
                    a.getNext().setPrevious(a)
        
    def append(self, item):
        if self.__size == 0:
            self.add(item)
        else:
            self.__size +=1
            temp = d_linked_node(item,None,self.__tail)
            self.__tail.setNext(temp)
            self.__tail = temp
        
    def insert(self, pos, item):
        temp = self.__head
        temp_in = d_linked_node(item,None,None)
        for i in range(pos):
            temp = temp.getNext()        
        if (pos == 0):
            temp_in.setNext(self.__head)
            self.__head = temp_in
            if (self.__size == 0):
                self.__tail = temp_in
            else:
                temp_in.getNext().setPrevious(temp_in)
            self.__size +=1
        else:
            if (temp == None):
                temp_in.setPrevious(self.__tail)
                self.__tail.setNext(temp_in)
                self.__tail=temp_in
            else:
                temp_in.setNext(temp)
                temp.getPrevious().setNext(temp_in)
                temp_in.setPrevious(temp.getPrevious())
                temp.setPrevious(temp_in)
            self.__size +=1
      
        
    def pop1(self):
        temp = self.__tail
        if (self.__size < 2):
            self.__head = None
            self.__tail = None
            self.__size = 0
        else:            
            temp.getPrevious().setNext(None)
            self.__tail = temp.getPrevious()
            self.__size -= 1          
        return temp.getData()
        
    def pop(self, pos):
        self.__size -= 1
        temp = self.__head
        if (pos == 0):
            self.__head = temp.getNext()
            if(self.__head == None):
                self.__tail = None
            else:
                self.__head.setPrevious(None)
            return temp.getData()
        else:
            for i in range(pos):
                temp = temp.getNext()
            a = temp.getPrevious()
            a.setNext(temp.getNext())
            if (a.getNext() == None):
                self.__tail = a
            else:
                a.getNext().setPrevious(a)
            return temp.getData()
        
    def search_larger(self, item):
        temp = self.__head
        a = 0
        while temp != None:
            if (temp.getData() > item):
                break
            temp = temp.getNext()
            a +=1
        if(temp == None):
            return -1
        return a
        
    def get_size(self):
        return self.__size    
    
    def get_item(self, pos):
        if (pos < 0):
            if (pos < -self.__size):
                raise Exception("pos doesn't exist")
            temp = self.__tail
            for i in range(pos,-1):
                temp = temp.getPrevious()
            return temp.getData()
        else:
            if (pos >= self.__size):
                raise Exception("pos doesn't exist")
            temp = self.__head
            for i in range(0,pos):
                temp = temp.getNext()     
            return temp.getData()
 
    
    def sort(self):
        for index in range(len(self)):
            smallindex=index
            for i in range(index,len(self)):
                if self[i]<self[smallindex]:
                    smallindex=i
         
        temp=self[index]
        self[index]=self[smallindex]
        self[smallindex]=temp        
        pass
    
    #you need to implement the sort by using selection sort to sort a list of items
    #sort by the specified attribute, either "price" or "quantity"
    def sort_by_attr(self, attr):
        if attr=="Price":
            for index in range(len(self)):
                smallindex=index
                for i in range(index,len(self)):
                    if self[i]<self[smallindex]:
                        smallindex=i
                     
            temp=self[index]
            self[index]=self[smallindex]
            self[smallindex]=temp   
        
        elif attr=="Quantity":
            for index in range(len(self)):
                smallindex=index
                for i in range(index,len(self)):
                    if self[i]<self[smallindex]:
                        smallindex=i
                     
            temp=self[index]
            self[index]=self[smallindex]
            self[smallindex]=temp             
            
        
    def __str__(self):
        temp = self.__head
        pr = ""
        while (temp != None):
            pr = pr + str(temp.getData()) + " "
            temp = temp.getNext()
        pr = pr[:-1]
        return pr

def test():
          
    linked_list = d_linked_list()
            
    is_pass = (linked_list.get_size() == 0)
    assert is_pass == True, "fail the test"
    
    linked_list.add("World")
    linked_list.add("Hello")    
    
    is_pass = (str(linked_list) == "Hello World")
    assert is_pass == True, "fail the test"
        
    is_pass = (linked_list.get_size() == 2)
    assert is_pass == True, "fail the test"
    
    is_pass = (linked_list.get_item(0) == "Hello")
    assert is_pass == True, "fail the test"


    is_pass = (linked_list.get_item(1) == "World")
    assert is_pass == True, "fail the test"    
    
    is_pass = (linked_list.get_item(0) == "Hello" and linked_list.get_size() == 2)
    assert is_pass == True, "fail the test"
    
    is_pass = (linked_list.pop(1) == "World")
    assert is_pass == True, "fail the test"     
    
    is_pass = (linked_list.pop1() == "Hello")
    assert is_pass == True, "fail the test"     
    
    is_pass = (linked_list.get_size() == 0)
    assert is_pass == True, "fail the test" 
    
    
        

            
    int_list2 = d_linked_list()
            
    for i in range(0, 10):
        int_list2.add(i)      
    int_list2.remove(1)
    int_list2.remove(3)
    int_list2.remove(2)
    int_list2.remove(0)
    is_pass = (str(int_list2) == "9 8 7 6 5 4")
    assert is_pass == True, "fail the test"
        
    for i in range(11, 13):
        int_list2.append(i)
    is_pass = (str(int_list2) == "9 8 7 6 5 4 11 12")
    assert is_pass == True, "fail the test"
        
    for i in range(21, 23):
        int_list2.insert(0,i)
    is_pass = (str(int_list2) == "22 21 9 8 7 6 5 4 11 12")
    assert is_pass == True, "fail the test"
        
    is_pass = (int_list2.get_size() == 10)
    assert is_pass == True, "fail the test"    
            
    int_list = d_linked_list()
            
    is_pass = (int_list.get_size() == 0)
    assert is_pass == True, "fail the test"
            

            
    for i in range(0, 1000):
        int_list.append(i)      
    correctOrder = True
    
    is_pass = (int_list.get_size() == 1000)
    assert is_pass == True, "fail the test"            
    

    for i in range(0, 200):
        if int_list.pop1() != 999 - i:
            correctOrder = False
                    
    is_pass = correctOrder
    assert is_pass == True, "fail the test" 
    
    is_pass = (int_list.search_larger(200) == 201)
    assert is_pass == True, "fail the test" 
    
    int_list.insert(7,801)   

    is_pass = (int_list.search_larger(800) == 7)
    assert is_pass == True, "fail the test"
    
    
    is_pass = (int_list.get_item(-1) == 799)
    assert is_pass == True, "fail the test"
    
    is_pass = (int_list.get_item(-4) == 796)
    assert is_pass == True, "fail the test"
            
    if is_pass == True:
        print ("=========== Congratulations! Your have finished exercise 1! ============")
        
if __name__ == '__main__':
    test()



and heres the tests im trying to pass:
from d_linked_list import *
import random

def test_sort_integer():
    integer_list = d_linked_list()
    
    for i in range(1000):
        data = random.randint(1, 1000)
        integer_list.append(data)
    
    #print(integer_list)
    
    integer_list.sort()
    
    #print(integer_list)
    
    prev_data = integer_list.pop(0)
    cur_data = integer_list.pop(0)
    
    while integer_list.get_size() > 0:
        assert cur_data >= prev_data, 'error: linked list is not sorted'
        
        prev_data = cur_data
        cur_data = integer_list.pop(0)
        
    print('========== cong ==================')

if __name__ == '__main__':
    test_sort_integer()


from d_linked_list import *
import random

def test_sort_by_attr(attr):
    item_list = d_linked_list()
    
    for i in range(10):
        name = 'goods' + str(i)
        price = random.randint(0, 1000)
        quantity = random.randint(1, 100)
        
        good = item(name, price, quantity)
        
        item_list.append(good)
    
    #print(item_list)
    
    item_list.sort_by_attr(attr)
    
    #print(item_list)
    
    prev_data = item_list.pop(0)
    cur_data = item_list.pop(0)
    
    while item_list.get_size() > 0:
        if attr == 'price':
            assert cur_data.get_price() >= prev_data.get_price(), \
            'error: linked list is not sorted by price'
        elif attr == 'quantity':
            assert cur_data.get_quantity() >= prev_data.get_quantity(), \
            'error: linked list is not sorted by quantity' 
        else:
            raise Exception('illegal attribute')           
        
        prev_data = cur_data
        cur_data = item_list.pop(0)
        
    print('========== cong on ' + attr + ' ==================')

def test_sort():
    test_sort_by_attr('price')
    test_sort_by_attr('quantity')

if __name__ == '__main__':
    test_sort()


but I know both my sort functions are wrong but I cant figure out why!!

Is This A Good Question/Topic? 1
  • +

Replies To: Sorting a double linked list

#2 jon.kiparsky  Icon User is online

  • Pancakes!
  • member icon


Reputation: 7872
  • View blog
  • Posts: 13,354
  • Joined: 19-March 11

Re: Sorting a double linked list

Posted 25 March 2013 - 02:21 PM

Please be more specific about what's happening, or what's not happening that you'd like to have happen. It's easier to help solve your problem if you tell us what your problem is!
Was This Post Helpful? 0
  • +
  • -

#3 medaa  Icon User is offline

  • D.I.C Head

Reputation: 6
  • View blog
  • Posts: 106
  • Joined: 24-October 12

Re: Sorting a double linked list

Posted 25 March 2013 - 02:27 PM

Heres the error Im getting:
File "d_linked_list.py", line 170, in sort
for index in range(len(self)):
builtins.TypeError: object of type 'd_linked_list' has no len()

I get the same error for both tests when I run them.
For the def sort(self), I want to sort a d-list in ascending order and for def sort by_att(self, attar):, I want to sort the list by either price or quantity
Im hoping you can look at my sort functions and tell me what Im doing wrong.
Was This Post Helpful? 0
  • +
  • -

#4 jon.kiparsky  Icon User is online

  • Pancakes!
  • member icon


Reputation: 7872
  • View blog
  • Posts: 13,354
  • Joined: 19-March 11

Re: Sorting a double linked list

Posted 25 March 2013 - 02:37 PM

len(foo) simply calls foo's __len__ method. You haven't defined that method for your linked list.
Was This Post Helpful? 0
  • +
  • -

#5 baavgai  Icon User is offline

  • Dreaming Coder
  • member icon

Reputation: 5874
  • View blog
  • Posts: 12,754
  • Joined: 16-October 07

Re: Sorting a double linked list

Posted 25 March 2013 - 02:37 PM

	def sort(self):
		for index in range(len(self)):
			smallindex=index
			for i in range(index,len(self)):
				if self[i]<self[smallindex]:



How exactly does len(self) work with your class? How does self[i] work? If you want that kind of functionality, you could write it. You haven't. Though you do have some methods you might consider calling. Note, sorting a linked list based on index position is probably the worst possible choice.
Was This Post Helpful? 0
  • +
  • -

#6 medaa  Icon User is offline

  • D.I.C Head

Reputation: 6
  • View blog
  • Posts: 106
  • Joined: 24-October 12

Re: Sorting a double linked list

Posted 25 March 2013 - 02:53 PM

what Im trying to do is take my list and go through each element and do a compare and swap type of thing
Was This Post Helpful? 0
  • +
  • -

#7 medaa  Icon User is offline

  • D.I.C Head

Reputation: 6
  • View blog
  • Posts: 106
  • Joined: 24-October 12

Re: Sorting a double linked list

Posted 25 March 2013 - 03:00 PM

Do you recommend at faster and simpler way?
Was This Post Helpful? 0
  • +
  • -

#8 baavgai  Icon User is offline

  • Dreaming Coder
  • member icon

Reputation: 5874
  • View blog
  • Posts: 12,754
  • Joined: 16-October 07

Re: Sorting a double linked list

Posted 25 March 2013 - 05:58 PM

Faster or simpler, pick one...

I'd just do a simple bubble sort. If you only swap the values, not the nodes, it's pretty straight forward. Even if do swap the nodes, it's not too bad.

Note, a proper bubble sort, not one of those horrid index loop things.

e.g.
def sort(self):
	if self.head and self.head.next:
		swapped = True
		while swapped:
			swapped = False
			node = self.head
			while node.next:
				if node.next.value < node.value:
					# ...



Hmmm... your instructions are to use a selection sort? Same deal, hold on to your nodes. Not indexes:
def sort(self):
	if self.head and self.head.next:
		i = self.head
		while i.next:
			selected = i
			j = i.next
			while j:
				if j.value < selected.value:
					# ...


Was This Post Helpful? 1
  • +
  • -

#9 medaa  Icon User is offline

  • D.I.C Head

Reputation: 6
  • View blog
  • Posts: 106
  • Joined: 24-October 12

Re: Sorting a double linked list

Posted 25 March 2013 - 10:48 PM

def sort(self):
    if self.head and self.head.next:
        i = self.head
        while i.next:
            selected = i
            j = i.next
            while j:
                if j.value < selected.value:
                    selected.value==self.head
                else:
                    j.value==self.head
 


Am I kinda on the right track, im still getting an error:

Traceback (most recent call last):
File "/Desktop/WingIDE.app/Contents/MacOS/src/debug/tserver/_sandbox.py", line 29, in <module>
File "/Desktop/WingIDE.app/Contents/MacOS/src/debug/tserver/_sandbox.py", line 21, in test_sort_integer
builtins.Assertionerror: error: linked list is not sorted
Was This Post Helpful? 0
  • +
  • -

#10 baavgai  Icon User is offline

  • Dreaming Coder
  • member icon

Reputation: 5874
  • View blog
  • Posts: 12,754
  • Joined: 16-October 07

Re: Sorting a double linked list

Posted 26 March 2013 - 04:46 AM

Not quite. Keep in mind, you're swapping "values" In a selection sort, there are two ways this is done; at the time or at the end of the inner loop, the latter being much more efficient.

Let's go back to your first sort:
# we're going to sort a list a, for demonstration purposes.
# def sort(self):
def selSort(a):
	# for each item
	# for index in range(len(self)):
	# note, a proper selection sort stops one from the end
	for i in range(len(a)-1):
		# look at what you're doing here
		# you're holding a reference to index i
		selected = i
		# you actually want to loop from i+1 to the end
		# for i in range(index,len(self)):
		for j in range(i+1,len(a)):
			# compare the selected value to the inner loop value
			if a[j]<a[selected]:
				# if the inner loop value is smaller
				# save the INDEX
				selected = j
		# you leave the inner loop, it's swap time
		# however, don't swap unless selected has changed from i
		if not selected==i:
			# we are swapping values
			tempVal = a[i] # hold so we don't loose
			a[i] = a[selected] # replace with selected value
			a[selected] = tempVal # complete swap




Back to a linked list. There is no len, but using head and last node as your start and stop values, it's pretty much the same logic.

The next line in the code I gave would be:
if j.value < selected.value:
	selected = j # understand?  We're hold the "index."  The node with the value we want to swap with node i.



Hope this helps.
Was This Post Helpful? 1
  • +
  • -

#11 medaa  Icon User is offline

  • D.I.C Head

Reputation: 6
  • View blog
  • Posts: 106
  • Joined: 24-October 12

Re: Sorting a double linked list

Posted 26 March 2013 - 09:32 AM

Okay Its slowly coming together.
Except I dont know what to do with this line or what its doing:

while integer_list.get_size() > 0


For instance in your example:

def sort(self):
        def sort(self):
            if self.head and self.head.next:
                i = self.head
                while i.next:
                    selected = i
                    j = i.next
                    while j:
                        if j.value < selected.value:
                            selected=j


How do you handle this piece of code, is it in the while j loop, or do I make a new loop?
Was This Post Helpful? 0
  • +
  • -

#12 baavgai  Icon User is offline

  • Dreaming Coder
  • member icon

Reputation: 5874
  • View blog
  • Posts: 12,754
  • Joined: 16-October 07

Re: Sorting a double linked list

Posted 26 March 2013 - 11:02 AM

You know, you still have to write the rest of that sort. You have swaps to make, nodes to move...

The integer_list.get_size() doesn't really make sense out of context. So, context:
# this is essentially one pass of a bubble sort
# if you have to make a swap, you fail
prev_data = integer_list.pop(0) # get the first value
cur_data = integer_list.pop(0) # get the second value

# this is actually pretty sloppy, we're assuming more than two items
while integer_list.get_size() > 0: # basically, we're just testing if there are more items
	# this check should to make sure that prev_data <= cur_data is true
	# as a sort should have made it
	# however, the = in >= is a bug and will fail if two values are the same, which should be valid
	assert cur_data >= prev_data, 'error: linked list is not sorted'
	
	# move forward
	# the current is now the previous
	prev_data = cur_data
	# the newly popped value is current
	cur_data = integer_list.pop(0)



Note, if the last value is out of order, this code will give you a pass.
Was This Post Helpful? 0
  • +
  • -

#13 medaa  Icon User is offline

  • D.I.C Head

Reputation: 6
  • View blog
  • Posts: 106
  • Joined: 24-October 12

Re: Sorting a double linked list

Posted 26 March 2013 - 03:10 PM

So I talked to my prof and he helped me work out a code:

from d_linked_node import d_linked_node
from item import item

class d_linked_list:
    
    def __init__(self):
        self.__head=None
        self.__tail=None
        self.__size=0        

            
    def search(self, item):
        current = self.__head
        found = False
        while current != None and not found:
            if current.getData() == item:
                found= True
            else:
                current = current.getNext()
        return found
        
    def index(self, item):
        current = self.__head
        found = False
        index = 0
        while current != None and not found:
            if current.getData() == item:
                found= True
            else:
                current = current.getNext()
                index = index + 1
        if not found:
                index = -1
        return index        
         
    def add(self, item):
        temp = d_linked_node(item,None,None)
        if (self.__tail == None):
            self.__head = temp
            self.__size += 1            
            self.__tail = temp
        else:
            temp.setNext(self.__head)            
            self.__head.setPrevious(temp)
            self.__head = temp
            self.__size += 1
        
    def remove(self, item):
        if (self.search(item)):
            inde = self.index(item)
            self.__size -= 1
            temp = self.__head
            if (inde == 0):
                self.__head = temp.getNext()
                if(self.__head == None):
                    self.__tail = None
                else:
                    self.__head.setPrevious(None)
            else:
                for i in range(inde):
                    temp = temp.getNext()
                a = temp.getPrevious()
                a.setNext(temp.getNext())
                if (a.getNext() == None):
                    self.__tail = a
                else:
                    a.getNext().setPrevious(a)
        
    def append(self, item):
        if self.__size == 0:
            self.add(item)
        else:
            self.__size +=1
            temp = d_linked_node(item,None,self.__tail)
            self.__tail.setNext(temp)
            self.__tail = temp
        
    def insert(self, pos, item):
        temp = self.__head
        temp_in = d_linked_node(item,None,None)
        for i in range(pos):
            temp = temp.getNext()        
        if (pos == 0):
            temp_in.setNext(self.__head)
            self.__head = temp_in
            if (self.__size == 0):
                self.__tail = temp_in
            else:
                temp_in.getNext().setPrevious(temp_in)
            self.__size +=1
        else:
            if (temp == None):
                temp_in.setPrevious(self.__tail)
                self.__tail.setNext(temp_in)
                self.__tail=temp_in
            else:
                temp_in.setNext(temp)
                temp.getPrevious().setNext(temp_in)
                temp_in.setPrevious(temp.getPrevious())
                temp.setPrevious(temp_in)
            self.__size +=1
      
        
    def pop1(self):
        temp = self.__tail
        if (self.__size < 2):
            self.__head = None
            self.__tail = None
            self.__size = 0
        else:            
            temp.getPrevious().setNext(None)
            self.__tail = temp.getPrevious()
            self.__size -= 1          
        return temp.getData()
        
    def pop(self, pos):
        self.__size -= 1
        temp = self.__head
        if (pos == 0):
            self.__head = temp.getNext()
            if(self.__head == None):
                self.__tail = None
            else:
                self.__head.setPrevious(None)
            return temp.getData()
        else:
            for i in range(pos):
                temp = temp.getNext()
            a = temp.getPrevious()
            a.setNext(temp.getNext())
            if (a.getNext() == None):
                self.__tail = a
            else:
                a.getNext().setPrevious(a)
            return temp.getData()
        
    def search_larger(self, item):
        temp = self.__head
        a = 0
        while temp != None:
            if (temp.getData() > item):
                break
            temp = temp.getNext()
            a +=1
        if(temp == None):
            return -1
        return a
        
    def get_size(self):
        return self.__size    
    
    def get_item(self, pos):
        if (pos < 0):
            if (pos < -self.__size):
                raise Exception("pos doesn't exist")
            temp = self.__tail
            for i in range(pos,-1):
                temp = temp.getPrevious()
            return temp.getData()
        else:
            if (pos >= self.__size):
                raise Exception("pos doesn't exist")
            temp = self.__head
            for i in range(0,pos):
                temp = temp.getNext()     
            return temp.getData()
 
    
    def select_least(self):
        least=self.__head
        current=self.__head
        while current.getNext(): 
            current=current.getNext()
            if current.getData()<least.getData(): 
                least=current
        return least
    
    def sort(self):
        sorted_list = d_linked_list()
        while self.__size > 0:
            remaining = self.select_least()
            sorted_list.append(remaining)
            self.remove(remaining)
        self.__head = sorted_list.head
        self.__tail = sorted_list.tail
        self.__size = sorted_list.size   
        pass
                                 
                        
    def sort_by_attr(self, attr):
        if attr=="Price":
            sorted_list = d_linked_list()
            while self.__size> 0:
                remaining = self.select_least()
                sorted_list.append(remaining)
                self.remove(remaining)
                self.__head = sorted_list.head
                self.__tail = sorted_list.tail
                self.__size = sorted_list.size           
            
                            
        elif attr=="Quantity":
            sorted_list = d_linked_list()
            while self.__size> 0:
                remaining = self.select_least()
                sorted_list.append(remaining)
                self.remove(remaining)
                self.__head = sorted_list.head
                self.__tail = sorted_list.tail
                self.__size = sorted_list.size              
            
                        
                                
    def __str__(self):
        temp = self.__head
        pr = ""
        while (temp != None):
            pr = pr + str(temp.getData()) + " "
            temp = temp.getNext()
        pr = pr[:-1]
        return pr

def test():
          
    linked_list = d_linked_list()
            
    is_pass = (linked_list.get_size() == 0)
    assert is_pass == True, "fail the test"
    
    linked_list.add("World")
    linked_list.add("Hello")    
    
    is_pass = (str(linked_list) == "Hello World")
    assert is_pass == True, "fail the test"
        
    is_pass = (linked_list.get_size() == 2)
    assert is_pass == True, "fail the test"
    
    is_pass = (linked_list.get_item(0) == "Hello")
    assert is_pass == True, "fail the test"


    is_pass = (linked_list.get_item(1) == "World")
    assert is_pass == True, "fail the test"    
    
    is_pass = (linked_list.get_item(0) == "Hello" and linked_list.get_size() == 2)
    assert is_pass == True, "fail the test"
    
    is_pass = (linked_list.pop(1) == "World")
    assert is_pass == True, "fail the test"     
    
    is_pass = (linked_list.pop1() == "Hello")
    assert is_pass == True, "fail the test"     
    
    is_pass = (linked_list.get_size() == 0)
    assert is_pass == True, "fail the test" 
    
    
        

            
    int_list2 = d_linked_list()
            
    for i in range(0, 10):
        int_list2.add(i)      
    int_list2.remove(1)
    int_list2.remove(3)
    int_list2.remove(2)
    int_list2.remove(0)
    is_pass = (str(int_list2) == "9 8 7 6 5 4")
    assert is_pass == True, "fail the test"
        
    for i in range(11, 13):
        int_list2.append(i)
    is_pass = (str(int_list2) == "9 8 7 6 5 4 11 12")
    assert is_pass == True, "fail the test"
        
    for i in range(21, 23):
        int_list2.insert(0,i)
    is_pass = (str(int_list2) == "22 21 9 8 7 6 5 4 11 12")
    assert is_pass == True, "fail the test"
        
    is_pass = (int_list2.get_size() == 10)
    assert is_pass == True, "fail the test"    
            
    int_list = d_linked_list()
            
    is_pass = (int_list.get_size() == 0)
    assert is_pass == True, "fail the test"
            

            
    for i in range(0, 1000):
        int_list.append(i)      
    correctOrder = True
    
    is_pass = (int_list.get_size() == 1000)
    assert is_pass == True, "fail the test"            
    

    for i in range(0, 200):
        if int_list.pop1() != 999 - i:
            correctOrder = False
                    
    is_pass = correctOrder
    assert is_pass == True, "fail the test" 
    
    is_pass = (int_list.search_larger(200) == 201)
    assert is_pass == True, "fail the test" 
    
    int_list.insert(7,801)   

    is_pass = (int_list.search_larger(800) == 7)
    assert is_pass == True, "fail the test"
    
    
    is_pass = (int_list.get_item(-1) == 799)
    assert is_pass == True, "fail the test"
    
    is_pass = (int_list.get_item(-4) == 796)
    assert is_pass == True, "fail the test"
            
    if is_pass == True:
        print ("=========== Congratulations! Your have finished exercise 1! ============")
        
if __name__ == '__main__':
    test()



I added a new function called select_least.

Does it make sense?

so my sort function has changed as you can see
Was This Post Helpful? 1
  • +
  • -

#14 baavgai  Icon User is offline

  • Dreaming Coder
  • member icon

Reputation: 5874
  • View blog
  • Posts: 12,754
  • Joined: 16-October 07

Re: Sorting a double linked list

Posted 27 March 2013 - 05:39 AM

It makes sense. It's kind of an inside out selection sort. But look at all the work you're doing! And there are a number of bugs, I'm afraid.

You're returning a node, which is good. You're appending the NODE to your new list, which is wrong. You're calling remove on the value ( which is still wrong, because it's a node. )

You should be able to remove the returned node from your list without calling anything. Though, a private removeNode method would be good.

Removing that node is complex. Swapping values wouldn't be. Inserting in order wouldn't be, either. You're making it harder on yourself, really.

The sort I offered only has a few more lines to complete it. Less code than that select_least... which has a bug in it, btw. It will crash on an empty list.
Was This Post Helpful? 1
  • +
  • -

#15 medaa  Icon User is offline

  • D.I.C Head

Reputation: 6
  • View blog
  • Posts: 106
  • Joined: 24-October 12

Re: Sorting a double linked list

Posted 27 March 2013 - 09:45 AM

This was quite a hard exercise for me and my classmates so my prof decided to forget about it. But im so frustrated now because Ive tried a bunch of things and I cant figure it out. Is it possible if you can show me your completed code and explain to me how you got it one last time if you have time.
Was This Post Helpful? 0
  • +
  • -

  • (2 Pages)
  • +
  • 1
  • 2