Question

You are provided with the files "Song.java" and "SongList.java". You are required complete the methods in the latter file to implement the sorted circular linked list. The list is sorted according to the title of each song in alphabetical order. You need to write these methods: add(String artist, String title) – This method takes an artist and a title and adds a Song node with these values into the list. The list must still be sorted in ascending order by song title. You do not need to handle duplicates – you can assume that we never insert the same song for more than once. This method takes an artist and a title and remove a Song node that matches the artist and the title from the list. If remove is successful, return true. If no such node exists, return false. buildList(String artist) – This method takes an artist and searches in the list for all the song nodes associated with this artist. It then adds all these nodes into a new sorted circular linked list and returns it as a SongList object. Do not alter the original song list in this method.

public class Song
{
// instance variables
private String m_artist;
private String m_title;
private Song m_link;

// constructor
public Song(String artist, String title)
{
m_artist = artist;
m_title = title;
m_link = null;
}

// getters and setters
public void setArtist(String artist)
{
m_artist = artist;
}

public String getArtist()
{
return m_artist;
}

public void setTitle(String title)
{
m_title = title;
}

public String getTitle()
{
return m_title;
}
  
public void setLink(Song link)
{
m_link = link;
}

public Song getLink()
{
return m_link;
}
}

public class SongList
{
// instance variables
private Song m_last;
private int m_numElements;

// constructor
// Do not make any changes to this method!
public SongList()
{
m_last = null;
m_numElements = 0;
}

// check whether the list is empty
// Do not make any changes to this method!
boolean isEmpty()
{
if (m_last == null)
return true;
else
return false;
}

// return the size of the list (# of Song nodes)
// Do not make any changes to this method!
public int size()
{
return m_numElements;
}

// add a new Song to the circular linked list with the given artist and
// title, keeping the list sorted by *song title*.
public void add(String artist, String title)
{
// TODO: implement this method
}

// remove a Song associated with the given artist and title from the list,
// keeping the list sorted by *song title*.
public boolean remove(String artist, String title)
{
find(artist);
if(found)
{
if (Songlist == Songlist.getLink())
list = null;
else if (previous.getLink() == Songlist)
previous.setLink(m_last.getLink());
numElements--;
}
  
return found;

}
  
  
// build and return a circular linked list that contains all songs from the
// given artist
public SongList buildList(String artist)
{
// TODO: implement this method
}
  
// return a string representation of the list
// Do not make any changes to this method!
public String toString()
{   
String listContent = "";
Song current = m_last;
  
if (m_last != null)
do
{
current = current.getLink();
listContent += " [" + current.getArtist() + " - " + current.getTitle() + "]\n";

} while (current != m_last);

return listContent;
}
}

Answer 1

// Song.java

public class Song
{
   // instance variables
   private String m_artist;
   private String m_title;
   private Song m_link;

   // constructor
   public Song(String artist, String title)
   {
       m_artist = artist;
       m_title = title;
       m_link = null;
   }

   // getters and setters
   public void setArtist(String artist)
   {
       m_artist = artist;
   }

   public String getArtist()
   {
       return m_artist;
   }

   public void setTitle(String title)
   {
       m_title = title;
   }

   public String getTitle()
   {
       return m_title;
   }
  
   public void setLink(Song link)
   {
       m_link = link;
   }

   public Song getLink()
   {
       return m_link;
   }
}

//end of Song.java

// SongList.java

public class SongList {

   // instance variables
   private Song m_last;
   private int m_numElements;

   // constructor
   // Do not make any changes to this method!
   public SongList()
   {
       m_last = null;
       m_numElements = 0;
   }

   // check whether the list is empty
   // Do not make any changes to this method!
   boolean isEmpty()
   {
       if (m_last == null)
           return true;
       else
           return false;
   }

   // return the size of the list (# of Song nodes)
   // Do not make any changes to this method!
   public int size()
   {
       return m_numElements;
   }

