java - Java-自定义单链接列表，删除具有特定值的所有出现的元素

This question was migrated from Software Engineering Stack Exchange because it can be answered on Stack Overflow. Migrated6年前Learn more。
我在java中创建了一个自定义的linkedlist，它在某种程度上是map和list之间的交叉。我做这个练习只是为了学习，我知道hashmap是一个更好更快的实现。我为linkedList实现了delete方法，但对于哪种方法是编写方法的最佳方式有些困惑：delete all基本上删除了某个特定元素的所有出现。
代码：

public class LinkedListMain
{
    public static void main(String[] args)
    {
        LinkedList linkedList = new LinkedList();

        System.out.println("isEmpty: " + linkedList.isEmpty());

        linkedList.insert("abc", 34);
        linkedList.insert("pqr", 44);
        linkedList.insert("xyz", 54);
        linkedList.insert("asd", 64);
        linkedList.insert("abc", 74);

        linkedList.print();

/*      System.out.println("delete: " + linkedList.delete("abc"));
        System.out.println("delete: " + linkedList.delete("pqr"));
        System.out.println("delete: " + linkedList.delete("xyz"));
        System.out.println("delete: " + linkedList.delete("asd"));
*/
        System.out.println("deleteAll: " + linkedList.deleteAll("abc"));
        System.out.println("isEmpty: " + linkedList.isEmpty());
    }
}

class LinkedList
{
    private ListNode first;
    private ListNode last;

    public LinkedList()
    {
        first = null;
        last = first;
    }

    public void insert(String d1, int d2)
    {
        ListNode node = new ListNode(d1, d2);

        if(first == null)
        {
            node.next = null;
            first = node;
            last = node;
        }

        else
        {
            last.next = node;
            node.next = null;
            last = node;
        }
    }

    public String deleteAll(String str)
    {
        return "To Be Implemented";
    }

    public String delete(String str)
    {
        ListNode slow = first;
        ListNode fast = first;

        int count = 0;

        while(fast != null)
        {
            if(count > 1)
            {
                slow = slow.next;
            }

            if(count <= 1)
            {
                count++;
            }

            if(fast.getVal()==str)
            {
                if(fast == first)
                {
                    first = first.next;
                }

                else
                {
                    if(fast.next != null)
                    {
                        slow.next = fast.next;
                    }

                    else
                    {
                        slow.next = null;
                    }
                }

                fast = null;
                return str;     // fast.getVal()
            }

            fast = fast.next;
        }

        return "not found";
    }

    public void print()
    {
        ListNode currentNode = first;

        while(currentNode != null)
        {
            currentNode.print();
            currentNode = currentNode.next;
        }
    }

    public boolean isEmpty()
    {
//      return ( ((first==null) ? (true) : (false)) && ((last==null) ? (true) : (false)));
        return (first==null) ? (true) : (false);
    }
}

class ListNode
{
    private String data1;
    private int data2;

    public ListNode next;

    public ListNode(String d1, int d2)
    {
        data1 = d1;
        data2 = d2;
    }

    public String getVal()
    {
        return data1;
    }

//  public void printMe(ListNode node)
    public void print()
    {
        System.out.println("data1: [" + data1 + "], data2: [" + data2 + "]");
    }
}

我有三个问题与本例相关：
理想的deleteall函数应该重复使用我的delete函数吗？我是否应该更改我的删除功能以适应这种情况？
isEmpty函数是否应该理想地将first和last都比较为空？如果last应该与null进行比较，那么我应该如何更改delete&deleteall函数以实现此功能。我尝试用当前的delete函数执行此操作，但遇到了一些问题。
总的来说，这段代码能得到显著的优化吗不是说“如果你需要完美的链表，就使用集合”，而是简单地问如果可能的话如何更精确地优化这个单链表？

最佳答案

deleteAll()可能最适合将前一个节点传递给节点删除方法。如果delete()除了明显的指针操作之外，还需要执行其他操作，则可以将此操作排除在外。

/**
 Deletes all nodes that contain target_string.
 Returns the number of nodes deleted.
*/
public int deleteAll(String target_string) {
  int deleted_nodes_cnt = 0;
  ...
  if (prev_node.next.getVal().equals(target_string)) { // not ==
    deleteNextNode(prev_node);
    prev_node = prev_node.next;
    deleted_nodes_cnt += 1;
  }
  ...
  return deleted_nodes_cnt;
}

/** Delete the node after prev_node; prev_node.next != null */
private void deleteNextNode(Node prev_node) {
  Node dead_node = prev_node.next;
  prev_node.next = prev_node.next.next;
  dead_node.afterDelete(); // any custom cleanup, if required
}

public boolean delete(String target_string) {
   ...

  if (prev_node.next.getVal().equals(target_string)) { // looks familiar?
    deleteNextNode(prev_node);
    return true;
  }
  ...
  return false;
}

您可能注意到delete()和deleteAll()使用的列表迭代逻辑也可以很好地分解出来。

/**
 Scan nodes, starting from this.
 Returns node X such that X.next.value equals target_string, or null.
*/
private Node findNodeBeforeMatching(String target_string) {
  Node prev_node = this;
  while (prev_node.next != null) {
    if (prev_node.next.getVal().equals(target_string)) return prev_node;
    else prev_node = prev_node.next;
  }
  return null;
}

要有效地使用此方法，您需要将LinkedList（本质上是'list head keeper'）设为Node的子类，或者将它们都设为公共类的子类更好的是，让它们实现相同的接口，允许getNext()和deleteNext()。或者，您可以从每个操作返回Node，但这当然与Collection接口不兼容。
旧的、不正确的文本：deleteAll()不应该调用单个的delete()methids，除非这些方法可能在子类中执行特殊的操作原因是这样的deleteAll()是o（1），在恒定时间内运行，而遍历列表到delete()每个节点是o（n）。AFAICTlast实例变量只用于加快将元素追加到列表末尾的速度（尽管insert()对它做了一些奇怪的事情）所以isEmpty()应该只检查first。如果first == null，则该方法可以assert last == null。我认为拥有first == null但是last != null意味着我们的记账错误，我们的数据已经损坏，我们无法继续。wrt优化，我看不出你的拜占庭式delete()应该如何工作。我认为在你的情况下，有两个指针不会加快速度。以不同的“速度”运行两个指针是一种已知的检测周期的方法，但我不知道它在这里是如何适用的。
如果您希望加快排序数据的速度，请阅读skip list，或使用树。对于未排序的数据，简单的顺序扫描是最好的选择。
对我来说，一个完整的LinkedList类的长度应该是它的一半，因为它在逻辑上非常简单。
您的ListNode和LinkedList不必要地紧密耦合在insert()中，这应该是我如何接受一个实例，而不是构造它。更好的是，ListNode和LinkedList应该是同一件事，就像在经典实现中一样。
拿到Wirth's book on data structures and algorithms，很平易近人。（当你完全理解后，试着继续读克努特的书，如果你真的很勇敢，继续读冈崎的书。）