LinkedList Insert Last

392
December 29, 2016, at 1:43 PM

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();

        }
    }
Answer 1

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.

Answer 2

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.

Answer 3

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);
        }
    }
}
READ ALSO
this in builder cannot be applied

this in builder cannot be applied

I am building a chat app using firebaseI am trying to notify the user when receive a new message

637
Why is a class called an abstraction of an object?

Why is a class called an abstraction of an object?

I understand that a class is essentially a blueprint of an object, but the idea that a class is an 'abstraction' of an object is a little hard for me to wrap my head around

374
HBASE filter by multiple values

HBASE filter by multiple values

I am having problems using filters to search data in hbase

467
A Numbered Variable Spawning Another Numbered Variable

A Numbered Variable Spawning Another Numbered Variable

So you begin with four variables

299