Java コレクション フレームワークについては、この記事を読むだけで十分です

いくつかの説明:

add(E e) は末尾に要素を追加することです。ArrayList は拡張される可能性がありますが、償却時間計算量 ) は依然として O(1) です。

add(intindex, E e) は、特定の位置に要素を追加することです。LinkedList は、最初にこの位置を見つけてから、この要素を追加する必要があります。これは単純な「add」ですが、 " アクション O(1) ですが、この位置を見つけるのはまだ O(n) です。 (これを O(1) だと考える人もいます。面接官に明確に説明し、責任を負うことを拒否してください。

remove(int Index) は、remove のインデックス上の要素です。したがって、

• ArrayList 内でこの要素を見つけるプロセスは O(1) ですが、削除後、後続の要素は 1 位置前に移動する必要があるため、償却された複雑さは O(n );
• LinkedList も最初にインデックスを見つける必要があります。このプロセスは O(n) であるため、全体のプロセスも O(n) です。
#remove(E e)

• LinkedList も検索する必要があります最初にこのプロセスは O(n) )、その後削除され、このプロセスは O(1) になり、合計は O(n) になります。
• 理由は何ですか?時間計算量の違いは?

回答

ArrayList は配列を使用して実装されているためです。
配列とリンク リストの最大の違いは、
• 配列にはランダムにアクセスできる (ランダム アクセス)
  .

  #この機能により、添字を使用すると O(1) 時間で任意の位置の数値を取得できますが、リンク リストではそれができず、先頭から 1 つずつしかたどることができません。

「追加と削除」についてはどうでしょうか？

この要素を見つける時間を考慮しない場合、

配列は物理的に連続しているため、要素を追加したり削除したりする場合は末尾でも大丈夫ですが、他の場所に移動すると後続の要素が削除されるため、効率が低下しますが、リンク リストでは次の要素との接続が簡単に切断されるため、新しい要素を直接挿入したり、古い要素を削除したりすることができます。

しかし、実際には、要素を見つけるまでの時間を考慮する必要があります。 。 。また、データ量が多い場合はArrayListを最後尾で動作させると高速になります。

##つまり:

1. #検索を変更して ArrayList を選択します。
2. ##最後に追加と削除を行う場合は ArrayList を選択します;
3. その他の場合、時間計算量が同じであれば、ArrayList を選択することをお勧めしますオーバーヘッドが小さいため、またはメモリがより効率的に使用されるためです。

List に関する最後の知識ポイントとして、Vector について話しましょう。これは年齢を明らかにする投稿でもあり、すべての偉人が使用します。

から継承し、最下層も配列を使用して実装されます。

しかし、追加される同期が多すぎるため、現在は非推奨になっています。

よくある面接の質問: Vector と ArrayList の違いは何ですか? これに答えるだけでは、あまり包括的ではありません。

スタック オーバーフローに関する投票の多かった回答を見てみましょう:

1 つ目は、先ほど述べたスレッド セーフティの問題です。 ;

これについてはソース コードを参照する必要があります:

これは ArrayList の拡張実装です。この 算術右シフト

が符号ビット を補いますが、容量には負の数がないため、やはり 0 を加算します。 1 ビットを右にシフトすると、 2 で除算され、定義される新しい容量は元の容量の 1.5 倍

Vector をもう一度見てみましょう:

通常、capacityIncrement を定義しないため、デフォルトでは 2 回拡張されます。

この2点に答えていただければ、間違いなく問題ありません。

Queue と Deque

Queue は、一方の端が入力でもう一方の端が出力である線形データ構造であり、Deque両端ですので全て出入り可能です。

Queue

Java の Queue インターフェイスは少しわかりにくいです。一般的に、セマンティクスは次のとおりです。キューの数 これらはすべて 先入れ先出し (FIFO) です。

しかし、ここには例外があります。つまり、PriorityQueue (ヒープとも呼ばれます) は、入力された時間順に出力されるのではなく、指定された優先順位に従って出力され、その操作は O ではありません。 (1)、時間 複雑さの計算は少し複雑なので、後ほど別の記事で説明します。

Queue メソッド公式ウェブサイト^[1]すべてをまとめました。2 つの API セットがあり、基本的な機能は同じですが、次のとおりです。

• 一方のグループは例外をスローし、
• #もう一方のグループは特別な値を返します。

