删除链表中所有元素的出现

Question

为了理解数据结构，我开始在java中实现它们。deleteAll的时间复杂度为O(n + n^2)。我该如何改进deleteAll方法？

/* 
* Singly linked list 
*/ 
package linkedlisttest; 

class Node { 

    int data; 
    Node next; 

    public Node(int data) { 
     this.data = data; 
    } 

} 

class LinkedList { 

    Node head; 
    int size; 

    /** 
    * 
    * @param data element to add to list 
    * Time Complexity : O(n) 
    */ 
    public void add(int data) { 
     if (head == null) { 
      head = new Node(data); 
      size += 1; 
      return; 
     } 

     Node current = head; 
     while (current.next != null) { 
      current = current.next; 
     } 
     current.next = new Node(data); 
     size += 1; 
    } 

    /** 
    * 
    * @return size of list 
    * Time Complexity: O(1) 
    * This is because we use a class 
    * variable size to keep track of size of linked list 
    */ 
    public int getSize() { 
     return size; 
    } 
    /** 
    * 
    * @param data element to insert 
    * @param index position at which to insert the element (zero based) 
    * Time Complexity : O(n) 
    */ 
    public void add(int data, int index) { 

     if (index > getSize()) { 
      return; // invalid position 
     } 

     Node current = head; //iterate through whole list 
     int pos = 0; 
     Node newNode = new Node(data); 

     if (index == 0) // special case, since its a single reference change! 
     { 
      newNode.next = head; 
      head = newNode; // this node is now the head 
      size += 1; 
      return; 
     } 
     while (current.next != null) { 
      if (pos == index - 1) { 
       break; 
      } 
      pos++; 
      current = current.next; 
     } 
     // These are 2 reference changes, as compared to adding at index 0 
     newNode.next = current.next; // here we are changing a refernce 
     current.next = newNode; // changing a reference here as well 
     size += 1; 

    } 
    /** 
    * Find the first occurrence of an element 
    * @param data element to find 
    * @return index at which element is found , -1 if not exist 
    * Time Complexity: O(n) 
    */ 
    public int find(int data) { 
     Node current = head; 
     int pos = 0; 
     int index = -1; 
     if(head == null) { //empty list 
      return index; 
     } 
     while(current != null) { 
      if (current.data == data) { 
       index = pos; 
       break; 
      } 
      pos++; 
      current = current.next; 
     } 
     return index; 
    } 

    /** 
    * Delete the first occurrence of data 
    * @param data element to delete 
    * Time complexity : O(n) 
    */ 
    public void delete(int data) { 
     Node current = head; 
     if (head == null) { // list is empty 
      return; 
     } 
     if(head.data == data) { // if we want to delete the head , make next node head 
      head = head.next; 
      size -= 1; 
      return; 
     } 
     while(current.next != null) { 
      if (current.next.data == data) { 
       current.next = current.next.next; 
       size -= 1; 
       return; 
      } 
      current = current.next; 
     } 
    } 

    /** 
    * Delete all occurrences of data 
    * @param data element to delete 
    * 
    */ 
    public void deleteAll(int data) { 
     Node current = head; 
     if (head == null) { // list is empty 
      return; 
     } 
     //while loop to delete consecutive occurances of data 
     while(head.data == data) { // if we want to delete the head , make next node head 
      head = head.next; 
      size -= 1; 
     } 
     while(current.next != null) { 
      //while loop to delete consecutive occurances of data 
      while (current.next.data == data) { 
       current.next = current.next.next; 
       size -= 1; 
      } 
      current = current.next; 
     } 
    } 

    public void reverse() { 

    } 



    /** 
    * Prints the whole linked list 
    * Time Complexity : O(n) 
    */ 
    public void print() { 

     if(head == null) { //list is empty 
      return; 
     } 
     Node current = head; 
     while (current.next != null) { 
      System.out.print(current.data + "->"); 
      current = current.next; 
     } 
     System.out.print(current.data + "\n"); 
    } 
} 

public class LinkedListTest { 

    /** 
    * @param args the command line arguments 
    */ 
    public static void main(String[] args) { 
     LinkedList lt = new LinkedList(); 
     lt.print(); 
     lt.add(3); 
     lt.add(5); 
     lt.add(6); 
     lt.print(); 
     lt.add(4, 1); 
     lt.print(); 
     lt.add(4, 7);// 7 is an invalid index 
     lt.add(8, 3); 
     lt.add(8, 4); 
     lt.print(); 
     System.out.println("Position : " + lt.find(8)); 
     lt.delete(5); 
     lt.print(); 
     lt.deleteAll(8); 
     lt.print(); 
     System.out.println("Size : " + lt.getSize()); 
    } 

} 

Answer 1

如您所料，您实施的时间复杂度为O(n)，而不是O(n + n^2)。 尽管嵌套循环是O(n^2)的常见标志，但并非总是如此。 重要的一点是迭代次数。 在你的情况下，如果你在嵌套循环中采用k步骤，则 ， 将外循环中的其余步骤减少k。 总的来说， 你仍然会采取n的步骤来达到目的。

但您的实现有一些错误， 也可以改进：

• 错误：您指定current = head，但如果head.data == data那么它将被删除，并且current仍将指向它
• 有不需要嵌套循环。头部用经过特殊处理，你可以简单地按照节点和删除相匹配的项目

像这样：

public void deleteAll(int data) { 
    while (head != null && head.data == data) { 
     head = head.next; 
     size -= 1; 
    } 

    if (head == null) { 
     return; 
    } 

    Node current = head; 
    while (current.next != null) { 
     if (current.next.data == data) { 
      current.next = current.next.next; 
      size -= 1; 
     } else { 
      current = current.next; 
     } 
    } 
} 

顺便说，头部的特殊处理可有点讨厌。 优雅的另一种方法是创建一个指向head虚设：

public void deleteAll(int data) { 
    Node dummy = new Node(); 
    dummy.next = head; 

    Node current = dummy; 
    while (current.next != null) { 
     if (current.next.data == data) { 
      current.next = current.next.next; 
      size -= 1; 
     } else { 
      current = current.next; 
     } 
    } 

    head = dummy.next; 
} 

Answer 2

请注意，Java中的所有内容都是引用，除了那些基本类型。所以current仍然停留在原来的head。

作为特殊情况不需要将连续事件对待。一个简单的迭代&通过与O(n)链接列表来判断 - 线性复杂度将完全符合你的要求。

此外，嵌套循环并不一定意味着它肯定会花费O（n^2）。如果每次移动current，它仍然以线性时间遍历链表。

另一种个人建议：如果您在处理链接列表时需要编写类似node.next.next的东西，那么应该设置另一个引用或重构代码。