CODEWITHSUNDEEP
sortingpython-3.xlinked-list
Suliman Sharif
Suliman Sharif

Reputation: 607

Sorting a Linked List in Python

I am having a tough time sorting out linked list. I was thinking of stripping each item in the list and appending each one to a new list and adding in order. But I want to sort them while in the list. I worked it out logically and drew it out but it doesn't seem to be working haha. For simplicity sake I am snipping out a lot of my code the rest of my code since they are not needed.

class Node:

    def __init__(self, initdata, position = 0):

        self.data = initdata
        self.next = None
        self.position = position

    def getData(self):
        return self.data

    def getNext(self):
        return self.next

    def setData(self, newdata):
        self.data = newdata

    def setNext(self, newnext):

        self.next = newnext

    def __str__(self):
        return str(self.data)

class LinkedList:

    def __init__(self):

        self.head = None
        self.tail = None

    def sortList(self):

        previous = self.head
        current = previous.getNext() # Earth
        temp = current.getNext() #Venus
        stop = False
        while current != None: #None
            if current.getData() > temp.getData():
                previous.setNext(temp)
                temp.setNext(current)
                current.setNext(temp.getNext())
                previus = current
                current = temp
                temp = temp.getNext()
            else:
                previous = current
                current = temp
                temp = temp.getNext()

So the Linked List is as follows, with the head being Earth

[Earth] points to [Venus] points to [Mercury] points to None

I want

[Earth] points to [Mercury] points to [Venus] points to None

So far I have not gotten this result after numerous trials :( Any help?

Upvotes: 0

Views: 3904

Answers (1)

rcgldr
rcgldr

Reputation: 28951

When swapping nodes, swapping adjacent nodes ends up rotating 3 next pointers, while swapping non-adjacent nodes swaps 2 pairs of next pointers. Both cases can be handled by swapping the next pointers of the nodes prior to the nodes to be swapped, then swapping the next pointers of the nodes to be swapped, in that order.

The code also needs to handle the case where a node is the first node of the list (in which case the head pointer is updated) and where a node is the last node of the list (in which case the tail pointer is updated).

The first method you mentioned, removing nodes from the original list and then inserting them in order into an initially empty list should be easier and faster.

The fastest method is to use an array (size 26 to 32) of head pointers that are either NULL or point to a list of size 2^i (2 to the power i). The algorithm uses a basic merge list function that merges two already sorted lists. Nodes are inserted into the array one at a time. Then the array is merged to form the final sorted array. This is the method used by C++ std::list:sort() (at least for HP / Microsoft STL).

Upvotes: 1

Related Questions