【Java数据结构】---List(LinkedList)

自由的羽毛  论坛元老 | 2024-8-16 20:49:06 | 来自手机 | 显示全部楼层 | 阅读模式
打印 上一主题 下一主题
楼主

主题 1059|帖子 1059|积分 3177

乐观学习，乐观生存，才华不断进步啊！！！

我的主页：optimistic_chen
    我的专栏：c语言 ，Java
    欢迎大家访问~
创作不易，大佬们点赞鼓励下吧~

  
  
媒介


上篇博客详细写了ArrayList的相干问题，包括上图（极其紧张），我会在最近几篇博客中都有附上。
ArrayList的长处很明显，底层逻辑是一个数组，它通过下标去访问数据的速度非常快。但是在ArrayList任意位置插入或者删除元素时，就需要将后序元素整体往前或者往后搬移，时间复杂度为O(n)，效率比较低
以是java集合框架中引入了LinkedList类，即链表结构。
链表（MySingleList）

   链表，作为线性表的一种，它与顺序表截然相反：链表是一种物理存储结构 上 非连续存储结构， 数据元素的逻辑顺序是通过链表中的引用 链接序次实现的
  之前C语言相识过这方面的知识C语言—链表专题，以是我们有一定的基础，我相信链表对于大家一定是熟悉的存在。我们先由易入难，先本身实验一下单链表（MySingleList）的功能实现，为接下来的 LinkedList(无头双向链表) 打下基础.
   接口
  1. public interface IList {
  2.     public void addFirst(int data);
  4.     public void addLast(int data);
  6.     public void addIndex(int index,int data);
  8.     public boolean contains(int key);
  10.     public void remove(int key);
  12.     public void removeAllKey(int key);
  14.     public int size();
  16.     public void clear();
  18.     public void display();
  19. }
复制代码
详细功能代码

头插法
  1. @Override
  2.     public void addFirst(int data) {
  3.         ListNode node = new ListNode(data);
  4.         node.next=head;
  5.         head=node;
  6.     }
复制代码
尾插法
  1. @Override
  2.     public void addLast(int data) {
  3.         ListNode node =new ListNode(data);
  4.         if(head==null){
  5.             head = node;
  6.             return;
  7.         }
  8.         ListNode cur=head;
  9.         while(cur.next!=null){
  10.             cur= cur.next;
  11.         }
  12.         cur.next=node;
  13.     }
复制代码
任意位置插入,第一个数据节点为0号下标
  1. @Override
  2.     public void addIndex(int index, int data) {
  3.         int len=size();
  4.         if(index<0||index>len){
  5.             System.out.println("index位置不合法");
  6.             return;
  7.         }
  8.         if(index==0){
  9.             addFirst(data);
  10.             return;
  11.         }
  12.         if(index==len){
  13.             addLast(data);
  14.             return;
  15.         }
  16.         ListNode cur=head;
  17.         while(index-1!=0){
  18.             cur=cur.next;
  19.             index--;
  20.         }
  21.         ListNode node=new ListNode(data);
  22.         node.next= cur.next;
  23.         cur.next=node;
  24.     }
复制代码
查找是否包含关键字key是否在单链表当中
  1. @Override
  2.     public boolean contains(int key) {
  3.         ListNode cur=head;
  4.         while(cur!=null){
  5.             if(cur.val==key){
  6.                 return true;
  7.             }
  8.             cur=cur.next;
  9.         }
  10.         return false;
  11.     }
复制代码
删除第一次出现关键字为key的节点
  1. @Override
  2.     public void remove(int key) {
  3.         if(head==null){
  4.             return;
  5.         }
  6.         if(head.val==key){
  7.             head=head.next;
  8.             return;
  9.         }
  10.         ListNode cur=findNodeOfKey(key);
  11.         if(cur==null){
  12.             return;
  13.         }
  14.         ListNode del= cur.next;
  15.         cur.next=del.next;
  17.     }
  18.     private ListNode findNodeOfKey(int key){
  19.         ListNode cur=head;
  20.         while(cur.next!=null) {
  21.             if (cur.next.val == key) {
  22.                 return cur;
  23.             }
  24.             cur= cur.next;
  25.         }
  26.         return null;
  27.     }
