2

Here is a implementation of LinkedList algorithm. Algorithm inserts node at beginner, after a given node, or at the end of list. 

package LinkedList;

class LinkedList {
    Node Head;

    class Node {
        int data;
        Node Next;

        public Node(int d) {
            data = d;
            Next = null;
        }
    }

    public void insert(int value) {
        if (Head ==null) {
            Head = new Node(value);
            return;
        }
        Node new_node = new Node(value);
        new_node.Next = Head;
        Head = new_node;
    }

    public void display() {
        Node a = Head; 
        while (a != null) {
            System.out.println("value:" + a.data);
            a = a.Next;
        }
    }

    public void insertMiddle(int valueToInsert, Node prev_node) {
        if (Head == null) {
            System.out.println("Cant put value after last node");
        }
        Node new_node = new Node(valueToInsert);
        new_node.Next = prev_node.Next;
        prev_node.Next = new_node;
    }

    public void last(int value){
            Node new_node = new Node(value);
        if(Head == null){
            Head = new Node(value);
            return;
        }
        new_node.Next = null;

        Node last = Head;
        while(last != null){
            last = last.Next ;
        }
        last = new_node;
            return;
    }
}

public class LinkedList_Insertion {
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        LinkedList list = new LinkedList();
        list.insert(8);
        list.insert(20);
        list.insert(0);
        list.insertMiddle(999, list.Head.Next);
        list.display();
        System.out.println("--------------");
        list.last(10000);
        list.display();
    }
}

In the above code, While using method insert: 

public void insert(int value) {
    if(Head ==null){
        Head = new Node(value);
        return;
    }
    Node new_node = new Node(value);
    new_node.Next = Head;
    Head = new_node;
}

why don't we use Head.next = new_node;

Similarly, for method :

public void last(int value){
    Node new_node = new Node(value);
    if(Head == null){
        Head = new Node(value);
        return;
    }
    new_node.Next = null;

    Node last = Head;
    while(last != null){
        last = last.Next ;
    }
    last = new_node;
    return;
}

why don't we use last.next = new_node;?

I often end up doing same mistake again and again. If someone can clear this concept, I will be grateful.
Looking forward to your response!

Improve this question
1
  • Because it's obvious from the code that insert is supposed to insert a new node at the start of the list and that last adds a new node at the end of the list and also last.next can not be a valid operation if you last is really meant to mean last. Commented Jun 23, 2018 at 17:16

2 Answers 2

Reset to default
1

Head case:

You can have Head->node1->node2->node3->...->lastNode

If you do Head.next = newNode, then node1->node2->node3->...->lastNode will be lost.

If you had a doubly-linked list, you could do Head.prev = newNode; Head = Head.prev (prev means previous).

Last case:

This code:

public void last(int value){
    Node new_node = new Node(value);
    if(Head == null){
        Head = new Node(value);
        return;
    }
    new_node.Next = null;

    Node last = Head;
    while(last != null){
        last = last.Next ;
    }
    last = new_node;
    return;
}

looks weird, the condition should actually be while (last.next != null), but even then you are not inserting, you first get a reference to the element that is last in your list, then you make that reference point to another object, it should actually be last.next = newNode, you are right.

Implementing linked lists is a good way to understand how java references work, keep practicing and also try to implement a doubly-linked list.

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

6 Comments

Thanks for your answer. I still didn't get the Head Case. Can you please elaborate more. @POrekhov
Yes, I wrote an example of a linked list like this: Head->node1->node2->node3->...->lastNode. It means that Head.next points to node1, node1.next points to node2, node2.next points to node3, etc. When you just do Head.next = newNode, you overwrite the value of Head.next making it point to something new, discarding node1->node2->node3->...->lastNode. Also, you can't do Head.next = newNode, because you're inserting your new node as the second element into your list, while I'm pretty sure you meant to put it in as the first element.
Also, can we say, since Head is not initialized (i.e. Node Head = new Node(5);) like other nodes, it's just a reference variable of type Node. So when we say Head.next = new_node; , Head.next actually means next of the pointing element which makes the statement wrong. Your previous explanation made things clear. Just additional question. @POrekhov
making diagram and executing statement periodically made sense of how the Node1->Node2->... will be lost if Head.Next used.
@aditya yeah, drawing images is a good way to understand this problem.
|
1

Your Second Code seems to be wrong, You are right it has to be last.next = newNode now answering your 1st question consider 3 nos in linked list 100(head),200,300. here head node with value 100 points to next node with value 200 which must in turn point to the node with value 300. Now let us suppose you want to insert 50 before 100, so when you do 

Head.next = new_node;

The node with value 100 is made to point to next node with value 50, so now we have 100,50 in the linked list with the head as 100 still which is wrong so we do

new_node.Next = Head;
Head = new_node;

In this case linked list becomes 50,100,200,300. Thus we do it this way.

Improve this answer

1 Comment

Wow. You are awesome man. Thanks. Beautiful explanation. @Prithvi

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.