Reputation: 64793

java implementation of Linked List Data Structure

I am trying to implement the linked list data structure using java, it works fine for insertion or removing first elements but fails to remove the last element via using the removeLast() method.

My Linked List Node class: public class LLNode { String value; LLNode next;

    public LLNode(String value){
        this.value = value;
        this.next = null;
    }

}

My Linked List class that holds a head Node:

public class LL {
    LLNode head;

    public LL(){
        this.head = null;   
    }

    public void insertHead(LLNode input){
        input.next = head;
        this.head = input;
    }

    public void removeFirst(){
        this.head = this.head.next;
    }

    public void removeLast(){
        if (this.head == null || this.head.next == null){
            this.head = null;
            return;
        }
        LLNode current = this.head;
        LLNode tmphead = current;
        while(current.next.next != null){
            current = current.next;
        }
        current.next.next = null;
        this.head = tmphead ;
    }

    public void printAll(){
        LLNode current = this.head;

        while(current != null){
            System.out.print(current.value+" ");
            current = current.next;
        }
        System.out.println();
    }


    public static void main( String[] args){

        LL test = new LL(); 
        LL test2 = new LL();
        String[] eben = {"one","two","three","four","five","six"};

        for(int i =0;i<eben.length;i++){
            test.insertHead(new LLNode(eben[i]));
        }
        test.printAll();
        test.removeFirst();
        test.printAll();
        test.removeLast();
        test.printAll();


    }

}

The output is such:

six five four three two one 
five four three two one 
five four three two one

even tho it had to be like this:

six five four three two one 
five four three two one 
five four three two

What is wrong with my implementation ?

Upvotes: 0

Answers (5)

grepit

Reputation: 22382

By far Carl Smotricz answer is the most logical one and of course others have done a good job explaining it. Here is my solution:

start with current node and point it to head
while the the two nodes a head of our current node is not null then set our current node to next node
at the end set the Next node to the currtentnode to null in other words, set the last node to null/ (remove it)

The code

 Node currentNode = head; // start with current node and point it to head
    while (currentNode.next.next != null) // while the current next next  node is not null then set our  current node to next node
    {
        currentNode = currentNode.next;
    }
    // at the end set the Next node to the currtentnode to null
    // in other words, set the last node to null/ (remove it)
    currentNode.next = null;

Here is the visual

currentNode     currentNode.next    currentNode.next.next
(head)                              (last Node)                     
    +-+-+         +-+-+                  +-+-+           
    | | +-------> | | +--------------->  | | |           
    +-+-+         +-+-+                  +-+-+

Upvotes: 0

user3668469

Reputation: 1

Try this:

public class Node {

private int data; //holds an arbitrary integer
private Node next; //reference to the next node

public Node(int d,Node n)
{
    data=d;
    next=n;
}

// these methods let us use our variables
public void setNext(Node n)
{
    next=n;
}

public void setData(int d)
{
    data=d;
}
public Node getNext()
{
    return next;
}

public int getData()
{
    return data;
}
private static Node firstNode; //a reference to the first Node
private static Node lastNode=null; //a reference to the last Node

public static void display() //displays all the data in nodes
{
    Node n=firstNode;
    while(n!=null) // loops forward displaying 
    {
        System.out.print(n.getData()+",  ");
        n=n.getNext(); //move to the next node in the list
    }
}

public static void create(int d) //inserts the node into the list
{
    Node n =new Node(d, null); // create node
    if(lastNode!=null) // if it is not the first node
    {
        lastNode.setNext(n);
        lastNode=n;
    }
    else //if n is the first node
    {
        firstNode=n;
        lastNode=n;
    }
}


 public static void removeLast(){
        if (firstNode == null || firstNode.next == null){
            firstNode = null;
            return;
        }
        Node current = firstNode;
        Node tmphead = current;
        while(current.next.next != null){
            current = current.next;
        }
        current.next = null;
        firstNode = tmphead ;
    }


 public static void removeFirst(){
     if(firstNode!=null)
     {
        firstNode= firstNode.next;
     }
    }

public static void main(String[] args) {

    create(10);
    create(20);
    create(30);
    create(40);
    create(50);
    create(60);
    display();
    System.out.println();
    removeLast();
    display();
    System.out.println();
    removeFirst();
    display();
}
}

Upvotes: -1

Carl Smotricz

Reputation: 67760

If you need a lot of code and/or a lot of variables for a task like this, you've probably overcomplicated yourself into a corner. Here's how I would do removeLast():

public void removeLast() {
  // avoid special case: List is empty
  if (this.head != null) {
    if (this.head.next == null) {
      // handle special case: List has only 1 node
      this.head = null;
    } else {
      LLNode prelast = this.head; // points at node before last (eventually)
      while (prelast.next.next != null) prelast = prelast.next;
      prelast.next = null;
    }
  }
}

Untested! Use at your own risk. No refunds of purchase price.

Upvotes: 2