Java: Хороший алгоритм для удаления элемента из связанного списка?

Question

У меня есть довольно простой вопрос. Я выполняю несколько операций в связанном списке в качестве упражнения. Одна такая операция удаления:

/** 
* Removes the element at index. 
* @param index 
* @throws IndexOutOfBoundsException If index is greater than the list's length. 
*/ 
public void remove(int index) throws IndexOutOfBoundsException; 

Класс только переменная экземпляра:

private Node<T> first; 

Node Класс:

public class Node<T> { 

    public T datum; 
    public Node<T> next; 

    public Node(T datum) { 
     this.datum = datum; 
    } 

    @Override 
    public int hashCode() { 
     final int prime = 31; 
     int result = 1; 
     result = prime * result + ((datum == null) ? 0 : datum.hashCode()); 
     result = prime * result + ((next == null) ? 0 : next.hashCode()); 
     return result; 
    } 

    @Override 
    public boolean equals(Object obj) { 
     if (this == obj) 
      return true; 
     if (obj == null) 
      return false; 
     if (getClass() != obj.getClass()) 
      return false; 
     Node<T> other = (Node<T>) obj; 
     if (datum == null) { 
      if (other.datum != null) 
       return false; 
     } else if (!datum.equals(other.datum)) 
      return false; 
     if (next == null) { 
      if (other.next != null) 
       return false; 
     } else if (!next.equals(other.next)) 
      return false; 
     return true; 
    } 
} 

Вот моя реализация remove():

@Override 
public void remove(final int index) throws IndexOutOfBoundsException { 

    if (null == first) { 
     throw new IndexOutOfBoundsException(); 
    } 

    Node<T> current = first; 
    int nodesExamined = 0; 

    if (0 == index) { 
     first = first.next; 
     return; 
    } 

    while (null != current) { 
     if (nodesExamined + 1 == index) { 
      current.next = null == current.next ? null : current.next.next; 
      return; 
     } 
     nodesExamined++; 
     current = current.next; 
    } 

    throw new IndexOutOfBoundsException(); 
} 

Он проходит несколько тестов, но, вероятно, осталось несколько ошибок. Хотя общий подход правильный? Мне кажется, что я слишком усложняюсь.

Answer 1

Я бы не сказал, что вы ошибаетесь, поскольку основная функциональность есть. Тем не менее, я рекомендую использовать итератор и так обходиться.

Посмотрите на этот код here, который реализует связанный список, используя итератор для всех функций поиска/удаления. Вы также можете расширить его оттуда, используя некоторый отказоустойчивый код, чтобы сделать его чище.

Answer 2

(редактирование:. Уточнить, ничего плохого с итерационным подходом, просто мысли вслух)

Поскольку это односвязный список, вы должны быть в состоянии выразить операцию удаления довольно сжато с использованием рекурсивной функции взяв узел и индекс и вернув узел. В общих чертах, вы бы:

1. проверить, что переданный узел не null (бросание исключения в противном случае)
2. затем ветвь на значении index: если 0, вернуть узел в next ; в противном случае снова вызовите рекурсивную функцию с узлом next и index, уменьшенным на 1, и присвойте результат next.

Просто догадка, может еще есть ошибка fencepost там ..

Answer 3

Почему бы не использовать цикл для управления выходом?

@Override 
public void remove(final int index) throws IndexOutOfBoundsException { 

    if (first == null) { 
     throw new IndexOutOfBoundsException(); 
    } 

    int nodesExamined = 0; 

    for(Node<T> current = first; current != null; current = current.next){ 
     if(nodesExamined == index){ 
      current.next = current.next == null ? null : current.next.next; 
      return; 
     } 
     nodesExamined++; 
    } 

    throw new IndexOutOfBoundsException(); 
} 

Предполагается, что у вас нет какой-либо функции linkedList.size(), доступной вам. Если вы это сделали, вы можете поместить чек в начале, чтобы убедиться, что ваш индекс < ваш размер.

Answer 4

Как насчет упрощения этой функции? Вы сказали:

public boolean equals(Object obj) { 
    if (this == obj) 
     return true; 
    if (obj == null) 
     return false; 
    if (getClass() != obj.getClass()) 
     return false; 
    Node<T> other = (Node<T>) obj; 
    if (datum == null) { 
     if (other.datum != null) 
      return false; 
    } else if (!datum.equals(other.datum)) 
     return false; 
    if (next == null) { 
     if (other.next != null) 
      return false; 
    } else if (!next.equals(other.next)) 
     return false; 
    return true; 

, когда вы могли бы сказать:

public boolean equals(Object obj) { 
    Node<T> other = (Node<T>) obj; 
    return (other != null) && 
     (getClass() == other.getClass()) && 
     ((datum == other.datum) || datum.equals(other.datum)) && 
     ((next == other.next) || next.equals(other.next)); 
    } 

Обратите внимание, что x == y || x.equals(y) обрабатывает пустой корпус, а также короткое замыкания Quicky для рефов на тот же объект.