Linked list write in Python please, Please edit the sortList function where we g
ID: 3828848 • Letter: L
Question
Linked list write in Python please, Please edit the sortList function where we get an unsorted list and we return a sorted list
Please also write the isSorted function
import random
class Link (object):
def __init__(self, data = None):
self.data = data
self.next = None
def get_next(self):
return self.next
def set_next(self, n):
self.next = n
def get_data(self):
return self.data
def set_data(self, d):
self.data = d
def __str__(self):
return str(self.data)
class LinkedList(object):
def __init__(self, r = None):
self.root = r
self.size = 0
def getNumLinks(self):
return self.size
def addFirst(self, data):
link = Link(data)
link.next = self.root
self.root = link
self.size += 1
def addLast(self, data):
if self.root == None:
self.addFirst(data)
return
else:
link = Link(data)
temp = self.root
while(temp.next):
temp = temp.next
temp.next = link
self.size += 1
def addInOrder(self, data):
if self.root is None:
data.next = self.root
self.root = data
elif self.root.data >= data.data:
data.next = self.root
self.root = data
else:
current = self.root
while(current.next is not None and current.next.data < data.data):
current = current.next
data.next = current.next
current.next = data
self.size += 1
def findUnordered(self, data):
this = self.root
while this.next:
if this.data == data:
return True
else:
this = this.get_next()
return None
def findOrdered(self, data):
this = self.root
while this.next:
if this.data == data:
return True
else:
this = this.get_next()
return None
def delete(self, data):
de = self.root
prev = None
while de.next:
if de.data == data:
if prev:
prev.set_next(de.get_next())
else:
self.root = de
self.size -= 1
return "Deleted Data"
else:
prev = de
de = de.get_next()
return "Could not delete data"
def __str__(self):
if self.root == None:
return "List is empty"
temp = self.root
out = str(temp.data) + " "
while(temp.next):
temp = temp.next
out += str(temp.data) + " "
return out
def copyList(self):
empty = LinkedList()
current = self.root
while current.next != None:
empty.addLast(current.data)
current = current.next
empty = str(empty) + str(current.data)
return empty
def reverseList(self):
prev = None
current = self.root
while current != None:
next = current.next
current.next = prev
prev = current
current = next
self.root = prev
def sortList(self):
prev = self.root
current = prev.get_next()
temp = current.get_next()
#stop = False
while current != None:
if current.get_data() > temp.get_data():
prev.set_next(temp)
temp.set_next(current)
current.set_next(temp.get_next())
prev = current
current = temp
temp = temp.get_next()
else:
prev = current
current = temp
temp = temp.get_next()
return current
def isSorted():
def main():
lis1 = LinkedList()
for i in range(12):
new = random.randint(1, 99)
lis1.addFirst(new)
print(lis1)
main()
Explanation / Answer
import random
class Link (object):
def __init__(self, data = None):
self.data = data
self.next = None
def get_next(self):
return self.next
def set_next(self, n):
self.next = n
def get_data(self):
return self.data
def set_data(self, d):
self.data = d
def __str__(self):
return str(self.data)
class LinkedList(object):
def __init__(self, r = None):
self.root = r
self.size = 0
def getNumLinks(self):
return self.size
def addFirst(self, data):
link = Link(data)
link.next = self.root
self.root = link
self.size += 1
def addLast(self, data):
if self.root == None:
self.addFirst(data)
return
else:
link = Link(data)
temp = self.root
while(temp.next):
temp = temp.next
temp.next = link
self.size += 1
def addInOrder(self, data):
if self.root is None:
data.next = self.root
self.root = data
elif self.root.data >= data.data:
data.next = self.root
self.root = data
else:
current = self.root
while(current.next is not None and current.next.data < data.data):
current = current.next
data.next = current.next
current.next = data
self.size += 1
def findUnordered(self, data):
this = self.root
while this.next:
if this.data == data:
return True
else:
this = this.get_next()
return None
def findOrdered(self, data):
this = self.root
while this.next:
if this.data == data:
return True
else:
this = this.get_next()
return None
def delete(self, data):
de = self.root
prev = None
while de.next:
if de.data == data:
if prev:
prev.set_next(de.get_next())
else:
self.root = de
self.size -= 1
return "Deleted Data"
else:
prev = de
de = de.get_next()
return "Could not delete data"
def __str__(self):
if self.root == None:
return "List is empty"
temp = self.root
out = str(temp.data) + " "
while(temp.next):
temp = temp.next
out += str(temp.data) + " "
return out
def copyList(self):
empty = LinkedList()
current = self.root
while current.next != None:
empty.addLast(current.data)
current = current.next
empty = str(empty) + str(current.data)
return empty
def reverseList(self):
prev = None
current = self.root
while current != None:
next = current.next
current.next = prev
prev = current
current = next
self.root = prev
def sortList(self):
new1 = self.root
while(new1.get_next()):
count = new1.get_next()
while(count):
if(new1.get_data() > count.get_data()):
temp = new1.get_data()
new1.set_data(count.get_data())
count.set_data(temp)
count = count.get_next()
new1 = new1.get_next()
# Return True if a list is sorted in ascending order or False otherwise
def isSorted(self):
n = self.root
while n.get_next():
if n.get_data() > n.get_next().get_data():
return False
n = n.get_next()
return True
def main():
lis1 = LinkedList()
for i in range(12):
new = random.randint(1, 99)
lis1.addFirst(new)
print(lis1)
if lis1.isSorted():
print "Already sorted"
else:
print "List is not in sorted order. Sorting...."
lis1.sortList()
print(lis1)
if lis1.isSorted():
print "Successfully sorted list"
main()
'''
Sample run
python main.py
8 46 89 83 72 90 42 48 88 47 38 91
List is not in sorted order. Sorting....
8 38 42 46 47 48 72 83 88 89 90 91
Successfully sorted list
'''
# link to the code in case indentation mess up.https://goo.gl/qKrX8v
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.