当前位置： 首页 > news >正文

LinkedList与链表

news 来源：原创 2024/9/29 13:25:58

目录

1. 链表

1.1 链表的概念及结构

2. 无头单向非循环链表实现 

3.LinkedList的模拟实现

4.LinkedList的使用 

4.1 什么是LinkedList

4.2 LinkedList的使用 

5. ArrayList和LinkedList的区别 

1. 链表

1.1 链表的概念及结构

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

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

1. 单向或者双向

2. 带头或者不带头

3. 循环或者非循环

虽然有这么多的链表的结构，但是我们重点掌握两种:

无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如 哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。

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

2. 无头单向非循环链表实现 

public class MySingleList {class ListNode {public int val;public ListNode next;public ListNode(int val) {this.val = val;}}//头节点public ListNode head;public void createList() {ListNode node1 = new ListNode(12);ListNode node2 = new ListNode(23);ListNode node3 = new ListNode(34);ListNode node4 = new ListNode(45);ListNode node5 = new ListNode(56);node1.next = node2;node2.next = node3;node3.next = node4;node4.next = node5;this.head = node1;}//遍历单链表public void show() {ListNode cur = head;while(cur != null) {System.out.print(cur.val + " ");cur = cur.next;}System.out.println();}//得到单链表的长度 --》 链表中节点的个数public int size() {ListNode cur = head;int count = 0;while(cur != null) {count++;cur = cur.next;}return count;}//查找是否包含关键字key是否在单链表当中public boolean contains(int key) {ListNode cur = head;while(cur != null) {if(cur.val == key) {return true;}cur = cur.next;}return false;}//头插法public void addFirst(int data) {ListNode node = new ListNode(data);node.next = head;head = node;}//尾插法public void addLast(int data) {ListNode node = new ListNode(data);if(head == null) {head = node;return;}ListNode cur = head;while(cur.next != null) {cur = cur.next;}cur.next = node;}//任意位置插入,第一个数据节点为0号下标public void addIndex(int index, int data) {if(index < 0 || index > size()) {throw new IndexOfBounds("插入数据时, index位置不合法, 此时, index: " + index);}if(0 == index) {addFirst(data);return;}if (size() == index) {addLast(data);return;}
//        ListNode node = new ListNode(data);
//        ListNode preCur = head;
//        ListNode cur = head.next;
//        while(index-1 != 0) {
//            cur = cur.next;
//            preCur = preCur.next;
//            index--;
//        }
//        node.next = cur;
//        preCur.next = node;//找到插入位置的前一个节点ListNode cur = findIndex(index);//插入ListNode node = new ListNode(data);node.next = cur.next;cur.next = node;}// 保存插入节点的前驱节点public ListNode findIndex(int index) {ListNode cur = head;while(index - 1 != 0) {cur = cur.next;index--;}return cur;}//删除第一次出现关键字为key的节点public void remove(int key) {if(head == null) {return;}if(head.val == key) {head = head.next;return;}ListNode prev = searchPrev(key);if(prev == null) {System.out.println("没有你要删除的数据");return;}ListNode del = prev.next;prev.next = del.next;}// 保存被删除的前驱节点public ListNode searchPrev(int key) {ListNode prev = head;while(prev.next != null) {if(prev.next.val == key) {return prev;}prev = prev.next;}return null;}//删除所有值为key的节点public void removeAllKey(int key) {if(head == null) {return;}ListNode prev = head;ListNode cur = head.next;while(cur != null) {if(cur.val == key) {prev.next = cur.next;cur = cur.next;}else {cur = cur.next;prev = prev.next;}}if(head.val == key) {head = head.next;}}// 清空链表public void clear() {this.head = null;}
}

3.LinkedList的模拟实现

public class MyLinkedList {static class ListNode {public int val;public ListNode prev;public ListNode next;public ListNode(int val) {this.val = val;}}public ListNode head;public ListNode last;public int size() {int len = 0;ListNode cur = head;while (cur != null) {len++;cur = cur.next;}return len;}// 打印public void display() {ListNode cur = head;while (cur != null) {System.out.print(cur.val + " ");cur = cur.next;}System.out.println();}//查找是否包含关键字key是否在链表当中public boolean contains(int key) {ListNode cur = head;while (cur != null) {if (cur.val == key) {return true;}cur = cur.next;}return false;}//头插法public void addFirst(int data) {ListNode node = new ListNode(data);if (head == null) {head = node;last = node;return;}node.next = head;head.prev = node;head = node;}//尾插法public void addLast(int data) {ListNode node = new ListNode(data);if (head == null) {head = node;last = node;return;}last.next = node;node.prev = last;last = node;}//任意位置插入,第一个数据节点为0号下标public void addIndex(int index,int data) {int size = size();if(index < 0 || index > size) {throw new IndexOfBounds("双向链表index不合法！");}if(index == 0) {addFirst(data);return;}if(index == size()) {addLast(data);return;}ListNode cur = head;while(index != 0) {cur = cur.next;index--;}ListNode node = new ListNode(data);node.next = cur;cur.prev.next = node;node.prev = cur.prev;cur.prev = node;}public void remove(int key) {ListNode cur = head;while(cur != null) {// 开始删if(cur.val == key) {// 删除的如果是头节点if(cur == head) {// 如果只有一个节点呢head = head.next;if (head != null) {head.prev = null;}else {last = null;}return;}// 删除的如果是尾节点if(cur == last) {last = last.prev;last.next = null;return;}// 删除的如果是中间节点cur.prev.next = cur.next;cur.next.prev = cur.prev;return;}else {cur = cur.next;}}System.out.println("没有你要删除的节点!");}//删除所有值为key的节点public void removeAllKey(int key) {ListNode cur = head;while (cur != null) {// 开始删if (cur.val == key) {// 删除的如果是头节点if (cur == head) {// 如果只有一个节点呢head = head.next;if (head != null) {head.prev = null;} else {last = null;}}else if (cur == last) {// 删除的如果是尾节点last = last.prev;last.next = null;}else {// 删除的如果是中间节点cur.prev.next = cur.next;cur.next.prev = cur.prev;}}cur = cur.next;}}// 清空public void clear() {ListNode cur = head;while (cur != null) {ListNode curNext = cur.next;cur.prev = null;cur.next = null;}head = null;last = null;}
}