复制代码
删除所有值为key的节点
  1. @Override
  2.     public void removeAllKey(int key) {
  3.         if(head==null){
  4.             return;
  5.         }
  7.         ListNode prev=head;
  8.         ListNode cur=head.next;
  10.         while(cur!=null){
  11.             if(cur.val==key){
  12.                 prev.next=cur.next;
  13.                 cur= cur.next;
  14.             }else{
  15.                 prev=cur;
  16.                 cur= cur.next;
  17.             }
  18.             if(head.val==key){
  19.                 head=head.next;
  20.                 return;
  21.             }
  22.         }
  23.     }
复制代码
得到单链表的长度
  1. @Override
  2.     public int size() {
  3.         int len=0;
  4.         ListNode cur=head;
  5.         while(cur!=null){
  6.             len++;
  7.             cur=cur.next;
  8.         }
  9.         return len;
  10.     }
复制代码
清空链表
  1. @Override
  2.     public void clear() {
  3.         ListNode cur=head;
  4.         while(cur!=null){
  5.             ListNode curN=cur.next;
  6.             cur.next=null;
  7.             cur=curN;
  8.         }
  9.         head=null;
  10.     }
复制代码
LinkedList简介



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

  • LinkedList实现了List接口
  • LinkedList的底层使用了双向链表
  • LinkedList没有实现RandomAccess接口，因此LinkedList不支持随机访问
  • LinkedList的任意位置插入和删除元素时效率比较高，时间复杂度为O(1)
  • LinkedList比较得当任意位置插入的场景
LinkedList的模仿实现


头插法
  1. @Override
  2.     public void addFirst(int data) {
  3.         ListNode node=new ListNode(data);
  4.         if(head==null){
  5.             head=last=node;
  6.         }else{
  7.             node.next=head;
  8.             head.prev=node;
  9.             head=node;
  10.         }
  11.     }
复制代码
尾插法
  1. @Override
  2.     public void addLast(int data) {
  3.         ListNode node=new ListNode(data);
  4.         if(head==null){
  5.             head=last=node;
  6.         }else{
  7.             last.next=node;
  8.             node.prev=last;
  9.             last= last.next;
  10.         }
  11.     }
复制代码
任意位置插入,第一个数据节点为0号下标
  1. @Override
  2.     public void addIndex(int index, int data) {
  3.         int len=size();
  4.         if(index<0||index>len){
  5.             return;
  6.         }
  7.         if(index==0){
  8.             addFirst(data);
  9.             return;
  10.         }
  11.         if(index==len){
  12.             addLast(data);
  13.             return;
  14.         }
  15.         ListNode cur=findIndex(index);
  16.         ListNode node=new ListNode(data);
  17.         node.next=cur;
  18.         cur.prev.next=node;
  19.         node.prev=cur.prev;
  20.         cur.next=node;
  21.     }
  22. private ListNode findIndex(int index){
  23.         ListNode cur=head;
  24.         while(index!=0){
  25.             cur= cur.next;
  26.             index--;
  27.         }
  28.         return cur;
  29.     }
复制代码
查找是否包含关键字key是否在链表当中
  1. @Override
  2.     public boolean contains(int key) {
  3.         ListNode cur=head;
  4.         int count=0;
  5.         while(cur!=null){
  6.             if(cur.val==key) {
  7.                 return true;
  8.             }
  9.             cur= cur.next;
  10.         }
  11.         return false;
  12.     }
复制代码
删除第一次出现关键字为key的节点
  1. @Override
  2.     public void remove(int key) {
  3.         ListNode cur=head;
  4.         while(cur!=null){
  5.             //开始删除
  6.             if(cur.val==key){
  7.                 //有可能是头节点
  8.                 if(cur==head){
  9.                     head = head.next;
  10.                     if(head!=null){
  11.                         head.prev=null;
  12.                     }
  13.                 }else{
  14.                     cur.prev.next= cur.next;
  15.                     if(cur.next==null){
  16.                         //有可能是尾节点
  17.                         last= last.prev;
  18.                     }else{
  19.                         cur.next.prev= cur.prev;
  20.                     }
  21.                 }
  22.                 return;
  23.             }else{
  24.                 cur = cur.next;
  25.             }
  26.         }
  27.     }
