java - 基于位置的序列 ADT 如何在 O(1) 时间内插入元素？

Question

我正在阅读有关基于位置的序列的内容。 (迈克尔·T·古德里奇)第 4 章(序列)。
我的理解是位置序列继续按线性顺序添加节点。 (基于双向链表)此外，每个节点可能指向其他一些节点。
例如，采用由位置序列实现的具有四个节点 a、b、c、d 的简单树。P(具有节点 p1、p2、p3、p4)

现在，如果我想添加新的树节点“e”作为“b”的右子节点。为此，我将在 p5 中添加该节点，然后我将引用 e。 书上说它在 O(1) 时间内添加一个节点。 我的观点是，要将 e 添加为 b 的右子节点，我们不需要从“a”的位置(链接跳跃)获得的 b 的位置。怎么不是O(n)。

我在 Stackoverflow 本身找到的解决方案之一是以下代码......

 public interface Position{
     Object element();
 }

创建一个实现 Position 接口(interface)的 Node 类:

 public class Node implements Position {

     private Object data;
     private Node next;
     private Node prev;

     public Node(Node prev, Object data, Node next){

         this.prev = prev;
         this.data = data;
         this.next = next;
     }

     public Object element()     // Method of interface Position
     {
         return data;
     }

     public void setData(Object data)
     {
         this.data = data;
     }

     public void setNext(Node next)
     {
         this.next = next;
     }

     public void setPrev(Node prev)
     {
         this.prev = prev;
     }

     public Node getNext()
     {
         return next;
     }

     public Node getPrev()
     {
         return prev;
     }

}

创建一个实现 List ADT 的 List 类:

   // this is a List ADT implemented using a Doubly Linked List

public class List{

      private Node first;
      private Node last;
      private int size;

      List()
      {
         first = null;
         last = null;
         size = 0;
      }

      public int getSize()
      {
         return size;
      }

      public boolean isEmpty()
      {
         return (size==0);
      }


     // Accessor methods

     public Position first()
     {
        return first;
     }

     public Position last()
     {
        return last;
     }

     public Position before(Position p) throws Exception
     {
        Node n = (Node) p;
        try{
             return n.getPrev();
        }catch(NullPointerException ex)
        {
             throw new Exception("Position Doesn't Exists");
        }
     }

     public Position after(Position p) throws Exception
     {
          Node n = (Node) p;
          try{
        return n.getNext();
    }catch(NullPointerException ex)
    {
        throw new Exception("Position Doesn't Exists");
    }
}

 // Update methods

public void insertFirst(Object data)
{
    Node node;
    if(isEmpty())
    {
        Node prev = null;
        Node next = null;
        node  = new Node(prev,data,next);
        first = node;
        last = node;
    }
    else
    {
        Node prev = null;
        Node next = first;
        node  = new Node(prev,data,next);
        first.setPrev(node);
        first = node;
    }
    size++;
}

public void insertLast(Object data)
{
    Node node;
    if(isEmpty())
    {
        Node prev = null;
        Node next = null;
        node  = new Node(prev,data,next);
        first = node;
        last = node;
    }
    else
    {
        Node prev = last;
        Node next = null;
        node  = new Node(prev,data,next);
        last.setNext(node);
        last = node;
    }
    size++;
}

public void insertBefore(Position p, Object data) throws Exception
{
    Node cur = (Node) p;
    Node prev;
    try{
        prev = cur.getPrev();
    }catch(NullPointerException ex)
    {
        throw new Exception("Position Doesn't Exists");
    }
    Node next = cur;
    Node node;
    node  = new Node(prev,data,next);
    next.setPrev(node);
    if(cur!=first)
        prev.setNext(node);
    else
        first=node;
    size++;
}

public void insertAfter(Position p, Object data) throws Exception
{
    Node cur = (Node) p;
    Node prev = cur;
    Node next;
    try{
        next = cur.getNext();
    }catch(NullPointerException ex)
    {
        throw new Exception("Position Doesn't Exists");
    }
    Node node;
    node  = new Node(prev,data,next);
    prev.setNext(node);
    if(cur!=last)
        next.setPrev(node);
    else
        last=node;
    size++;
}

public Object remove(Position p) throws Exception
{
    Node n = (Node) p;

    Object data = n.element();
    if(isEmpty())
    {
        throw new Exception("List is Empty");
    }
    else
    {
        Node prev,next;
        if(n==first && n==last)
        {
            first = null;
            last = null;
        }
        else if(n==first)
        {
            prev = null;
            next = n.getNext();
            next.setPrev(prev);
            first = next;
        }
        else if(n==last)
        {
            prev = n.getPrev();
            next = null;
            prev.setNext(next);
            last = prev;
        }
        else
        {
            prev = n.getPrev();
            next = n.getNext();
            prev.setNext(next);
            next.setPrev(prev);             
        }   
        size--;
    }
    return data;
}

 }

和平

Answer 1

我对这种情况的理解如下。为了将新项目添加到列表中，我们必须执行以下任务:

第一个:找到目标项目，然后我们要添加新项目。

第二个:添加项目并更改链接。

正如您正确指出的那样，在链接列表的情况下，第一个操作取决于列表中项目的数量，并且将花费(最大)O(n)。但是，例如在数组列表的情况下，它可能需要 O(1)。

我猜，书上说的是第二个任务，当目标项目已经找到时。如果您使用链表，此操作确实需要恒定的操作量 - O(1)。对数组列表进行相同的操作可能需要 O(n)。

关于您的评论。比较一下:

基于位置

• get(i) 的复杂度为 O(n)
• add(item) 的时间复杂度为 O(1) 优势
• addToPosition(i, item) 的复杂度为 O(n)
• 删除(项目) 的时间复杂度为 O(1) 优点
• delete(i) 从 O(1) 到 O(n)

基于排名

• get(i) 的时间复杂度为 O(1) 优点
• add(item) 从 O(1) 到 O(n)
• addToPosition(i, item) 从 O(1) 到 O(n)
• 删除(项目) 从 O(1) 到 O(2n)
• delete(i) 从 O(1) 到 O(n)

所以，您应该了解这两种类型的优点，以便根据情况使用。例如，如果您需要大量的添加和删除操作 - 您应该使用LinkedList，但是当您只需要通过索引访问项目时， 添加和删除操作很少 - 选择ArrayList。