4.LinkedList的使用 

4.1 什么是LinkedList

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

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

1. LinkedList实现了List接口

2. LinkedList的底层使用了双向链表

3. LinkedList没有实现RandomAccess接口，因此LinkedList不支持随机访问

4. LinkedList的任意位置插入和删除元素时效率比较高，时间复杂度为O(1)

5. LinkedList比较适合任意位置插入的场景 

4.2 LinkedList的使用 

1. LinkedList的构造

public static void main(String[] args) {// 构造一个空的LinkedListList<Integer> list1 = new LinkedList<>();List<String> list2 = new java.util.ArrayList<>();list2.add("JavaSE");list2.add("JavaWeb");list2.add("JavaEE");// 使用ArrayList构造LinkedListList<String> list3 = new LinkedList<>(list2);
}

2. LinkedList的其他常用方法介绍

3. LinkedList的遍历

public static void main(String[] args) {LinkedList<Integer> list = new LinkedList<>();list.add(1); // add(elem): 表示尾插list.add(2);list.add(3);list.add(4);list.add(5);list.add(6);list.add(7);System.out.println(list.size());// foreach遍历for (int e:list) {System.out.print(e + " ");}System.out.println();// 使用迭代器遍历---正向遍历ListIterator<Integer> it = list.listIterator();while(it.hasNext()){System.out.print(it.next()+ " ");}System.out.println();// 使用反向迭代器---反向遍历ListIterator<Integer> rit = list.listIterator(list.size());while (rit.hasPrevious()){System.out.print(rit.previous() +" ");}System.out.println();
}

5. ArrayList和LinkedList的区别 

ArrayList适合用于“读多写少”的场景，因为它的随机访问性能较好；而LinkedList则更适合于频繁的插入和删除操作，尤其是在列表的两端，因为它能够在这些情况下提供更好的性能。然而，LinkedList的内存开销通常比ArrayList要大，因为每个节点都需要维护额外的引用信息。   

相关文章：

  • Kubernetes面试整理-Kubernetes的主要组件有哪些？
  • SpringBoot三层架构
  • 高分论文密码---大尺度空间模拟预测与数字制图
  • 使用开源的zip.cpp和unzip.cpp实现压缩包的创建与解压（附源码）
  • 【机器学习】第2章 线性回归及最大熵模型
  • Android Room数据库使用介绍
  • SpringBoot3 整合 Mybatis 完整版
  • 【MySQL】分库分表
  • USB - 常用开发工具
  • C++ -- 红黑树的基本操作
  • 从零开始精通Onvif之图片抓拍
  • Mybatis --- 动态SQL 和数据库连接池
  • docker Pulling fs layer 含义
  • DeepSpeed Monitoring Comm. Logging
  • 速盾：什么是高防CDN?有什么优势?
  • “大数据应用场景”之隔壁老王（连载四）
  • 【个人向】《HTTP图解》阅后小结
  • 【跃迁之路】【477天】刻意练习系列236（2018.05.28）
  • 4月23日世界读书日 网络营销论坛推荐《正在爆发的营销革命》
  • Apache的基本使用
  • Codepen 每日精选（2018-3-25）
  • Java深入 - 深入理解Java集合
  • JS数组方法汇总
  • miniui datagrid 的客户端分页解决方案 - CS结合
  • node入门
  • PHP 小技巧
  • SpringCloud集成分布式事务LCN (一)
  • vue总结
  • 阿里云应用高可用服务公测发布
  • 大整数乘法-表格法
  • 电商搜索引擎的架构设计和性能优化
  • 诡异！React stopPropagation失灵
  • 技术发展面试
  • 微服务核心架构梳理
  • 小程序开发之路（一）
  • 移动端解决方案学习记录
  • 仓管云——企业云erp功能有哪些？
  • ​如何使用ArcGIS Pro制作渐变河流效果
  • # .NET Framework中使用命名管道进行进程间通信
  • # centos7下FFmpeg环境部署记录
  • #中的引用型是什么意识_Java中四种引用有什么区别以及应用场景
  • （Arcgis）Python编程批量将HDF5文件转换为TIFF格式并应用地理转换和投影信息
  • (C#)Windows Shell 外壳编程系列9 - QueryInfo 扩展提示
  • （javaweb）Http协议
  • (leetcode学习)236. 二叉树的最近公共祖先
  • (pojstep1.3.1)1017(构造法模拟)
  • (二) 初入MySQL 【数据库管理】
  • （二）丶RabbitMQ的六大核心
  • （附源码）springboot工单管理系统 毕业设计 964158
  • （附源码）springboot炼糖厂地磅全自动控制系统 毕业设计 341357
  • （力扣）1314.矩阵区域和
  • （七）c52学习之旅-中断
  • （十八）devops持续集成开发——使用docker安装部署jenkins流水线服务
  • (微服务实战)预付卡平台支付交易系统卡充值业务流程设计
  • (转)MVC3 类型“System.Web.Mvc.ModelClientValidationRule”同时存在