Как я могу удалить последний узел связанного списка в java? - PullRequest
Новая
       15

Как я могу удалить последний узел связанного списка в java?

0 голосов
/ 13 марта 2020

Мне нужно реализовать два метода removeFirst и removeLast из LinkedList в Java

Первый метод, который я решил это следующим образом: 

@Override
public E removeFirst() {
    if(isEmpty()){
        throw new NoSuchElementException();
    }
    E element = top.next.data;
    top.next = top.next.next;
    numElements--;
    return element;
}

У меня проблемы с removeLast method 

     public E removeLast() {
     if(isEmpty()){
         throw new NoSuchElementException();
     }

      for (int i = 0; i < numElements;i++) {


      }

}

Моя идея - использовать цикл for для поиска последнего элемента, но я не знаю, что делать после этого

Есть предложения?

Мой класс Node следующий: 

public class Node<E> {

E data;
Node<E> next; 

public Node(E data) {
    this(data,null);
}

public Node(E data, Node<E> next) {
    this.data = data;
    this.next = null;
}

@Override
public String toString () {
    return data.toString();


}

}

Ответы [ 4 ]

0 голосов
/ 13 марта 2020

Мы должны оставить два указателя на предыдущий и текущий. Поскольку мы храним запись о количестве элементов в списке, мы можем использовать l oop для обхода списка и нахождения последнего узла, на который указывает указатель currentNode, и предыдущего узла, на который указывает указатель previousNode. Наконец, обновите предыдущий следующий указатель на null и верните данные currentNode. 

 public E removeLast() {
    if(isEmpty()){
        throw new NoSuchElementException();
    }
    Node previousNode = top;
    Node currentNode = top;
    for (int i = 0; i < numElements -1 ;i++) {
        previousNode = currentNode;
        currentNode = currentNode.next;
    }
    // removed the last element and return the data
    previousNode.next = null;
    numElements-- 
    return currentNode.data;

}

0 голосов
/ 13 марта 2020

removeFirst и removeLast уже существуют в классе LinkedList ( LinkedList javado c). Не нужно создавать их с нуля.

0 голосов
/ 13 марта 2020

Что-то вроде этого может работать, трудно сказать, не видя вашего списка, потому что я не могу его проверить: 

  public E removeLast() {
    if(isEmpty()){
        throw new NoSuchElementException();
    }
    Node<E> node = top;
    while (true) {
      Node<E> nextNode = node.next;
      if (nextNode.next == null) {
        node.next = null;
        return nextNode.data;
      } else {
        node = nextNode;
      }
    }
  }

Но стоит добавить, что обычно в односвязном списке вы хотите содержащий класс для хранения хвостового указателя (иначе вы не сможете эффективно добавить к концу). Если вы сделаете это, вам также потребуется обновить свой хвост.

И еще один комментарий: если вы действительно удаляете последнее регулярно, вы хотите переключиться на двусвязный список ... и почему вы просто не используете встроенный класс java .util.LinkedList? Это для школьного проекта или что-то?

0 голосов
/ 13 марта 2020

Этот лог c должен работать - 

Node <E> tmp;
tmp = next;


while(tmp.next.next != null)
tmp = tmp.next;
tmp.setNext(null);

Так что, если мы имеем 1-> 3-> 4-> нуль

Всякий раз, когда он добирается до 3, он должен установить Next на ноль поэтому новый массив будет выглядеть следующим образом 1-> 3-> null

...