University of Arizona, Department of Computer Science

CSc 120: Sorting a linked list

Expected Behavior

Write a Python method sort() to sort a LinkedList object in descending order of the attribute _value. The code for the LinkedList class is shown below. You should use the sorting algorithm described here.

Given a LinkedList object llist, the execution of the code

llist.sort() print(llist)

should cause the sorted list to be printed out.

The code for the LinkedList class is as follows:

class Node:
    def __init__(self, value):
        self._value = value
        self._next = None
    
    # getter for the _value attribute
    def value(self):
        return self._value
    
    # getter for the _next attribute
    def next(self):
        return self._next
        
    def __str__(self):
        return str(self._value) + "; "
    
class LinkedList:
    def __init__(self):
        self._head = None

    # add a node to the head of the list
    def add(self, node):
        node._next = self._head
        self._head = node
        
    # remove a node from the head of the list and return the node
    def remove(self):
        assert self._head != None
        _node = self._head
        self._head = _node._next
        _node._next = None
        return _node
    
    # insert node2 after node1
    def insert(self, node1, node2):
        assert node1 != None
        node2._next = node1._next
        node1._next = node2
    
    def __str__(self):
        string = 'List[ '
        curr_node = self._head
        while curr_node != None:
            string += str(curr_node)
            curr_node = curr_node.next()
        string += ']'
        return string

Examples

Code:

ll = LinkedList() ll.add(Node(1)) ll.add(Node(3)) ll.add(Node(2)) ll.sort() print(ll)
Result: (this is the string returned by the __str__() method for the LinkedList class)

List[ 3; 2; 1; ]
Code:

ll = LinkedList() ll.sort() print(ll)
Result:

List[ ]
Code:

ll = LinkedList() ll = LinkedList() ll.add(Node(1)) ll.add(Node(1)) ll.add(Node(1)) ll.sort() print(ll)
Result:

List[ 1; 1; 1; ]