技術共有

LinkedList とリンクされたリスト

2024-07-12

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

1. ArrayList の欠陥

ArrayList 内の任意の位置に要素を挿入または削除する場合、後続の要素全体を前後に移動する必要があるため、時間計算量は O(n) となり、効率が比較的低くなります。そのため、ArrayList は挿入および削除には適していません。どの場面でも。そのため、リンクされたリスト構造である LinkedList が Java コレクションに導入されました。

2. リンクリスト

2.1 リンクリストの概念と構造

リンク リストは物理的に不連続なストレージ構造であり、データ要素の論理的順序はリンク リスト内の参照リンク順序によって実現されます。

2.2 リンクリストの実装

1. ヘッダー挿入メソッド addFirst()

  1. public void addFirst(int data) {
  2.         ListNode node = new ListNode(data);
  3.         node.next = head;
  4.         head = node;
  5.     }

2.末尾挿入メソッドaddLast()

  1. public void addList(int data) {
  2.         ListNode node = new ListNode(data);
  3.         if (head == null) {
  4.             head = node;
  5.         }
  6.         ListNode cur = head;
  7.         while (cur.next != null) {
  8.             cur = cur.next;
  9.         }
  10.         cur.next = node;
  11.     }

3.インデックスを追加します()

  1. public void addIndex(int index, int data) {
  2.         int len = size();
  3.         // 不合法
  4.         if (index < 0 || index > len) {
  5.             System.out.println("index不合法");
  6.             return;
  7.         }
  8.         // 空链表
  9.         if (index == 0) {
  10.             addFirst(data);
  11.             return;
  12.         }
  13.         // 尾部插入
  14.         if (index == len) {
  15.             addLast(data);
  16.             return;
  17.         }
  18.  
  19.         //中间位置插入
  20.         ListNode cur = head;
  21.         while (index - 1 != 0) {
  22.             cur = cur.next;
  23.             index--;
  24.         }
  25.         ListNode node = new ListNode(data);
  26.         node.next = cur.next;
  27.         cur.next = node;
  28.     }

4. を含む()

  1. public boolean contains(int key) {
  2.         ListNode cur = head;
  3.         while (cur != null) {
  4.             if (cur.val == key) {
  5.                 return true;
  6.             }
  7.             cur = cur.next;
  8.         }
  9.         return false;
  10.     }

5.削除()

  1. public void remove(int key) {
  2.         if (head == null) {
  3.             return;
  4.         }
  5.         if (head.val == key) {
  6.             head = head.next;
  7.         }
  8.  
  9.         ListNode cur = findNodeOfKey(key);
  10.         if (cur == null) {
  11.             return;
  12.         }
  13.         ListNode del = cur.next;
  14.         cur.next = del.next;
  15.     }
  16.  
  17.     private ListNode findNodeOfKey(int key) {
  18.         ListNode cur = head;
  19.         while (cur.next != null) {
  20.             if (cur.next.val == key) {
  21.                 return cur;
  22.             }
  23.             cur = cur.next;
  24.         }
  25.         return null;
  26.     }

6.すべてのキーを削除します。

  1. public void removeAllKey(int key) {
  2.         ListNode cur = head.next;
  3.         ListNode prev = head;
  4.         while (cur != null) {
  5.             if (cur.val == key) {
  6.                 prev.next = cur.next;
  7.             } else {
  8.                 prev = cur;
  9.             }
  10.             cur = cur.next;
  11.         }
  12.         if (head.val == key) {
  13.             head = head.next;
  14.         }
  15.     }

7.クリア()

  1.  public void clear() {
  2.         ListNode cur = head;
  3.         while (cur != null) {
  4.             ListNode curNext = cur.next;
  5.             cur.next = null;
  6.             cur = curNext;
  7.         }
  8.         head = null;
  9.     }

8.サイズ()

  1. public int size() {
  2.         int count = 0;
  3.         ListNode cur = head;
  4.         while (cur != null) {
  5.             count++;
  6.             cur = cur.next;
  7.         }
  8.         return count;
  9.     }

