Question

// The Song class that represents a song
// Do not make any changes to this file!

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;
}
}

Complete the required methods:

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)
{
// TODO: implement this method
}
  
  
// 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)
   {
       Song song = new Song(artist, title); // create a new Song with given artist and title
       if(isEmpty()) // empty list, make m_last equal to song
       {
           m_last = song;
           m_last.setLink(m_last); // set link of m_last to itself
       }
       else // non-empty list
       {
           // curr to first node
           Song curr = m_last.getLink();
           Song prev = m_last; // prev to last node
          
           // loop over the list until curr is 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
               }
              
               prev = curr;
               curr = curr.getLink();
           }
          
           // curr has not reached the last node
           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
           {
               // compare title of song with title of last node
               if(curr.getTitle().compareTo(title) > 0) // song's title < m_last's title, insert before curr
               {
                   song.setLink(curr); // 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()) // not an empty list
       {
           // curr to first node and prev to last node
           Song curr = m_last.getLink();
           Song prev = m_last;
          
           // loop over the list until curr = 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 artistList = new SongList();
       if(!isEmpty()) // not an empty list
       {
           // curr to first node
           Song curr = m_last.getLink();
          
           // loop over the list until curr is the last node
           while(curr != m_last)
           {
               // curr's = artist
               if(curr.getArtist().equals(artist))
               {
                   artistList.add(curr.getArtist(), curr.getTitle()); // insert curr's song into artistList
               }
              
               curr = curr.getLink();
           }
          
           // last node's artist = artist, insert last node's data into artistList
           if(m_last.getArtist().equals(artist))
               artistList.add(m_last.getArtist(), m_last.getTitle());
       }
      
       return artistList;
   }
  
   // 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