I have been trying to implement a Linked List in Python, and have been given this task of sorting it based on of the string values present in the Linked List.
I am trying to use the bubble sort logic and the below function is what I have come up with:
def sort_linked_list(self):
temp = self.head_node
if(temp == None) | (temp.next == None):
return
while(temp is not None):
if(temp.song.song_name > temp.song.song_name):
prev = temp
temp = temp.next
temp.next = prev
temp = temp.next
return
Unfortunately, this iterates over the first two values in my Linked List and is stuck in an infinite loop. I am pretty new to Linked List, hence might be making some fundamental mistake in this loop which I am unable to identify.
Any help is appreciated. Request to please add the explanation to the solution so that I can understand.
The code for the Linked List part:
class Song:
def __init__(self, song_id, song_name, song_length):
self.song_id = song_id
self.song_name = song_name
self.song_length = song_length
def __str__(self):
return str({'song_id':self.song_id,
'song_name':self.song_name,
'song_length':self.song_length})
# Node for each of teh cong object that is going to be created.
# Each of these node will contain the song data nd reference to the next element
class ListNode:
def __init__(self, song:Song):
self.song = song
self.next = None
def __str__(self):
return str(self.song)
# Linked list class that will be used to do the various operations
# Insert, create, delete, traversal of the linked list
# Few other operation such as
# a. deletion of song,
# b. sorting a linked list based on song
# c. randomly picking a song for playing
class LinkedList:
def __init__(self):
self.head_node = None
self.count = 0
# Traversing the linked lists
def traversal(self):
if self.head_node is None:
return
temp_node = self.head_node
while(temp_node != None):
print(temp_node.song)
time.sleep(2)
temp_node = temp_node.next
time.sleep(2)
return
# insertion of the node in the beginning of the linked lists
def insert_at_start(self, node):
if self.head_node is None:
self.head_node = node
self.count = self.count 1
return True
node.next = self.head_node
self.head_node = node
return True
# insertion of the node after a particular song
def insert_after(self, song_name, node):
temp_node = self.head_node
# Checking till we find the song_name we are looking for
while(temp_node.song.song_name!=song_name):
temp_node = temp_node.next
# if song is not found
if temp_node is None:
return False
# if song is found
else:
# Chckinhg if it is the last node
if temp_node.next == None:
temp_node.next = node
# If it is not the last node
else:
node.next = temp_node.next
temp_node.next = node
return True
# insertion of the node before a particular song in the linked lists
def insert_before(self, song_name, node):
temp_node = self.head_node
prev_node = None
# Checking till we find the song_name we are looking for
while(temp_node.song.song_name!=song_name):
prev_node = temp_node
temp_node = temp_node.next
# if song is not found
if temp_node == None:
return False
# if list has only one song
if prev_node == None:
node.next = self.head_node
self.head_node = node
return True
# updating the linked list and inserting the data
prev_node.next = node
node.next = temp_node
return True
CodePudding user response：
A few issues with your attempt:
The algorithm only makes one visit to every node. It is not possible to sort a list in just one sweep. Bubble sort needs two loops (nested). The outer loop keeps looping for as long as the inner loop had to make swaps. Once the inner loop does not find any pair to swap, the list is sorted, and the outer loop can stop.
A swap of two adjacent nodes in general needs two references to change. The
nextattribute of the node that sits before that pair needs to be changed as well, and your code is not doing that.Sorting may mean that that what was originally the head node, no longer sits at the head, and so your code must foresee an assignment to
self.head_node... or else the "sorted" version will always start with the same node as before the sort happened.
I would suggest to first create a dummy node that sits before the head node. This helps to simplify the code when the head node needs to be swapped. In that case the dummy's next attribute will change just like any other node's next can change. When all is done, we can then read what is the node that comes after the dummy, and make it the new head node.
def sort_linked_list(self):
sentinel = ListNode(None)
sentinel.next = self.head_node
dirty = True
while dirty: # Repeat until the inner loop finds nothing to swap
dirty = False
node = sentinel
# keep comparing the pair that follows after(!) `node`
while node.next and node.next.next:
first = node.next
second = first.next
if first.song.song_name > second.song.song_name:
# A swap needs to set two(!) next attributes
node.next = second
first.next = second.next
second.next = first
dirty = True # Indicate that the outer loop needs another iteration
node = node.next
# Make sure the head node references the right node after sorting
self.head_node = sentinel.next
Here is a demo which quickly creates a few nodes with your classes and then runs the above method and finally traverses the sorted list:
# Your code without change, except in the `sort_linked_list` method
class Song:
def __init__(self, song_id, song_name, song_length):
self.song_id = song_id
self.song_name = song_name
self.song_length = song_length
def __str__(self):
return str({'song_id':self.song_id,
'song_name':self.song_name,
'song_length':self.song_length})
class ListNode:
def __init__(self, song:Song):
self.song = song
self.next = None
def __str__(self):
return str(self.song)
class LinkedList:
def __init__(self):
self.head_node = None
self.count = 0
def traversal(self):
if self.head_node is None:
return
temp_node = self.head_node
while(temp_node != None):
print(temp_node.song)
temp_node = temp_node.next
return
def insert_at_start(self, node):
if self.head_node is None:
self.head_node = node
self.count = self.count 1
return True
node.next = self.head_node
self.head_node = node
return True
def sort_linked_list(self):
sentinel = ListNode(None)
sentinel.next = self.head_node
dirty = True
while dirty: # Repeat until the inner loop finds nothing to swap
dirty = False
node = sentinel
# keep comparing the pair that follows after(!) `node`
while node.next and node.next.next:
first = node.next
second = first.next
if first.song.song_name > second.song.song_name:
# A swap needs to set two(!) next attributes
node.next = second
first.next = second.next
second.next = first
dirty = True # Indicate that the outer loop needs another iteration
node = node.next
# Make sure the head node references the right node after sorting
self.head_node = sentinel.next
# Demo
titles = [
"Smells Like Teen Spirit",
"Billie Jean",
"Stayin’ Alive",
"I Will Survive",
"Whole Lotta Love",
"Sweet Child O’Mine",
"Scream and Shout",
"Santeria",
"Alright",
"Thrift Shop"
]
lst = LinkedList()
for i, title in enumerate(titles):
lst.insert_at_start(ListNode(Song(i, title, len(title))))
lst.sort_linked_list()
lst.traversal() # Outputs the 10 songs in sorted order