9.表示()

  1. public void display() {
  2.         ListNode cur = head;
  3.         while (cur != null) {
  4.             System.out.print(cur.val + " ");
  5.             cur = cur.next;
  6.         }
  7.     }

3.LinkedListのシミュレーション実装

  1. / 2、无头双向链表实现
  2. public class MyLinkedList {
  3. //头插法
  4. public void addFirst(int data){ }
  5. //尾插法
  6. public void addLast(int data){}
  7. //任意位置插入,第一个数据节点为0号下标
  8. public void addIndex(int index,int data){}
  9. //查找是否包含关键字key是否在单链表当中
  10. public boolean contains(int key){}
  11. //删除第一次出现关键字为key的节点
  12. public void remove(int key){}
  13. //删除所有值为key的节点
  14. public void removeAllKey(int key){}
  15. //得到单链表的长度
  16. public int size(){}
  17. public void display(){}
  18. public void clear(){}
  19. }
  1. package DounlyLinkedList;
  2.  
  3. import java.util.LinkedList;
  4. import java.util.List;
  5.  
  6. public class MyDoublyLinkedList implements IList {
  7.  
  8.     static class ListNode {
  9.         public int val;
  10.         public ListNode next;
  11.         public ListNode prev;
  12.  
  13.         public ListNode(int val) {
  14.             this.val = val;
  15.         }
  16.     }
  17.  
  18.     public ListNode head;
  19.     public ListNode last;
  20.  
  21.  
  22.     @Override
  23.     public void addFist(int data) {
  24.         ListNode node = new ListNode(data);
  25.         if (head == null) {
  26.             head = node;
  27.             last = node;
  28.         } else
  29.             node.next = head;
  30.         head.prev = node;
  31.         head = node;
  32.     }
  33.  
  34.     @Override
  35.     public void addLast(int data) {
  36.         ListNode node = new ListNode(data);
  37.         if (head == null) {
  38.             head = node;
  39.             last = node;
  40.         }
  41.         last.next = node;
  42.         node.prev = last;
  43.         last = node;
  44.     }
  45.  
  46.     @Override
  47.     public void addIndex(int index, int data) {
  48.         int len = size();
  49.         if (index < 0 || index > len) {
  50.             System.out.println("index 不合法！");
  51.         }
  52.  
  53.         if (index == 0) {
  54.             addFist(data);
  55.             return;
  56.         }
  57.  
  58.         if (index == len) {
  59.             addLast(data);
  60.             return;
  61.         }
  62.         ListNode cur = findIndex(index);
  63.         ListNode node = new ListNode(data);
  64.         node.next = cur;
  65.         cur.prev.next = node;
  66.         node.prev = cur.prev;
  67.         cur.prev = node;
  68.     }
  69.  
  70.     private ListNode findIndex(int index) {
  71.         ListNode cur = head;
  72.         while (index != 0) {
  73.             cur = cur.next;
  74.             index--;
  75.         }
  76.         return cur;
  77.     }
  78.  
  79.  
  80.     @Override
  81.     public boolean contains(int key) {
  82.         ListNode cur = head;
  83.         int count = 0;
  84.         while (cur != null) {
  85.             if (cur.val == key) {
  86.                 return true;
  87.             }
  88.             cur = cur.next;
  89.         }
  90.         return false;
  91.     }
  92.  
  93.     @Override
  94.     public void remove(int key) {
  95.         ListNode cur = head;
  96.         while (cur != null) {
  97.             if (cur.val == key) {
  98.                 if (cur == head) {
  99.                     head = head.next;
  100.                     if (head != null) {
  101.                         head.prev = null;
  102.                     }
  103.                     head.prev = null;
  104.                 } else {
  105.                     cur.prev.next = cur.next;
  106.                     if (cur.next == null) {
  107.                         last = last.prev;
  108.                     } else {
  109.                         cur.next.next = cur.prev;
  110.                     }
  111.                 }
  112.                 return;
  113.             }
  114.             cur = cur.next;
  115.  
  116.         }
  117.     }
  118.  
  119.     @Override
  120.     public void removeAllKey(int key) {
  121.         ListNode cur = head;
  122.         while (cur != null) {
  123.             if (cur.val == key) {
  124.                 if (cur == head) {
  125.                     head = head.next;
  126.                     if (head != null) {
  127.                         head.prev = null;
  128.                     }
  129.                     head.prev = null;
  130.                 } else {
  131.                     cur.prev.next = cur.next;
  132.                     if (cur.next == null) {
  133.                         last = last.prev;
  134.                     } else {
  135.                         cur.next.next = cur.prev;
  136.                     }
  137.                 }
  138.             }
  139.             cur = cur.next;
  140.         }
  141.     }
  142.  
  143.     @Override
  144.     public int size() {
  145.         ListNode cur = head;
  146.         int count = 0;
  147.         while (cur != null) {
  148.             count++;
  149.             cur = cur.next;
  150.         }
  151.         return count;
  152.     }
  153.  
  154.     @Override
  155.     public void clear() {
  156.         ListNode cur = head;
  157.         while (cur != null) {
  158.             ListNode curNext = cur.next;
  159.             cur.next = null;
  160.             cur.prev = null;
  161.             cur = curNext;
  162.         }
  163.         head = null;
  164.         last = null;
  165.     }
  166.  
  167.     @Override
  168.     public void dispaly() {
  169.         ListNode cur = head;
  170.         while (cur != null) {
  171.             System.out.print(cur.val + " ");
  172.             cur = cur.next;
  173.         }
  174.         System.out.println();
  175.     }
  176. }
  177.  
  178.  
  179.  
  180.  
  181.  
  1. package DounlyLinkedList;
  2.  
  3. public interface IList {
  4.     void addFist(int data);
  5.  
  6.     void addLast(int data);
  7.  
  8.     void addIndex(int index, int data);
  9.  
  10.     boolean contains(int key);
  11.  
  12.     void remove(int key);
  13.  
  14.     void removeAllKey(int key);
  15.  
  16.     int size();
  17.  
  18.     void clear();
  19.  
  20.     void dispaly();
  21. }

