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

Question

我在 java 中创建了一个自定义的 LinkedList，它有点介于 map 和列表之间。我做这个练习只是为了学习，我知道 HashMap 是一个更好更快的实现。我为 LinkedList 实现了 delete 方法，但对于哪种编写方法的最佳方式有点困惑:deleteAll 基本上删除了特定元素的所有出现。

代码:

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 + "]");
    }
}

我有 3 个与此示例相关的问题:

1. 理想的 deleteAll 函数是否应该重复使用我的 delete 函数？我是否应该更改我的删除功能以适应这种情况？
2. 理想情况下，isEmpty 函数是否应该将 first 和 last 都与 null 进行比较？如果 last 应该与 null 进行比较，那么我应该如何更改我的 delete 和 deleteAll 函数才能实现它。我尝试使用当前的删除功能执行此操作，但遇到了一些问题。
3. 总的来说，这段代码能否得到显着优化？不是那种“如果你需要完美的链表，就使用 Collections”的意思，只是问如果可能的话如何更准确地优化这个单链表？

Answer 1

deleteAll() 可能最适合将previous 节点传递给节点删除方法。如果 delete() 预期除了明显的指针操作之外做任何事情，那么这个 Action 可以被分解掉。

/** 
 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(本质上是“列表负责人”)设为 Node 的子类，或者将它们设为共同的子类类(class)。更好的是，让它们实现允许 getNext() 和 deleteNext() 的相同接口(interface)。或者，您可以从每个操作返回一个 Node，但这当然与 Collection 接口(interface)不兼容。

_{旧的、不正确的文本:deleteAll() 应该不调用单独的 delete() 方法，除非这些方法可以做一些事情特殊在后代类。原因是这样的deleteAll()复杂度为O(1)，运行时间恒定，而遍历链表到delete()每个节点的复杂度为O(n)。 AFAICT last 实例变量仅用于加快将元素附加到列表末尾的速度(尽管 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 ，非常平易近人。 (当你完全理解它时，试着继续读 Knuth 的书，如果你真的很勇敢，就读 Okasaki 的书。)