6

私は、株式市場プログラムに関してリンク リストを実装しています。

動作あり・購入

購入のコードは

//Stocks is a linked List like so 
//LinkedList<Integer> stocks = new LinkedList<Integer>();
public void buy(int q, int p) {
    stocks.addLast(q); //add number of stocks
    stocks.addLast(p); //for i stocks i +1 = price of stock
}

この操作 addLast はリンクされたリスト用であり、現在のリストの末尾にある新しい位置に指定された要素を追加します。

たとえば、次のデータを含むリストがある場合

//Stock, price, stock, price etc...
[100, 50, 5000, 30, 8000, 60]

IaddLastがリンク リストで最後の要素を検索してから追加する場合、時間の複雑さは O(n) になります (Big Oh に関してのみ)。それとも、リストの最後にインデックスを付けて、リストの最後が言うことに気づき、リストの最後にstocks[5]新しいデータを参照する新しいノードを挿入していますか?

だから私の質問は、addLast()O(n) または O(1) のリンクされたリストの時間の複雑さの操作ですか?

説明のために以下に投稿してください

4

3 に答える 3

5

LinkedList クラスの javadoc を読むと、次のように記載されています。指定されたインデックスに。」

これは、O(1) であることを意味します。

編集

株式名、価格表のより良い実装が必要な場合は、株式の説明を含むクラスを作成することをお勧めします。

public class Stock {
    private int stockName;
    private int stockPrice;

    // other methods, properties, constructor
}

そして、LinkedList<Stock>

于 2013-09-08T00:42:36.587 に答える
2

add()orの複雑さaddLast()はO(1)、リストの長さにあります。これはLinkedList ソースコードを読めば明らかです。

(動作のこの側面は javadoc 1で正確に指定されていないため、理論的には変更される可能性があります。ただし、この可能性を自信を持って除外できます。たとえそれが理にかなっていたとしても (そうではありません!)、そのような変更は、非常に多くの既存のアプリケーションを破壊します.それだけで、それを信じがたいものとして除外する十分な理由になります.)

1 - javadoc の文「[o]operations that index into the list will tr​​averse the list from the first or the end, which are Nearly the specified index.」は、このメソッドには明確に適用されないと主張します。add/メソッドはリストにインデックスaddLastを付けないと主張することができます。

于 2013-09-08T00:42:24.533 に答える
1

LinkedList クラスのソースを見ると、次addLastのメソッドが実際に呼び出されているように見えますlinkLast。

void linkLast(E e) {
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    size++;
    modCount++;
}

関連する部分はlast、クラスで宣言されている場所でtransient Node<E> last; 、クラスが最後のノードへの「ポインター」を保持しているように見えます。次に、指定された新しいノードで更新します。したがって、リストのサイズに関係なく、O(1) である必要があります。

于 2013-09-08T00:48:31.683 に答える