例外をスロー	戻り値
add(e)	offer(e)
		なぜ例外がスローされるのでしょうか? たとえば、キュ​​ーが空の場合、remove() は例外をスローしますが、poll() は null を返し、element() は例外をスローしてピークを返します。 () は null を返すだけです。 add(e) が例外をスローするのはなぜですか? 一部のキューには、BlockingQueue などの容量制限があります。最大容量に達していて拡張されない場合は、例外がスローされます。ただし、オファー (e ) の場合、false が返されます。 それでは、どのように選択すればよいでしょうか? ： まず、これを使用する場合は、同じ API セットを使用してください。、表と裏を統一する必要があります。 ##第二に、ニーズに応じて。例外をスローする必要がある場合は、例外をスローするものを使用しますが、アルゴリズムの問​​題を実行する場合は基本的に使用されないため、特別な値を返すものを選択してください。 DequeDeque は両端から出入りできるため、当然のことながら次のターゲットになります。操作と最後の側の操作、各側には 2 つのグループがあり、1 つのグループは例外をスローし、もう 1 つのグループは特別な値を返します: Function##increaseaddFirst(e)/ addLast(e)offerFirst( e)/ offerLast(e)DeleteremoveFirst()/removeLast()pollFirst()/ pollLast()LookgetFirst()/ getLast() 例外をスローします 戻り値 #peekFirst()/ PeakLast() 使用する場合も同様ですので、使用する場合は同じグループを使用してください。 Queue と Deque のこれらの API の時間計算量は O(1) です。正確には、これは償却時間計算量です。 実装クラス 実装クラスには次の 3 つがあります: つまり、 「通常のキュー - 先入れ先出し」のセマンティクスを実装したい場合は、LinkedList または ArrayDeque を使用してそれを実現します。 #If 「優先キュー」のセマンティクスを実現したい場合は、PriorityQueue を使用します; 「スタック」のセマンティクスを実現したい場合は、ArrayDeque を使用します。 1 つずつ見てみましょう。 共通キューを実装する場合、 LinkedList と ArrayDeque のどちらを選択すればよいですか? StackOverflow [2] で最も投票数の多かった回答を見てみましょう: 概要 LinkedList には他の追加のオーバーヘッドがある一方で、効率が高い ArrayDeque を使用することをお勧めします。 ArrayDeque と LinkedList の違いは何ですか? 同じ質問がまだありますが、これが私が考える最良の要約です。 ArrayDeque これは、展開可能な配列、LinkedList はリンク リスト構造です。 ArrayDeque は null 値を保存できませんが、LinkedList は保存できます。 ArrayDeque in It is more先頭と末尾の追加と削除の操作は効率的ですが、LinkedList の削除は、中間の要素を削除する必要があり、その要素が見つかった場合にのみ O(1) になります。 #ArrayDeque はメモリ使用量の点でより効率的です。 したがって、null 値を保存する必要がない限り、ArrayDeque を選択してください。 それでは、非常に上級の面接官から尋ねられた場合、どのような状況で LinkedList の使用を選択すべきでしょうか? 答：Java 6 以前。。。因为 ArrayDeque 在 Java 6 之后才有的。。 为了版本兼容的问题，实际工作中我们不得不做一些妥协。。 那最后一个问题，就是关于 Stack 了。 Stack Stack 在语义上是 后进先出（LIFO） 的线性数据结构。 有很多高频面试题都是要用到栈的，比如接水问题，虽然最优解是用双指针，但是用栈是最直观的解法也是需要了解的，之后有机会再专门写吧。 那在 Java 中是怎么实现栈的呢？ 虽然 Java 中有 Stack 这个类，但是呢，官方文档都说不让用了！ 原因也很简单，因为 Vector 已经过被弃用了，而 Stack 是继承 Vector 的。 那么想实现 Stack 的语义，就用 ArrayDeque 吧： Deque<Integer> stack = new ArrayDeque<>(); Set 最后一个 Set，刚才已经说过了 Set 的特定是无序，不重复的。 就和数学里学的「集合」的概念一致。 Set 的常用实现类有三个： HashSet: 采用 Hashmap 的 key 来储存元素，主要特点是无序的，基本操作都是 O(1) 的时间复杂度，很快。 LinkedHashSet: 这个是一个 HashSet + LinkedList 的结构，特点就是既拥有了 O(1) 的时间复杂度，又能够保留插入的顺序。 TreeSet: 采用红黑树结构，特点是可以有序，可以用自然排序或者自定义比较器来排序；缺点就是查询速度没有 HashSet 快。 那每个 Set 的底层实现其实就是对应的 Map： 値はマップ内のキーに配置され、PRESENT は値に配置されます。これはプレースホルダーに相当する静的オブジェクトであり、各キーはこのオブジェクトを指します。 つまり、具体的な 実装原則 、追加、削除、変更、チェック 4 つの操作、および ハッシュ競合 、 hashCode( )/equals() などについては HashMap の記事で説明しているのでここでは詳しく説明しませんが、まだ見ていない友達は公式アカウントの背景で「HashMap」と返信することもできます記事を参照するには~ 概要 画像に戻る初めは透明なほうの毛糸でしょうか？ 実際には、PriorityQueue などの各データ構造の下に多くのコンテンツがありますが、この人がそれについて話すと長くなるため、この記事では詳しく説明しません。 。 記事が良いと思われる場合は、記事の最後にある「いいね」が再び表示されます。「いいね」と「読んで」を忘れずにお願いします~ 最後に、多くの読者からコミュニケーション グループについて質問を受けましたが、私は時差ぼけがあり、それを管理するのが難しいため、参加していません。 でも、今は一緒に管理してくれるプロの管理者が見つかったので、「チー姉妹の秘密基地」を準備中です。国内外の偉い人たちを招待して、皆さんにお届けする予定です。異なる視点。 第一段階の交流グループは7月中旬から上旬に開設予定ですので、その際はモーメントで招待状をお送りしますので、楽しみにお待ちください！