1

我在 java 中制作了一个自定义的 LinkedList，它有点像地图和列表之间的交叉。我做这个练习只是为了学习，我知道 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. 总的来说，这段代码可以显着优化吗？不是说“如果你需要完美的链表，就使用集合”，只是问如果可能的话，如何更精确地优化这个单链表？
4

1 回答 1

1

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（本质上是“列表主管”）的子类Node，或将它们都设为公共类的子类。更好的是，让它们实现相同的接口，允许getNext()和deleteNext(). 或者，您可以Node从每个操作中返回 a，但这Collection当然与接口不兼容。

旧的、不正确的文本：不应deleteAll()调用单独的方法，除非这些方法可能在后代类中做一些特殊的事情。原因是这样是 O(1)，在恒定时间内运行，而遍历列表到每个节点是 O(n)。AFAICT实例变量仅用于加速将元素附加到列表末尾（尽管对它做了奇怪的事情）。所以应该只有真正检查。如果，方法可能。我认为这意味着我们的簿记是错误的，我们的数据已经损坏，我们无法继续。WRT优化，我看不出你的拜占庭如何delete()deleteAll()delete()lastinsert()isEmpty()firstfirst == null assert last == nullfirst == nulllast != nulldelete()应该管用。我不认为在你的情况下有两个指针可以加快速度。以不同的“速度”运行两个指针是检测周期的一种已知方法，但我看不出它在这里如何适用。

如果您想加快排序数据的速度，请阅读跳过列表，或使用树。对于未排序的数据，简单的顺序扫描是您最好的选择。

对我来说，整个 LinkedList 类的长度应该是原来的一半，因为它在逻辑上非常简单。

您的ListNode和LinkedList不必要地紧密耦合insert()，恕我直言，它应该接受一个实例，而不是构造它。更好的是，ListNode应该和LinkedList经典实现一样。

获取Wirth 关于数据结构和算法的书，它非常平易近人。（当你完全理解后，试着继续看 Knuth 的书，如果你真的很勇敢，可以看 Okasaki 的书。）

于 2013-03-24T02:38:00.110 回答