复制代码
删除所有值为key的节点
  1. @Override
  2.     public void removeAllKey(int key) {
  3.         ListNode cur=head;
  4.         while(cur!=null){
  5.             //开始删除
  6.             if(cur.val==key){
  7.                 //有可能是头节点
  8.                 if(cur==head){
  9.                     head = head.next;
  10.                     if(head!=null){
  11.                         head.prev=null;
  12.                     }
  13.                 }else{
  14.                     cur.prev.next= cur.next;
  15.                     if(cur.next==null){
  16.                         //有可能是尾节点
  17.                         last= last.prev;
  18.                     }else{
  19.                         cur.next.prev= cur.prev;
  20.                     }
  21.                 }
  22.             }else{
  23.                 cur = cur.next;
  24.             }
  25.         }
  27.     }
复制代码
LinkedList的使用

前面我们自主实现了LinkedList的各种方法，只是为了大家更好的明白和学习，以后做题大概会运用到类似的想法或思路，可以更加高效的完成标题，平时也可以直接使用LinkedList下的方法。如下图：

LinkedList的构造


  1. public static void main(String[] args) {
  2.         List<Integer> list1=new LinkedList<Integer>();
  3.         LinkedList<Integer> list2 = new LinkedList<Integer>();
  4.         
  5.    //使用ArrayList构造LinkedList     
  6.         List<String> list3=new ArrayList<>();
  7.         List<String> list4=new LinkedList<>(list3);
  8.     }
复制代码
为什么可以有的构造可以用List，有的用LinkedList,甚至出现了ArrayList？一切都是这张贯穿整个数据结构的图。

LinkedList的方法

  1. public static void main(String[] args) {
  2.   LinkedList<Integer> list = new LinkedList<>();
  3.   list.add(1);  // add(): 表示尾插
  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);
  13.   // subList(from, to): 用list中[from, to)之间的元素构造一个新的LinkedList返回
  14.   List<Integer> list2 = list.subList(0, 3);
  15.   System.out.println(list);
  16.   System.out.println(list2);
  17.   list.clear();        // 将list中元素清空
  18.   System.out.println(list.size());
  19. }
复制代码
LinkedList的遍历

之前ArrayList博客【Java数据结构】—List(ArrayList) 讲过线性表的遍历，这次补充一下…
  1. public static void main(String[] args) {
  2.   LinkedList<Integer> list = new LinkedList<>();
  3.   list.add(1);  // add(): 表示尾插
  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.   
  12. // 使用反向迭代器---反向遍历
  13.   ListIterator<Integer> it = list.listIterator(list.size());
  14.   while (it.hasPrevious()){
  15.     System.out.print(it.previous() +" ");
  16. }
  17. }
复制代码
ArrayList和LinkeddList的区别

不同ArrayListLinkedList存储空间物理上一定连续逻辑上连续，但物理上不一定连续随机访问支持O(1)不支持O(n)头插空间不够时扩容不存在容量的概念运用场景元素高效存储+频仍访问频仍任意位置的插入和删除 完结

好了，到这里Java语法部分就已经结束了~
如果这个系列博客对你有帮助的话，可以点一个免费的赞并收藏起来哟~
可以点点关注，避免找不到我~ ，我的主页：optimistic_chen
我们下期不见不散~~Java
下期预告: 【Java数据结构】- - - List

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

本帖子中包含更多资源

您需要 登录 才可以下载或查看，没有账号？立即注册

x
回复

使用道具 举报

0 个回复

倒序浏览
返回列表

快速回复

高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 or 立即注册

本版积分规则

自由的羽毛

论坛元老
这个人很懒什么都没写!

楼主热帖

标签云

AI 运维 CIO 存储 服务器
微信订阅号
微信服务号
微信客服
小程序
H5
关于我们 商务合作 网站地图
©Copyright 2022-2024 杭州祥升科技有限公司 版权所有 浙ICP备20004199号
快速回复 返回顶部 返回列表