devbox
代码探险家
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

LinkedList与链表

作者：代码探险家 | 2024-07-12 03:49:27

赞

踩

LinkedList与链表

1. ArrayList的缺陷

当在ArrayList任意位置插入或者删除元素时，就需要将后序元素整体往前或者往后搬移，时间复杂度为O(n)，效率比较低，因此ArrayList不适合做任意位置插入和删除比较多的场景。因此：java 集合中又引入了LinkedList，即链表结构。

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

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

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

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

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

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

  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()无参构造
public LinkedList(Collection<?extends<Ec)使用其他集合容器中元素构造List
  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的其他常用方法介绍

方法解释
boolean add(E e)尾插 e
void add(int index, E element)将 e 插入到 index 位置
boolean addAll(Collection c)尾插 c 中的元素
E remove(int index)删除 index 位置元素
boolean remove(Object o)删除遇到的第一个 o
E get(int index)获取下标 index 位置元素
E set(int index, E element)将下标 index 位置元素设置为 element
void clear()清空
boolean contains(Object o)判断 o 是否在线性表中
int indexOf(Object o)返回第一个 o 所在下标
int lastIndexOf(Object o)返回最后一个 o 的下标
List subList(int fromIndex, int toIndex)截取部分 list
  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的区别

不同点ArrayListLinkedList
存储空间上物理上一定连续逻辑上连续,物理上不一定连续
随机访问支持O(1)不支持：O(N)
头插需要搬移元素，效率低O(N)只需修改引用的指向，时间复杂度为O(1)
插入空间不够时需要扩容没有容量的概念
应用场景元素高效存储+频繁访问任意位置插入和删除频繁

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/代码探险家/article/detail/812549
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号