Insert() node method in java?

Question

I have a LinkedList that I have created when used creates a Band, Song, and Duration of the song list.

Example output:

What I can't figure out is how to implement a method where I can insert a node in any given position. So far my code looks like this:

public class Song {
    private String band;
    private String name;
    private double duration;
    Song next;
    
    public Song(String band, String name, double duration) {
        this.band = band;
        this.name = name;
        this.duration = duration;
    }

    public String getBand() {
        return band;
    }

    public void setBand(String band) {
        this.band = band;
    }


    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public double getDuration() {
        return duration;
    }

    public void setDuration(double duration) {
        this.duration = duration;
    }

    public Song getNext() {
        return next;
    }

    public void setNext(Song next) {
        this.next = next;
    }
    
    public Song getLastNode() {
        Song currentNode = this;
        while(currentNode.next != null) {
            currentNode = currentNode.next;
        };
        return currentNode;
    }
        
    public void append(Song newSong) {
        Song tmpNode = this.getLastNode();
        tmpNode.next = newSong;
    }
    
    public void printAllSongs() {
        // print all songs from j
        Song currentNode = this;
        do {
            System.out.println("Band: " + currentNode.getBand() + " | " +  
                                " Song: " + currentNode.getName() +  " | " + 
                                " Duration: " + currentNode.getDuration() + " minutes");
            currentNode = currentNode.next;
        } while( currentNode != null );
    
    }
}

public class Main {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Song mySong = new Song("Led Zepplen", "Stairway to Heaven", 8.02);
        mySong.append(new Song ("AC/DC", "Back in Black", 4.14 ));
        mySong.append(new Song("The Rolling Stones", "Paint it Black", 3.46));
        
        mySong.printAllSongs();

    }

}

What is one way I could achieve coding a method that inserts a node at any given position?

Not what you're asking, but this is a common error — a Song should not have a next. When you have a linked-list, each element has a next and should have a value -- in your case the value is a Song object; so it is the list Node object that should have a value and a next (otherwise any sort of object you might ever want to put in a list must have a "next") — Stephen P
– Stephen P, Commented Jul 21, 2020 at 0:15

Andrew Vershinin · Accepted Answer · 2020-07-21 14:44:09Z

1

public void insertAt(int index, Song song) {
    // First, check the inputs
    if (index > size)
        throw new IndexOutOfBoundsException();

    if (song == null)
        throw new NullPointerException();
    
    // Skip (index - 1) songs from the beginning (this), keeping track of previous entry
    Song cur = this, prev = null;
    for (int i = 0; i < index; i++) {
        prev = cur;
        cur = cur.next;
    }

    // Insert in between previous and current entry
    if (prev != null)
        prev.next = song;

    song.next = cur;
    ++size;
}

A good visualisation can be found at VisuAlgo

edited Jul 21, 2020 at 14:44

answered Jul 21, 2020 at 0:02

Andrew Vershinin

1,97813 silver badges16 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Dasax121 Over a year ago

Thank you for the VisuAlgo link, it's awesome and helps me visualize things. Could you however explain your solution please? It hasn't been working for me and I keep getting errors.

Andrew Vershinin Over a year ago

@Dasax121 I forgot to mention that it is convenient to store the number of songs in the list, so you need to add a new field, private int size = 1, to the class, and increment it whenever you add a new element, like in this method and in append.

Andrew Vershinin Over a year ago

@Dasax121 Also, this code won't work whe index = 0, since we treat this as the beginning of the list. There is two solutions: make insertAt return the beginning of the list, and when index == 0, return song, otherwise return this. This is, apparently, not very convenient. The better way would be using a wrapper class for the list, i.e. Album, and keep a sentinel element (an empty Song) as the starting element, so actual elements of the list would go after that, and inserting an element at the beginning would be no different from any other position.

Andrew Vershinin Over a year ago

@Dasax121 Although, the traversal must be modified accordingly, as in going to the next in the first line of the loop, to skip the sentinel.

Collectives™ on Stack Overflow

Insert() node method in java?

1 Answer 1

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related