Java-реализация структуры данных связанного списка

Question

Я пытаюсь реализовать структуру данных связанного списка, используя java, она отлично работает для вставки или удаления первых элементов, но не может удалить последний элемент с помощью метода removeLast ().

Класс узла My Linked List: открытый класс LLNode { Строковое значение; LLNode следующий;

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

}

Класс My Linked List, который содержит головной узел:

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


    }

}

Вывод такой:

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

даже если бы это было так:

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

Что не так с моей реализацией?

Answer 1

Если вам нужно много кода и / или много переменных для такой задачи, как вы, вы, вероятно, слишком усложнили себя в углу. Вот как бы я это сделал 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;
    }
  }
}

Не проверено! Используйте на свой страх и риск. Нет возмещения стоимости покупки.

Answer 2

while(current.next.next != null) наступает, пока не станет правдой. В какой момент вы установите current.next.next = null;. Который это уже есть.

Answer 3

current.next.next = null;

должно быть

current.next = null;

---

и реализация терпит неудачу с NPE при попытке удалить первый элемент пустого Списка

Answer 4

На сегодняшний день ответ Карла Смотрича является наиболее логичным, и, конечно, другие хорошо его объяснили. Вот мое решение:

1. начать с текущего узла и указать его на голову
2. в то время как два узла заголовок нашего текущего узла не равен нулю, тогда установите наш текущий узел на следующий узел
3. в конце установите для узла Next значение currtentnode, равное нулю, другими словами, установите для последнего узла значение null / (удалите его)

Код

 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;

Вот изображение

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

Answer 5

Попробуйте это:

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