java implementation of Linked List Data Structure

Question

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 ?

This is either J2ME or homework, since there's no other earthly reason why you would want to do this. — skaffman
– skaffman, Commented Jan 9, 2010 at 18:38
egad, if I recall from my data structures class in 1980 this example is cleaned up about 99% by using a sentinel. — President James K. Polk
– President James K. Polk, Commented Jan 9, 2010 at 18:41

Carl Smotricz · Accepted Answer · 2010-01-09 18:45:29Z

2

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.

answered Jan 9, 2010 at 18:45

Carl Smotricz

68k18 gold badges129 silver badges170 bronze badges

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

Comments

Jens Schauder · Accepted Answer · 2010-01-09 18:43:20Z

1

current.next.next = null;

should be

current.next = null;

and the implementation fails with a NPE when trying to remove the first element of an empty List

edited Jan 9, 2010 at 18:43

Jens Schauder

82.6k35 gold badges199 silver badges379 bronze badges

answered Jan 9, 2010 at 18:38

DaveC

2,06017 silver badges14 bronze badges

Comments

Mark Bolusmjak · Accepted Answer · 2010-01-09 18:45:16Z

1

while(current.next.next != null) advances until it's true. At which point you set current.next.next = null;. Which it already is.

answered Jan 9, 2010 at 18:45

Mark Bolusmjak

24.6k10 gold badges77 silver badges133 bronze badges

Comments

grepit · Accepted Answer · 2015-01-01 21:37:54Z

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)                     
    +-+-+         +-+-+                  +-+-+           
    | | +-------> | | +--------------->  | | |           
    +-+-+         +-+-+                  +-+-+

Alok · Accepted Answer · 2014-05-23 10:32:36Z

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

You've basically pasted some code without any real explanation of what you've changed and why. Answers that are effectively just "here's some code, go try it" aren't really high quality. If you could provide an explanation of this code, it would go some way to improving the answer's quality.

Collectives™ on Stack Overflow

java implementation of Linked List Data Structure

5 Answers 5

Comments

Comments

Comments

Comments

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

5 Answers 5

Comments

Comments

Comments

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related