Condivisione della tecnologia

LinkedList ed elenco collegato

2024-07-12

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

1. Difetti di ArrayList

Quando si inseriscono o si eliminano elementi in qualsiasi posizione in ArrayList, è necessario spostare tutti gli elementi successivi avanti o indietro. La complessità temporale è O(n) e l'efficienza è relativamente bassa Pertanto, ArrayList non è adatto per l'inserimento e l'eliminazione posizione. Pertanto: LinkedList, la struttura dell'elenco collegato, viene introdotta nelle raccolte Java.

2. Elenco collegato

2.1 Concetto e struttura di lista concatenata

Un elenco collegato è una struttura di archiviazione fisicamente non continua e l'ordine logico degli elementi di dati viene ottenuto tramite l'ordine dei collegamenti di riferimento nell'elenco collegato.

2.2 Implementazione dell'elenco collegato

1. Metodo di inserimento dell'intestazione addFirst()

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

2. Metodo di inserimento della coda 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.addIndex()

  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. contiene()

  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.rimuovi()

  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.rimuoviTutteLeChiavi()

  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.cancella()

  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.dimensione()

  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.visualizza()

  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.Simulazione dell'implementazione di 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.Utilizzo di LinkedList

4.1 Cos'è LinkedLis

【illustrare】

1. LinkedList implementa l'interfaccia Elenco

2. Il livello sottostante di LinkedList utilizza un elenco doppiamente collegato

3. LinkedList non implementa l'interfaccia RandomAccess, quindi LinkedList non supporta l'accesso casuale.

4. L'inserimento e l'eliminazione di elementi in qualsiasi posizione in LinkedList è relativamente efficiente e la complessità temporale è O (1)

5. LinkedList è più adatto per scenari di inserimento in qualsiasi posizione

4.2 Utilizzo di LinkedList

1. Costruzione di LinkedList

metodospiegare
Lista collegata()Costruzione senza argomenti
pubblico LinkedList(CollezioneCostruisci un elenco utilizzando elementi di altri contenitori di raccolta
  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. Introduzione ad altri metodi comuni di LinkedList

metodospiegare
booleano add(E e)tappo di coda e
void add(int indice, E elemento)Inserire e nella posizione dell'indice
booleano addAll(Collezione c)Inserisci gli elementi in c alla fine
E rimuovi(int indice)Elimina l'elemento della posizione dell'indice
booleano rimuovi(Oggetto o)Elimina la prima o incontrata
E get(int indice)Ottieni l'elemento di posizione dell'indice in pedice
E set(int indice, E elemento)Imposta l'elemento di posizione dell'indice del pedice su element
vuoto cancella()Chiaro
booleano contiene(Oggetto o)Determina se o è nella tavola lineare
int indiceOf(Oggetto o)Restituisce l'indice in cui si trova la prima o
int lastIndexOf(Oggetto o)Restituisce il pedice dell'ultima o
Elenco subList(int fromIndex, int toIndex)Intercetta parte della lista
  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. Attraversamento della 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.La differenza tra ArrayList e LinkedList

differenzaLista di arrayLista collegata
Sullo spazio di archiviazionedeve essere fisicamente continuaLogicamente continuo, non necessariamente fisicamente continuo
accesso casualeSupporto O(1)Non supportato: O(N)
Tappo di testaNecessità di spostare elementi, bassa efficienza O(N)Basta modificare il puntatore del riferimento, la complessità temporale è O(1)
inserireQuando lo spazio è insufficiente, è necessaria l'espansioneNessun concetto di capacità
Scenari applicativiStoccaggio efficiente degli elementi + accesso frequenteInserimento ed eliminazione frequenti in qualsiasi posizione

Profilo personale

Si dedica alla ricerca tecnologica da più di 30 anni ed è esperto in vari linguaggi come Java, Linux, Javascript, php, css, ecc. Ha dato numerosi contributi nel campo dell'open source stazione di documentazione per gli sviluppatori per condividere alcuni problemi nello sviluppo della tecnologia per riferimento futuro

le mie informazioni di contatto

Posta