Add a node in a single linked list

Question

Good evening

I'm trying to implement a single linked list by myself and I've run into an issue when I want to create a search method. Evidently when you want to search for a node (which will be used to insert a node at a certain place) you will have to evaluate some values to see if you reached the right spot. Considering my nodes only have a data field as a identifier, I don't see any other way than using that. However, since the data field isn't unique there might be multiple nodes eligible.

Consider the following list: 5, 7, 2, 8, 3, 1, 6, 5, 8, 4, 2. When I want to add a node somewhere in the list (say: After the node with value 8) he will go trough the list and add the new node after the first occurrence of '8'. What should I do if I wanted to insert it after the 2nd 8?

Is this even possible with a Single Linked List?

Other than that I'd like to have some feedback on my 'removeLast()' method which doesn't seem to do what I want it to do (remove the last node from the list). I am aware my code isn't supposed to work if the list has only 1 value, I'll look into that as soon as the general code of removing the last node works.

My code can be found here.

Edited with code:

 public class SingleLinkedList {

 public void deleteLast() {
    if (lastNode != null) {
        Node currentNode = firstNode;

        while (currentNode != null) {
            Node nextNode = currentNode.getNextNode();
            Node nextNextNode = nextNode.getNextNode();

            if (nextNextNode == null) {
                nextNextNode = null;
                lastNode = nextNode;
            }
        }
        listSize--;
    }
}

}

It is possible, but is what is the semantic of your method? Insert a number after all occurrences of some number? — nhahtdh
– nhahtdh, Commented Dec 3, 2012 at 7:45
@nhahtdh: I'd like to add a node at a specified place. The problem is that I don't know how to specify this particular spot, considering the only thing that defines a node is their data, which isn't unique. I was considering using their 'index' in the list, but if I need an index, why would I use a list instead of an array? — Jeroen Vannevel
– Jeroen Vannevel, Commented Dec 3, 2012 at 7:48
If it's evening, you'd be about the same time zone as...Tokyo. — Ben
– Ben, Commented Dec 3, 2012 at 7:52

amit · Accepted Answer · 2012-12-03 08:05:20Z

3

Sure it can be done - you need to keep track of the number of objects you have passed in the way, and after you have passed n objects equals to the seeked one - insert the new data:

public void addAfterNth(Object data,Object o, int n) { 
    Node curr = firstNode;
    while (curr != null) { 
        if (curr.data.equals(o)) n--;
        if (n == 0) { 
            Node newNode = new Node(data,curr.nextNode);
            curr.setNext(newNode);
            break;
        }
        curr = curr.getNextNode();
    }
}

In here you insert a new node with the data denoted in the parameter data after the nth encounter of a node with data equals to o.

Running with:

SingleLinkedList list = new SingleLinkedList();
list.addLast(5);
list.addLast(7);
list.addLast(2);
list.addLast(8);
list.addLast(3);
list.addLast(1);
list.addLast(6);
list.addLast(5);
list.addLast(8);
list.addLast(4);
list.addLast(2);
list.drawList();
list.addAfterNth(999,8, 2);
System.out.println("");
list.drawList();

yields (as expected):

5, 7, 2, 8, 3, 1, 6, 5, 8, 4, 2, 
5, 7, 2, 8, 3, 1, 6, 5, 8, 999, 4, 2,

answered Dec 3, 2012 at 8:05

amit

179k27 gold badges245 silver badges348 bronze badges

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

1 Comment

amit Over a year ago

You are welcome. Note that if number of elements requested is smaller then n (for example if you would insert n==4 in the above example), it will be silently ignored - which is probably not a good thing. You should probably throw an exception or return false in these cases (change the signature to return boolean instead of `void).

Rahul · Accepted Answer · 2012-12-03 08:53:15Z

1

Here is the pseudo code for deleting the last code of a LL. The above answer correctly answers your question of inserting at a specific position.

if (START == NULL){
    Print: Linked-List is empty.
}
else{
    PTR = START, PREV = START
    while (PTR->LINK != NULL)enter code here
        PREV = PTR //Assign PTR to PREV
    PTR = PTR->LINK //Move PTR to next node

    ITEM = PTR->INFO //Assign INFO of last node to ITEM
    If (START->LINK == NULL) Then //If only one node is left
        START = NULL //Assign NULL to START
    Else
        PREV->LINK = NULL //Assign NULL to link field of second last node

    Delete PTR
}

answered Dec 3, 2012 at 8:53

Rahul

16.4k4 gold badges44 silver badges64 bronze badges

1 Comment

Jeroen Vannevel Over a year ago

Thanks for adding this! I got it working on my own with the following code: pastebin.com/QkE3EQpx

Collectives™ on Stack Overflow

Add a node in a single linked list

2 Answers 2

1 Comment

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related