python: how to check if linked list is sorted

Question

I'm trying to understand the concepts of Linked Lists. I've searched for information about my question but I haven't found any answer which would help me. I'd like to know how to check if linked list is sorted? Evidently, we can't use the simple two lines function as for regular lists. For example if I want to check if my list is sorted(without using list.sort()), I'll create the function like this:

def is_sorted(l):
return all(a <= b for a, b in zip(l[:-1], l[1:]))

But for the linked list, should I compare list tail and head values? How it works exactly?

Contruction I use to create Linked Lists:

class Node :
    def __init__(self, data):
        self.data = data
        self.next = None
        self.prev = None

class LinkedList:
    def __init__(self):
        self.head = None        

    def add(self, data):
        node = Node(data)
            if self.head == None:   
                self.head = node
            else:
                node.next = self.head
                node.next.prev = node                       
                self.head = node            

    def search(self, k):
        p = self.head
        if p != None :
            while p.next != None :
                if ( p.data == k ) :
                    return p                
                p = p.next
            if ( p.data == k ) :
                return p
        return None

    def remove( self, p ) :
        tmp = p.prev
        p.prev.next = p.next
        p.prev = tmp        

    def __str__( self ) :
        s = ""
        p = self.head
        if p != None :      
            while p.next != None :
                s += p.data
                p = p.next
            s += p.data
        return s

score 3 · Accepted Answer · answered Nov 09 '16 at 01:10

You can do basically the same thing. The only caveat is that you need a way to iterate over your linked list...

class LinkedList:
    ...

    def __iter__(self):
        p = self.head
        while p:
            # I yield the data for simplicity in this problem.
            # Depending on the constraints for linked lists, it might be
            # nicer to yield nodes.
            yield p.data
            p = p.next

Now that we have that, checking if it is sorted is easy and pretty much analogous to the method you wrote for lists earlier:

def is_sorted(linked_list):
    iter1 = iter(linked_list)
    iter2 = iter(linked_list)
    next(iter2, None)  # drop the first element in iter2.
    return all(i1 <= i2 for i1, i2 in zip(iter1, iter2))

Also note that having a method for iterating over the linked list really simplifies other methods that you've already written. e.g.

def __str__(self):
    return ''.join(iter(self))  # Original code assumes string data, so I do too.

score 0 · Answer 2 · edited May 23 '17 at 10:32

Calling this a linkedList does not cause it to become compatible with Python's list type. :-)

Your LinkedList class doesn't have the methods necessary to make it an iterable object in Python. Thus, you can't use the built-in functions that work on iterables. You'd have to write a new method to check the list: traverse from head to tail, checking that each element's value is >= the previous one.

Alternatively, look up the additional methods needed to make this an iterable (you need more methods of the form ), and then apply your known solution.

python: how to check if linked list is sorted

2 Answers2