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

Question

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

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

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

} 

Мой Linked класс список, который держит голову Узел:

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

current.next.next = null;

должно быть

current.next = null;

---

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

Answer 3

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

Answer 4

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

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

Answer 5

До сих пор Карл Smotricz ответ является наиболее логичным один и, конечно, другие проделали хорошую работу, объясняя это. Вот мое решение:

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

код

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