   // add a new Song to the circular linked list with the given artist and
   // title, keeping the list sorted by *song title*.
   public void add(String artist, String title)
   {
       // create a new Song node
       Song song = new Song(artist, title);
      
       if(isEmpty()) // list is empty
       {
           m_last = song; // set m_last to song
           m_last.setLink(m_last); // set link of m_last to itself
       }
       else // list is not empty
       {
           // initialize curr to first node i.e m_last.link
           Song curr = m_last.getLink();
          
           Song prev = m_last; // initialize prev to last node i.e node previous to curr
          
           // loop over the list until curr reaches the last node
           while(curr != m_last)
           {
               if(curr.getTitle().compareTo(title) > 0) // title of curr > title of song, insert before curr
               {
                   break; // exit the loop
               }
              
               // move the pointer to the next node
               prev = curr;
               curr = curr.getLink();
           }
          
           // curr is not the last node, hence insert song before curr
           if(curr != m_last)
           {
               song.setLink(curr); // set song's link to curr
               prev.setLink(song); // set prev's link to song
           }
           else // curr has reached the last node
           {
               // curr points to m_last
               if(m_last.getTitle().compareTo(title) > 0) // song's title < m_last's title, insert before m_last
               {
                   song.setLink(m_last); // set song's link to curr
                   prev.setLink(song); // set prev's link to song
               }
               else // make song the last node
               {
                   // set song's link to the first node
                   song.setLink(m_last.getLink());
                   m_last.setLink(song); // set m_last's link to song
                   m_last = song; // update m_last to song
               }
           }
       }
      
       m_numElements++; // increment number of elements
   }
  
   // remove a Song associated with the given artist and title from the list,
   // keeping the list sorted by *song title*.
   public boolean remove(String artist, String title)
   {
      
       if(!isEmpty()) // list is not empty
       {
           // initailize curr to first node and prev to last node i.e node previous to curr
           Song curr = m_last.getLink();
           Song prev = m_last;
          
           // loop over the list until curr reaches last node
           while(curr != m_last)
           {
               // curr's title and artist match, remove curr
               if(curr.getArtist().equals(artist) && curr.getTitle().equals(title))
               {
                   // set link of prev to link of curr
                   prev.setLink(curr.getLink());
                   m_numElements--; // decrement number of elements
                   return true; // deletion successful
               }
              
               prev = curr;
               curr = curr.getLink();
           }
      
           // last node is the node to remove
           if(m_last.getArtist().equals(artist) && m_last.getTitle().equals(title))
           {
               // list contains 1 element, set it to empty list
               if(m_last.getLink() == m_last)
               {
                   m_last = null;
               }
               else
               {
                   prev.setLink(m_last.getLink()); // set prev's link to first node
                   m_last = prev; // update m_last to prev
               }
              
               m_numElements--; // decrement number of elements
               return true; // delete successful
           }
          
       }
      
       return false; // delete failed
   }
  
  
   // build and return a circular linked list that contains all songs from the
   // given artist
   public SongList buildList(String artist)
   {
       // create an empty list to contain the songs of artist
       SongList result = new SongList();
      
       if(!isEmpty()) // list is not empty
       {
           // initialize curr to first node
           Song curr = m_last.getLink();
          
           // loop over the list until curr reaches the last node
           while(curr != m_last)
           {
               // curr's artist = artist
               if(curr.getArtist().equals(artist))
               {
                   result.add(curr.getArtist(), curr.getTitle()); // insert curr's song into result
               }
              
               curr = curr.getLink();
           }
          
           // last node's artist = artist, insert last node's data into result
           if(m_last.getArtist().equals(artist))
               result.add(m_last.getArtist(), m_last.getTitle());
       }
      
       return result;
   }
  
   // return a string representation of the list
   // Do not make any changes to this method!
   public String toString()
   {   
       String listContent = "";
       Song current = m_last;
      
       if (m_last != null)
       do
       {
           current = current.getLink();
           listContent += " [" + current.getArtist() + " - " + current.getTitle() + "]\n";
  
       } while (current != m_last);
  
       return listContent;
   }
}

//end of SongList.java