Java中的链表
发布时间：2023年12月18日
文章目录
前言
在前面我们已经学习了关于顺序表ArrayList的一些基本操作。通过源码知道，ArrayList底层使用数组来存储元素，由于其底层是一段连续空间，当在ArrayList任意位置插入或者删除元素时，就需要将后序元素整体往前或者往后搬移，时间复杂度为O(n)，效率比较低，因此ArrayList不适合做任意位置插入和删除比较多的场景。因此：java集合中又引入了LinkedList，即链表结构
一、链表的概念及结构
链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的
注意：
1.链式结构在逻辑上是连续的，但是在物理上不一定连续
2.现实中的结点一般都是从堆上申请出来的
3.从堆上申请的空间，是按照一定的策略来分配的，两次申请的空间可能是连续，也可能不连续
链表的结构有8种样式：
单向带头循坏、单向带头非循坏、单向不带头循坏、单向不带头非循坏
双向带头循坏、双向带头非循坏、双向不带头循坏、双向不带头非循坏
这里我们主要学习以下两中结构：
单向不带头非循坏
LinkedList底层使用的就是双向不带头非循坏
二、单向不带头非循坏链表的实现
创建一个类：
public class MySingleList {
static class ListNode {
public int val;
public ListNode next;
public ListNode(int val) {
this.val = val;
}
}
//链表的头节点
public ListNode head;
}
2.1打印链表
不带参数的打印
public void display() {
ListNode cur = head;
if(cur != null) {//遍历完所以节点
System.out.print(cur.val+" ");
cur = cur.next;
}
System.out.println();
}
带参数的打印
public void display(ListNode newHead) {
ListNode cur = newHead;
if(cur != null) {
System.out.print(cur.val+" ");
cur = cur.next;
}
System.out.println();
}
2.2求链表的长度
public int size(){
ListNode cur = head;
int count = 0;
while (cur != null) {
count++;
cur = cur.next;
}
return count;
}
2.3头插法
public void addFirst(int data){
ListNode node = new ListNode(data);
node.next = head;
head = node;
}
2.4尾插法
public void addLast(int data){
ListNode node = new ListNode(data);
if(head == null) {
head = node;
}else {
ListNode cur = head;
while (cur.next != null) {//走到最后一个节点的位置
cur = cur.next;
}
cur.next = node;
}
}
2.5任意位置插入
在任意位置插入时我们要判断该位置是否合法，不合法的时候要抛一个异常
public void addIndex(int index,int data){
if(index < 0 || index > size()) {
throw new IndexException("index位置不合法："+index);
}
ListNode node = new ListNode(data);
if(head == null) {
head = node;
return;
}
if(index == 0) {
addFirst(data);
return;
}
if(index == size()) {
addLast(data);
return;
}
//中间插入
ListNode cur = serchIndex(index);
node.next = cur.next;
cur.next = node;
}
找要添加节点位置的前一个节点
public ListNode serchIndex(int index) {
ListNode cur = head;
int count = 0;
while (count != index-1) {
cur = cur.next;
count++;
}
return cur;
}
2.6查找是否包含某个元素的节点
遍历这个链表找是否与这个元素相同
public boolean contains(int key){
ListNode cur = head;
while (cur != null) {
if(cur.val == key) {
return true;
}
cur = cur.next;
}
return false;
}
2.7删除第一次出现这个元素的节点
public void remove(int key){
if(head == null) {
return;
}
if(head.val == key) {
head = head.next;
return;
}
ListNode cur = findKey(key);
if(cur == null) {
return;//没有要删除的元素
}
ListNode del = cur.next;
cur.next = del.next;
}
要删除节点的前一个节点
public ListNode findKey(int key) {
ListNode cur = head;
while (cur.next != null) {
if(cur.next.val == key) {
return cur;
}else {
cur = cur.next;
}
}
return null;
}
2.8删除包含这个元素的所以节点
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 {
prev = cur;
cur = cur.next;
}
}
//除了头节点外，其余都删完了
if(head.val == key) {
head = head.next;
}
}
2.9清空链表
清空链表只需要把头节点置为空
public void clear() {
head = null;
}
单向链表的测试
public class Test {
public static void main(String[] args) {
MySingleList list = new MySingleList();
list.addLast(30);//尾插
list.addLast(20);
list.addLast(30);
list.addLast(40);
list.addLast(50);
list.addFirst(100);//头插
list.addIndex(2,15);//任意位置插入
list.display();
System.out.println("*****");
System.out.println(list.contains(20));//查看是否包含某个节点
System.out.println("*****");
System.out.println(list.size());//求链表长度
System.out.println("*****");
list.remove(30);//删除第一个出现的节点
list.display();
list.removeAllKey(30);//删除包含这个元素的所以节点
System.out.println("*****");
list.display();
System.out.println("*****");
list.clear();//清空链表
list.display();
}
}
三、双向不带头非循坏链表的实现
创建一个类：
static class ListNode {
public int val;
public ListNode next;
public ListNode prev;
public ListNode(int val) {
this.val = val;
}
}
public ListNode head;
public ListNode last;
}
3.1打印双向链表
public void display(){
ListNode cur = head;
while (cur != null) {
System.out.print(cur.val+" ");
cur = cur.next;
}
System.out.println();
}
3.2求双向链表的长度
public int size(){
int count = 0;
ListNode cur = head;
while (cur != null) {
count++;
cur = cur.next;
}
return count;
}
3.3头插法
public void addFist(int data) {
ListNode node = new ListNode(data);
if(head == null) {//一个节点都没有的情况
head = node;
last = node;
}else {
node.next = head;
head.prev = node;
head = node;
}
}
3.4尾插法
public void addLast(int data) {
ListNode node = new ListNode(data);
if(head == null) {//一个节点都没有的情况
head = node;
last = node;
}else {
last.next = node;
node.prev = last;
last = node;
}
}
3.5任意位置插入
这里的插入与单向链表一样也需要判断该位置的合法性，不合法时抛一个异常
public void addIndex(int index,int data) {
if(index < 0 || index > size()) {
throw new IndexException("双向链表中index的位置不合法："+index);
}
if(index == 0) {
addFist(data);
}
if(index == size()) {
addLast(data);
}
ListNode cur = findIndex(index);
ListNode node = new ListNode(data);
node.next = cur;
cur.prev.next = node;
node.prev = cur.prev;
cur.prev = node;
}
要添加节点的位置
public ListNode findIndex(int index) {
ListNode cur = head;
if(index != 0) {
cur = cur.next;
index --;
}
return cur;
}
3.6查找是否包含某个元素的节点
public boolean contains(int key){
ListNode cur = head;
while (cur != null) {
if(cur.val == key) {
return true;
}
cur = cur.next;
}
return false;
}
3.7删除第一次出现这个元素的节点
因为数据结构是一门逻辑性非常严谨的学科，所以这里的删除需要考虑多种因素
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;
}
}else {
//删除中间节点
if(cur.next != null) {
cur.next.prev = cur.prev;
cur.prev.next = cur.next;
}else {
//删除尾巴节点
cur.prev.next = cur.next;
last = last.prev;
}
}
return;
}
cur = cur.next;
}
}
3.7删除包含这个元素的所有节点
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;
}
}else {
//删除中间节点
if(cur.next != null) {
cur.next.prev = cur.prev;
cur.prev.next = cur.next;
}else {
//删除尾巴节点
cur.prev.next = cur.next;
last = last.prev;
}
}
}
cur = cur.next;
}
}
3.9清空双向链表
public void clear(){
ListNode cur = head;
while (cur != null) {
ListNode curNext = cur.next;
cur.prev = null;
cur.next = null;
cur = cur.next;
}
head = null;//头节点置空
last = null;//尾巴节点置空
}
双向链表的测试
public class Test {
public static void main(String[] args) {
MyLinkedList myLinkedList = new MyLinkedList();
myLinkedList.addLast(12);//尾插法
myLinkedList.addLast(45);
myLinkedList.addLast(34);
myLinkedList.addLast(45);
myLinkedList.addFist(56);//头插法
myLinkedList.addIndex(2,15);//任意位置插入
myLinkedList.display();
System.out.println(myLinkedList.size());//求双向链表的长度
System.out.println("******");
System.out.println(myLinkedList.contains(23));//查找是否包含某个元素的节点
System.out.println("******");
myLinkedList.remove(45);//删除第一次出现这个元素的节点
myLinkedList.display();
System.out.println("******");
myLinkedList.removeAllKey(45);//删除包含这个元素的所以节点
myLinkedList.display();
System.out.println("******");
myLinkedList.clear();//清空链表
myLinkedList.display();
}
}
LinkedList的遍历方式
关于LinkedList的遍历方式有四种：
public class Test {
public static void main(String[] args) {
LinkedList<Integer> list = new LinkedList<>();
list.add(1);
list.add(2);
list.add(3);
list.add(4);
System.out.println(list);
//for循坏遍历
for (int i = 0; i < list.size(); i++) {
System.out.print(list.get(i)+" ");
}
System.out.println();
System.out.println("*******");
//foreach遍历
for (int m : list) {
System.out.print(m +" ");
}
System.out.println();
System.out.println("*******");
//使用迭代器——正向遍历
ListIterator<Integer> it = list.listIterator();
while (it.hasNext()) {
System.out.print(it.next()+" ");
}
System.out.println();
System.out.println("*******");
//使用迭代器——反向遍历
ListIterator<Integer> it2 = list.listIterator(list.size());
while (it2.hasPrevious()) {
System.out.print(it2.previous()+" ");
}
System.out.println();
}
}
四、ArrayList和LinkedList的区别
1.ArrayList在物理上是连续的，LinkedList在逻辑上连续，但在物理上不一定连续
2.ArrayList和LinkedList是两种不同的数据结构。ArrayList是基于动态数组的，而LinkedList则是基于链表的
3.当需要随机访问元素（如get和set操作）时，ArrayList效率更高，因为LinkedList需要逐个查找。但当进行数据的增加和删除操作（如add和remove操作）时，LinkedList效率更高，因为ArrayList在进行这些操作时需要移动大量数据
4.ArrayList需要手动设置固定大小的容量，使用方便但自由性低；而LinkedList能够随数据量变化而动态调整，自由性较高但使用较为复杂
文章来源:https://blog.csdn.net/2301_78373304/article/details/134963559
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：chenni525@qq.com进行投诉反馈，一经查实，立即删除！
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：chenni525@qq.com进行投诉反馈，一经查实，立即删除！
最新文章
- Python教程
- 深入理解 MySQL 中的 HAVING 关键字和聚合函数
- Qt之QChar编码（1）
- MyBatis入门基础篇
- 用Python脚本实现FFmpeg批量转换
- Springboot+vue的公寓报修管理系统（有报告）。Javaee项目，springboot vue前后端分离项目
- 基于Java8构建Docke镜像
- ERP库存管理系统的核心价值：优化企业供应链与库存智能控制-亿发
- AIGC之什么是AIGC
- uni-app做A-Z排序通讯录、索引列表
- 5G应用逐浪数字化之巅， 开创高质量发展新局面！
- [计网00] 计算机网络开篇导论
- C#基础——ArrayList动态数组
- 半导体：Gem/Secs基本协议库的开发（2）
- 自学黑客（网络安全）技术——高效学习