LinkedList Insert Last

Question

I am trying to insert element at the end of a linked list insertAtEnd(). When I debug the code I see a node(0,null) is being inserted as default in the beginning of the insertion. I think this is causing the problem while iterating through the list. Any suggestions on how fix this?

package com.ds.azim;

public class Node {
    //Node has 1. Data Element 2. Next pointer
    public int data;
    public Node next;
    //empty constructor 
    public Node(){
        //
    }
    public Node(int data){
        this.data= data;
        this.next = null;
    }
    public Node(int data, Node next){
        this.data = data;
        this.next = next;
    }
}

//*************************************//    

package com.ds.azim;

    public class SingleLinkedList {
        //Single Linked list has a head tail and has a length
        public Node head;
        public Node tail;
        public int length;
        //constructor
        public SingleLinkedList(){
            head = new Node();
            length = 0;
        }
        public void insertAtFirst(int data){
            head = new Node(data,head);
        }
        public void insertAtEnd(int data){
            Node curr = head;
            if(curr==null){
                insertAtFirst(data);
            }else{
                while(curr.next!=null){
                    curr = curr.next;
                }
                curr.next = new Node(data,null);
            }
        }
        public void show(){
            Node curr = head;
            while(curr.next!=null){
                //do something
                System.out.print(curr.data+",");
                curr = curr.next;
            }
        }
        public static void main(String[] args){
            SingleLinkedList sll = new SingleLinkedList();
            sll.insertAtFirst(12);
            sll.insertAtFirst(123);
            sll.insertAtFirst(890);
            sll.insertAtEnd(234);
            sll.show();


        }
    }

You have a `tail` variable which, presumably, should be pointing at the last node in the list (though currently your code doesn't use it). Inserting at the end should be just a matter of `tail.next = new Node(data)`. — sprinter, Dec 29 '16 at 01:14
That requires that `tail` be updated when the structure changes, and that "empty" is handled correctly. — Lew Bloch, Dec 29 '16 at 01:23
@sprinter thanks for the response. i declared the tail but never made use of it. How could i make this work using head pointer ? — Azim Shaik, Dec 29 '16 at 01:24
@sprinter or did you mean `tail.next = (tail = new Node(data));`? — Bohemian, Dec 29 '16 at 01:44

score 0 · Answer 1 · answered Dec 29 '16 at 01:21

0

Your code initializes the list with a Node containing (0, null) and head pointing to it. To fix this, don't do that.

public SingleLinkedList() {
  head = new Node();
  length = 0;
}

Also in that code you set length = 0;, but actually the length is 1. Remove both the assignments from the constructor. Then you will have a structure with zero members and the length will be correct.

answered Dec 29 '16 at 01:21

Lew Bloch

3,364
1
16
10

Do I exclusively need to have variable length ? – Azim Shaik Dec 29 '16 at 01:56

sprinter · Answer 2 · 2016-12-29T03:28:38.217

You have a tail variable which should point to the last node in your list. You should be keeping it up to date:

class SingleLinkedList {
    private Node head = null;
    private Node tail = null;

    public void addAtHead(int data) {
        if (head == null) {
            addFirst(data);
        } else {
            head.next = new Node(data, head.next);
            if (tail == head)
                tail = head.next;
        }
    }

    public void addAtTail(int data) {
        if (head == null) {
            addFirst(data);
        } else {
            assert tail != null;
            assert tail.next == null;
            tail.next = new Node(data);
            tail = tail.next;
        }
    }

    private void addFirst(int data) {
        assert head == null;
        assert tail == null;
        head = new Node(data);
        tail = head;
    }
}

If you want to remove the tail variable, then:

class SingleLinkedList {
    private Node head = null;

    public void addAtHead(int data) {
        if (head == null) {
            head = new Node(data);
        } else {
            head.next = new Node(data, head.next);
        }
    }

    public void addAtTail(int data) {
        if (head == null) {
            head = new Node(data);
        } else {
            Node curr = head; 
            while (curr.next != null) 
                curr = curr.next;
            curr.next = new Node(data);
        }
    }
}

You don't need to use assert. It's just a very good idea for avoiding unexpected errors in this type of code. See http://stackoverflow.com/questions/2758224/what-does-the-java-assert-keyword-do-and-when-should-it-be-used — sprinter, Dec 29 '16 at 02:44

score 0 · Accepted Answer · answered Dec 29 '16 at 03:06

Along with removing this part of the code

public SingleLinkedList() {
  head = new Node();
  length = 0;
}

change your show function as well, because this will not print the last element

while(curr.next!=null){
                //do something
                System.out.print(curr.data+",");
                curr = curr.next;
            }

after this while, put one more print statement to print the last element.

System.out.print(curr.data);

this will fix the errors.

LinkedList Insert Last

3 Answers3