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

详解LinkedList与链表_listnode 与linkedlistnode

作者：我家自动化 | 2024-06-19 13:45:26

赞

踩

listnode 与linkedlistnode

1. ArrayList的缺陷

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

因此：java 集合中又引入了LinkedList，即链表结构。

2. 链表的概念及结构

链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的。

实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：

1. 单向或者双向

2. 带头或者不带头

3. 循环或者非循环

重点掌握两种:

  • 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如 哈希桶、图的邻接表等等。

  • 无头双向链表：在Java的集合框架库中LinkedList底层实现就是无头双向循环链表。

3. 链表的实现

无头单向非循环链表实现

  1. public class MySingleLinkedList {
  2.  
  3.     // 节点内部类
  4.     static class ListNode {
  5.         public int val;
  6.         public ListNode next;
  7.  
  8.         public ListNode(int val) {
  9.             this.val = val;
  10.         }
  11.     }
  12.  
  13.     public ListNode head;// 不初始化，默认为null
  14.  
  15.     public void dispaly() {
  16.         ListNode cur = this.head;
  17.         while (cur != null) {
  18.             System.out.print(cur.val + " ");
  19.             cur = cur.next;
  20.         }
  21.         System.out.println(" ");
  22.     }
  23.  
  24.     // 得到单链表的长度
  25.     public int size() {
  26.         int count = 0;
  27.         ListNode cur = head;
  28.         while (cur != null) {
  29.             count++;
  30.             cur = cur.next;
  31.         }
  32.         return count;
  33.     }
  34.  
  35.     // 查找是否包含关键字key是否在单链表当中
  36.     public boolean contains(int key) {
  37.         ListNode cur = this.head;
  38.         while (cur != null) {
  39.             if (cur.val == key) {
  40.                 return true;
  41.             }
  42.             cur = cur.next;
  43.         }
  44.         return false;
  45.     }
  46.  
  47.     // 头插法
  48.     // 先绑定和后面节点的关系
  49.     public void addFirst(int data) {
  50.         ListNode node = new ListNode(data);
  51.         node.next = head;
  52.         head = node;
  53.     }
  54.  
  55.     // 尾插法
  56.     public void addLast(int data) {
  57.         ListNode node = new ListNode(data);
  58.         ListNode cur = this.head;
  59.         if(cur == null) {
  60.             this.head = node;
  61.         }else {
  62.             while (cur.next != null) {
  63.                 cur = cur.next;
  64.             }
  65.             //cur已经是尾节点了
  66.             cur.next = node;
  67.         }
  68.     }
  69.  
  70.     // 任意位置插入,第一个数据节点为0号下标
  71.     public void addIndex(int index, int data) {
  72.         if (index < 0 || index > size()) {
  73.             System.out.println("index位置不合法");
  74.             throw new IndexWrongFulException("index位置不合法");
  75.         }
  76.         if (index == 0) {
  77.             addFirst(data);
  78.             return;
  79.         }
  80.         if (index == size()) {
  81.             addLast(data);
  82.             return;
  83.         }
  84.         // 先走index-1步,找到cur
  85.         ListNode cur = findIndexSubOne(index);
  86.         ListNode node = new ListNode(data);
  87.         //
  88.         node.next = cur.next;
  89.         cur.next = node;
  90.     }
  91.     private ListNode findIndexSubOne(int index) {
  92.         ListNode cur = this.head;
  93.         while (index - 1 != 0) {
  94.             cur = cur.next;
  95.             index--;
  96.         }
  97.         return cur;
  98.     }
  99.  
  100.     // 删除第一次出现关键字为key的节点
  101.     public void remove(int key) {
  102.         // 判断链表为空
  103.         if (this.head == null) {
  104.             return;
  105.         }
  106.         // 删除头节点
  107.         if (this.head.val == key) {
  108.             this.head = this.head.next;
  109.             return;
  110.         }
  111.         ListNode cur = findPrevOfKey(key);
  112.         if (cur == null) {
  113.             System.out.println("没有你要删除的数字");
  114.             return;
  115.         }
  116.         ListNode del = cur.next;
  117.         cur.next = del.next;
  118.     }
  119.     private ListNode findPrevOfKey(int key) {
  120.         ListNode cur = this.head;
  121.         while (cur.next != null) {
  122.             if (cur.next.val == key) {
  123.                 return cur;
  124.             }
  125.             cur = cur.next;
  126.  
  127.         }
  128.         return null;
  129.     }
  130.  
  131.     // 删除所有值为key的节点
  132.     public void removeAllKey(int key) {
  133.         if (this.head == null) {
  134.             return;
  135.         }
  136.         ListNode cur = this.head.next;
  137.         ListNode pre = this.head;
  138.         while (cur != null) {
  139.             if (cur.val == key) {
  140.                 pre.next = cur.next;
  141.                 cur = cur.next;
  142.             } else {
  143.                 pre = cur;
  144.                 cur = cur.next;
  145.             }
  146.         }
  147.         if (this.head.val == key) {
  148.             head = head.next;
  149.         }
  150.     }
  151.  
  152.     public void clear() {
  153.         this.head = null;
  154.     }

4.什么是LinkedList

LinkedList官方文档

LinkedList的底层是双向链表结构，由于链表没有将元素存储在连续的空间中，元素存储在单独的节点中，然后通过引用将节点连接起来了，因此在在任意位置插入或者删除元素时，不需要搬移元素，效率比较高。

在集合框架中，LinkedList也实现了List接口，具体如下：

【说明】
1. LinkedList实现了List接口
2. LinkedList的底层使用了 双向链表
3. LinkedList 没有实现RandomAccess接口，因此LinkedList 不支持随机访问
4. LinkedList的 任意位置插入和删除元素时效率比较高， 时间复杂度为O(1)

5.LinkedList的模拟实现

LinkedList底层就是一个双向链表

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

6.LinkedList的使用

6.1LinkedList的构造

LinkedList()

无参构造

public LinkedList(Collection<? extends E> c)

使用其他集合容器中元素构造List

  1. public static void main(String[] args) { 
  2.    // 构造一个空的LinkedList
  3.    List<Integer> list1 = new LinkedList<>();
  4.    List<String> list2 = new ArrayList<>();
  5.    list2.add("JavaSE");
  6.    list2.add("JavaWeb");
  7.    list2.add("JavaEE");
  8.    // 使用ArrayList构造LinkedList
  9.    List<String> list3 = new LinkedList<>(list2); 
  10. }

6.2常用方法

方法

解释

boolean add(E e)

尾插e

void add(int index, E element)

将e插入到index位置

boolean addAll(Collection<? extends E> 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 lastlndexOf(Object o)

返回最后一个o的下标

List<E> subList(int fromIndex, int tolndex)

截取部分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. }

6.3LinkedList的遍历

  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. }

7.ArrayList和LinkedList的区别

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

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

  

闽ICP备14008679号