4.LinkedListの利用方法

4.1 LinkedLisとは

【イラスト】

1. LinkedList は List インターフェイスを実装します。

2. LinkedList の基礎となる層は二重リンク リストを使用します

3. LinkedList は RandomAccess インターフェイスを実装していないため、LinkedList はランダム アクセスをサポートしません。

4. LinkedList 内の任意の位置での要素の挿入と削除は比較的効率的であり、時間計算量は O(1) です。

5. LinkedList は、あらゆる場所での挿入シナリオにより適しています。

4.2 LinkedListの使用

1. LinkedListの構築

方法説明する
リンクリスト()引数なしの構築
パブリックLinkedList(コレクション他のコレクションコンテナの要素を使用してリストを構築する
  1. import java.util.LinkedList;
  2. import java.util.List;
  3.  
  4. public class Test {
  5.     public static void main(String[] args) {
  6.         List<Integer> list1 = new LinkedList<>();
  7.         List<String> list2 = new java.util.ArrayList<>();
  8.  
  9.         list2.add("javaSE");
  10.         list2.add("javaWeb");
  11.         list2.add("javaEE");
  12.  
  13.         List<String> list3 = new LinkedList<>(list2);
  14.         
  15.     }
  16. }
  17.  
  18.

2. LinkedList の他の一般的なメソッドの紹介

方法説明する
ブール加算(E e)テールプラグe
void add(int インデックス、E 要素)インデックス位置に e を挿入します
ブール型addAll(コレクションc)cの最後に要素を挿入します
E 削除(int インデックス)インデックス位置要素を削除する
ブール値削除(オブジェクトo)最初に見つかった o を削除します
E get(int インデックス)添え字のインデックス位置要素を取得します
E セット(int インデックス、E 要素)添字インデックス位置要素を要素に設定します
void をクリアする()クリア
ブール値を含む(オブジェクト o)o が線形表にあるかどうかを判断します
int インデックス(オブジェクト o)最初の o が位置するインデックスを返します
int lastIndexOf(オブジェクトo)最後の o の添え字を返します
リストのサブリスト(int fromIndex, int toIndex)リストの一部をインターセプトする
  1. public static void main(String[] args) {
  2. LinkedList<Integer> list = new LinkedList<>();
  3. list.add(1); // add(elem): 表示尾插
  4. list.add(2);
  5. list.add(3);
  6. list.add(4);
  7. list.add(5);
  8. list.add(6);
  9. list.add(7);
  10. System.out.println(list.size());
  11. System.out.println(list);
  12. // 在起始位置插入0
  13. list.add(0, 0); // add(index, elem): 在index位置插入元素elem
  14. System.out.println(list);
  15. list.remove(); // remove(): 删除第一个元素，内部调用的是removeFirst()
  16. list.removeFirst(); // removeFirst(): 删除第一个元素
  17. list.removeLast(); // removeLast(): 删除最后元素
  18. list.remove(1); // remove(index): 删除index位置的元素
  19. System.out.println(list);
  20. // contains(elem): 检测elem元素是否存在，如果存在返回true，否则返回false
  21. if(!list.contains(1)){
  22. list.add(0, 1);
  23. }
  24. list.add(1);
  25. System.out.println(list);
  26. System.out.println(list.indexOf(1)); // indexOf(elem): 从前往后找到第一个elem的位置
  27. System.out.println(list.lastIndexOf(1)); // lastIndexOf(elem): 从后往前找第一个1的位置
  28. int elem = list.get(0); // get(index): 获取指定位置元素
  29. list.set(0, 100); // set(index, elem): 将index位置的元素设置为elem
  30. System.out.println(list);
  31. // subList(from, to): 用list中[from, to)之间的元素构造一个新的LinkedList返回
  32. List<Integer> copy = list.subList(0, 3); 
  33. System.out.println(list);
  34. System.out.println(copy);
  35. list.clear(); // 将list中元素清空
  36. System.out.println(list.size());
  37. }

3. LinkedList の走査

  1. public static void main(String[] args) {
  2. LinkedList<Integer> list = new LinkedList<>();
  3. list.add(1); // add(elem): 表示尾插
  4. list.add(2);
  5. list.add(3);
  6. list.add(4);
  7. list.add(5);
  8. list.add(6);
  9. list.add(7);
  10. System.out.println(list.size());
  11. // foreach遍历
  12. for (int e:list) {
  13. System.out.print(e + " ");
  14. }
  15. System.out.println();
  16. // 使用迭代器遍历---正向遍历
  17. ListIterator<Integer> it = list.listIterator();
  18. while(it.hasNext()){
  19. System.out.print(it.next()+ " ");
  20. }
  21. System.out.println();
  22. // 使用反向迭代器---反向遍历
  23. ListIterator<Integer> rit = list.listIterator(list.size());
  24. while (rit.hasPrevious()){
  25. System.out.print(rit.previous() +" ");
  26. }
  27. System.out.println();
  28. }

5.ArrayListとLinkedListの違い

違い配列リストリンクリスト
収納スペースについて物理的に連続していなければならない論理的には連続的ですが、物理的には必ずしも連続的ではありません
ランダムアクセスサポートO(1)サポートされていない: O(N)
ヘッドプラグ要素を移動する必要があり、効率が低い O(N)参照のポインタを変更するだけで、時間計算量は O(1) になります。
入れるスペースが足りない場合は増設が必要容量という概念がない
アプリケーションシナリオ要素の効率的な保管 + 頻繁なアクセスあらゆる場所での頻繁な挿入と削除

個人プロフィール

彼は 30 年以上テクノロジーの研究に専念しており、Java、linux、javascript、php、css などのさまざまな言語に堪能であり、オープンソース分野で多くの貢献を行っています。将来の参考のために技術開発におけるいくつかの問題を共有する開発者ドキュメント ステーション。

私の連絡先情報

郵便