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

链表（LinkedList）

web 2025/8/30 6:53:39

链表

链表：⼀种物理存储结构上⾮连续存储结构，数据元素的逻辑顺序是通过链表中的引⽤链接次序实现的

链表结构

LinkedList单向链表

LinkedList的创建与打印
public class MyLinkedList {static class ListNode{public int val;public ListNode next;public ListNode(int val){this.val=val;}}public ListNode head;public void creatList(){ListNode node1=new ListNode(11);ListNode node2=new ListNode(22);ListNode node3=new ListNode(33);ListNode node4=new ListNode(44);ListNode node5=new ListNode(55);node1.next=node2;node2.next=node3;node3.next=node4;node4.next=node5;this.head=node1;}public void print(){ListNode cur=head;while(cur!=null){System.out.print(cur.val+" ");cur=cur.next;}System.out.println();}
}

public class Test {public static void main(String[] args) {MyLinkedList myLinkedList=new MyLinkedList();myLinkedList.creatList();myLinkedList.print();}
}
LinkedList的头插法

public void addFirst(int data) {ListNode node=new ListNode(data);node.next=head;head=node;
}
public class Test {public static void main(String[] args) {MyLinkedList myLinkedList=new MyLinkedList();myLinkedList.addFirst(1);myLinkedList.addFirst(2);myLinkedList.addFirst(3);myLinkedList.print();}
}

LinkedList的尾插法
public void addLast(int data) {ListNode node=new ListNode(data);ListNode cur=head;if(cur==null){head=node;return;}while (cur.next!=null){cur=cur.next;}cur.next=node;
}
public class Test {public static void main(String[] args) {MyLinkedList myLinkedList=new MyLinkedList();myLinkedList.addLast(10);myLinkedList.addLast(20);myLinkedList.addLast(30);myLinkedList.print();}
}

LinkedList的指定位置插入法


public void addIndex(int index, int data) {
if(index<0||index>size()){
return ;
}
if (index==0){
addFirst(data);
return;
}
if(index==size()){
addLast(data);
return;
}
ListNode node=new ListNode(data);
ListNode cur=searchIndex(index);
if(cur==null){
return;
}
node.next=cur.next;
cur.next=node;

}
public ListNode searchIndex(int index){
if(index<0||index>size()){
return null;
}
ListNode cur=head;
int count=0;
while (count!=index-1){
cur=cur.next;
count++;
}
return cur;
}

public class Test {public static void main(String[] args) {MyLinkedList myLinkedList=new MyLinkedList();myLinkedList.creatList();myLinkedList.print();myLinkedList.addIndex(0,0);myLinkedList.addIndex(6,66);myLinkedList.print();}
}

Linked List的contains方法
public boolean contains(int key) {ListNode cur=head;while(cur!=null){if(cur.val==key){return true;}cur=cur.next;}return false;
}

public class Test {public static void main(String[] args) {MyLinkedList myLinkedList=new MyLinkedList();myLinkedList.creatList();System.out.println(myLinkedList.contains(33));System.out.println(myLinkedList.contains(66));}
}

LinkedList的删除第一次出现的key关键字

public ListNode searchIndex(int index){if(index<0||index>size()){return null;}ListNode cur=head;int count=0;while (count!=index-1){cur=cur.next;count++;}return cur;
}// 查找是否包含关键字 key 是否在单链表当中
public boolean contains(int key) {ListNode cur=head;while(cur!=null){if(cur.val==key){return true;}cur=cur.next;}return false;
}
public class Test {public static void main(String[] args) {MyLinkedList myLinkedList=new MyLinkedList();myLinkedList.addLast(10);myLinkedList.addLast(20);myLinkedList.addLast(30);myLinkedList.addLast(40);myLinkedList.print();myLinkedList.remove(30);myLinkedList.print();}
}

LinkedList的删除所有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 {prev=cur;cur=cur.next;}}if (head.val==key){head=head.next;}
}
public class Test {public static void main(String[] args) {MyLinkedList myLinkedList=new MyLinkedList();myLinkedList.addLast(10);myLinkedList.addLast(30);myLinkedList.addLast(20);myLinkedList.addLast(30);myLinkedList.addLast(40);myLinkedList.addLast(30);myLinkedList.print();myLinkedList.removeAllKey(30);myLinkedList.print();}
}

LinkedList的size()方法


public int size() {
ListNode cur=head;
int count=0;
while (cur!=null){
count++;
cur=cur.next;
}
return count;
}

public class Test {public static void main(String[] args) {MyLinkedList myLinkedList=new MyLinkedList();myLinkedList.creatList();System.out.println(myLinkedList.size());}
}

LinkedList的clear方法
public void clear() {head=null;
}

public class Test {public static void main(String[] args) {MyLinkedList myLinkedList=new MyLinkedList();myLinkedList.creatList();myLinkedList.print();myLinkedList.clear();System.out.println("clear之后：");myLinkedList.print();}
}

LinkedList的完整实现
public class MyLinkedList {static class ListNode{public int val;public ListNode next;public ListNode(int val){this.val=val;}}public ListNode head;public ListNode last;public void creatList(){ListNode node1=new ListNode(11);ListNode node2=new ListNode(22);ListNode node3=new ListNode(33);ListNode node4=new ListNode(44);ListNode node5=new ListNode(55);node1.next=node2;node2.next=node3;node3.next=node4;node4.next=node5;this.head=node1;}public void print(){ListNode cur=head;while(cur!=null){System.out.print(cur.val+" ");cur=cur.next;}System.out.println();}// 头插法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);ListNode cur=head;if(cur==null){head=node;return;}while (cur.next!=null){cur=cur.next;}cur.next=node;}// 任意位置插入，第一个数据节点为 0 号下标public void addIndex(int index, int data) {if(index<0||index>size()){return ;}if (index==0){addFirst(data);return;}if(index==size()){addLast(data);return;}ListNode node=new ListNode(data);ListNode cur=searchIndex(index);if(cur==null){return;}node.next=cur.next;cur.next=node;}public ListNode searchIndex(int index){if(index<0||index>size()){return null;}ListNode cur=head;int count=0;while (count!=index-1){cur=cur.next;count++;}return cur;}// 查找是否包含关键字 key 是否在单链表当中public boolean contains(int key) {ListNode cur=head;while(cur!=null){if(cur.val==key){return true;}cur=cur.next;}return false;}// 删除第一次出现关键字为 key 的节点public void remove(int key) {if (head==null){return;}if (head.val==key){head=head.next;return;}ListNode pre=findKey(key);if (pre==null){return;}ListNode delete=pre.next;pre.next=delete.next;}public ListNode findKey(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 {prev=cur;cur=cur.next;}}if (head.val==key){head=head.next;}}// 得到单链表的长度public int size() {ListNode cur=head;int count=0;while (cur!=null){count++;cur=cur.next;}return count;}public void clear() {head=null;}}

DoubleLinked List双向链表

Double Linked List的头插法
public void addFirst(int data) {LinkedNode node=new LinkedNode(data);if(head==null){head=node;last=node;}else {node.next=head;head.prev=node;head=node;}
}

DoubleLinkedList的尾插法
public void addLast(int data) {LinkedNode node=new LinkedNode(data);if (head==null){head=node;last=node;}else {last.next=node;node.prev=last;last=node;}
}

DoubleLinkedList的任意位置插入的方法
public void addIndex(int index, int data) {if (index<0||index>size()){System.out.println("下标位置不合法："+index);return;}if (index==0){addFirst(data);return;}if(index==size()){addLast(data);return;}LinkedNode node=new LinkedNode(data);LinkedNode cur=search(index);node.next=cur;cur.prev.next=node;node.prev=cur.prev;cur.prev=node;
}
public LinkedNode search(int index){LinkedNode cur=head;while (index!=0){cur=cur.next;index--;}return cur;
}

DoubleLinkedList删除key节点的方法 
// 删除第一次出现关键字为 key 的节点
public void remove(int key) {LinkedNode cur=head;while (cur!=null){if(cur.val == key) {if(cur == head) {//删除头节点head = head.next;if(head == null) {//只有一个节点的情况下last = null;}else {head.prev = null;}}else {//删除中间和尾巴if(cur.next == null) {//尾巴cur.prev.next = cur.next;last = last.prev;}else {cur.prev.next = cur.next;cur.next.prev = cur.prev;}}return;}cur = cur.next;}
}// 删除所有值为 key 的节点
public void removeAllKey(int key) {LinkedNode cur = head;while (cur != null) {if(cur.val == key) {if(cur == head) {//删除头节点head = head.next;if(head == null) {//只有一个节点的情况下last = null;}else {head.prev = null;}}else {//删除中间和尾巴if(cur.next == null) {//尾巴cur.prev.next = cur.next;last = last.prev;}else {cur.prev.next = cur.next;cur.next.prev = cur.prev;}}}cur = cur.next;}
}

DoubleLinkedList的contains（）方法

public boolean contains(int key) {
LinkedNode cur=head;
while (cur!=null){
if (cur.val==key){
return true;
}
cur=cur.next;
}
return false;
}
Double Linked List的size（）方法
public int size() {LinkedNode cur=head;int count=0;while (cur!=null){count++;cur=cur.next;}return count;
}
Double Linked List的display()方法
public void display() {LinkedNode cur=head;while (cur!=null){System.out.print(cur.val+" ");cur=cur.next;}System.out.println();
}
DoubleLinkedList的clear()方法
public void clear() {LinkedNode cur = head;while (cur != null) {LinkedNode curN = cur.next;cur.prev = null;cur.next = null;cur = curN;}head = null;last = null;
}

DoubleLinkedList的完整实现
public class DoubleLinkedList {static class LinkedNode{public int val;public LinkedNode next;public LinkedNode prev;public LinkedNode(int val){this.val=val;}}public LinkedNode head;public LinkedNode last;public void addFirst(int data) {LinkedNode node=new LinkedNode(data);if(head==null){head=node;last=node;}else {node.next=head;head.prev=node;head=node;}}// 尾插法public void addLast(int data) {LinkedNode node=new LinkedNode(data);if (head==null){head=node;last=node;}else {last.next=node;node.prev=last;last=node;}}// 任意位置插入，第一个数据节点为 0 号下标public void addIndex(int index, int data) {if (index<0||index>size()){System.out.println("下标位置不合法："+index);return;}if (index==0){addFirst(data);return;}if(index==size()){addLast(data);return;}LinkedNode node=new LinkedNode(data);LinkedNode cur=search(index);node.next=cur;cur.prev.next=node;node.prev=cur.prev;cur.prev=node;}public LinkedNode search(int index){LinkedNode cur=head;while (index!=0){cur=cur.next;index--;}return cur;}// 查找是否包含关键字 key 是否在单链表当中public boolean contains(int key) {LinkedNode cur=head;while (cur!=null){if (cur.val==key){return true;}cur=cur.next;}return false;}// 删除第一次出现关键字为 key 的节点public void remove(int key) {LinkedNode cur=head;while (cur!=null){if(cur.val == key) {if(cur == head) {//删除头节点head = head.next;if(head == null) {//只有一个节点的情况下last = null;}else {head.prev = null;}}else {//删除中间和尾巴if(cur.next == null) {//尾巴cur.prev.next = cur.next;last = last.prev;}else {cur.prev.next = cur.next;cur.next.prev = cur.prev;}}return;}cur = cur.next;}}// 删除所有值为 key 的节点public void removeAllKey(int key) {LinkedNode cur = head;while (cur != null) {if(cur.val == key) {if(cur == head) {//删除头节点head = head.next;if(head == null) {//只有一个节点的情况下last = null;}else {head.prev = null;}}else {//删除中间和尾巴if(cur.next == null) {//尾巴cur.prev.next = cur.next;last = last.prev;}else {cur.prev.next = cur.next;cur.next.prev = cur.prev;}}}cur = cur.next;}}// 得到单链表的长度public int size() {LinkedNode cur=head;int count=0;while (cur!=null){count++;cur=cur.next;}return count;}// 遍历显示链表元素（假设功能），实际可根据需求定义public void display() {LinkedNode cur=head;while (cur!=null){System.out.print(cur.val+" ");cur=cur.next;}System.out.println();}// 清空链表public void clear() {LinkedNode cur = head;while (cur != null) {LinkedNode curN = cur.next;//cur.val = null;cur.prev = null;cur.next = null;cur = curN;}head = null;last = null;}
}

Linked List的使用

【说明】

1. LinkedList实现了List接⼝

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

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

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

5. LinkedList⽐较适合任意位置插⼊的场景

LinkedList的常用方法
import java.util.LinkedList;public class Test {public static void main(String[] args) {LinkedList<Integer> linkedList=new LinkedList<>();LinkedList<Integer> linkedList1=new LinkedList<>();linkedList1.add(55);linkedList1.add(66);//尾插linkedList.add(11);linkedList.add(22);linkedList.add(33);System.out.println(linkedList);//元素插入index位置linkedList.add(0,0);linkedList.add(4,44);System.out.println(linkedList);//插入其他链表的元素linkedList.addAll(linkedList1);System.out.println(linkedList);//删除元素linkedList.remove(0);linkedList.remove(4);System.out.println(linkedList);//获取下标元素System.out.println(linkedList.get(3));//设置index元素linkedList.set(1,111);System.out.println(linkedList);//判断元素是否存在System.out.println(linkedList.contains(44));System.out.println(linkedList.contains(22));//返回下标System.out.println(linkedList.indexOf(55));System.out.println(linkedList.lastIndexOf(111));//截取System.out.println(linkedList.subList(0, 4));//清空System.out.println(linkedList);linkedList.clear();System.out.println(linkedList);}
}

Linked List的遍历
import java.util.LinkedList;
import java.util.ListIterator;
public class Test {public static void main(String[] args) {LinkedList<Integer> linkedList=new LinkedList<>();linkedList.add(1);linkedList.add(2);linkedList.add(3);//直接遍历System.out.println(linkedList);//for循环遍历for (int i = 0; i <linkedList.size() ; i++) {System.out.print(linkedList.get(i)+" ");}System.out.println();//foreach遍历for (int i:linkedList) {System.out.print(i+" ");}System.out.println();//迭代器遍历ListIterator<Integer> iterator=linkedList.listIterator();while (iterator.hasNext()){System.out.print(iterator.next()+" ");}System.out.println();ListIterator<Integer> iterator1=linkedList.listIterator(linkedList.size());while (iterator1.hasPrevious()){System.out.print(iterator1.previous()+" ");}System.out.println();}

http://www.xdnf.cn/news/19187.html

相关文章：

  • docker compose设置命令别名的方法
  • Swift 解法详解：LeetCode 366《寻找二叉树的叶子节点》
  • 贪心算法面试常见问题分类解析
  • 微服务入门指南（一）：从单体架构到服务注册发现
  • PPT处理控件Aspose.Slides教程：使用 C# 编程将 PPTX 转换为 XML
  • Pytorch超分辨率模型实现与详细解释
  • CRYPT32!CryptMsgUpdate函数分析和asn.1 editor nt5inf.cat 的总览信息
  • 机器学习回顾——逻辑回归
  • Consul 操作命令汇总 - Prometheus服务注册
  • 计算机视觉与深度学习 ｜ 视觉里程计技术全景解析：从原理到前沿应用
  • 2024年09月 Python（四级）真题解析#中国电子学会#全国青少年软件编程等级考试
  • 项目一系列-第8章 性能优化Redis基础
  • 星链调查（SOS）线上问卷调查：全流程标准化实践与核心优势深挖
  • 第三届机械工程与先进制造智能化技术研讨会（MEAMIT2025）
  • 【NJU-OS-JYY笔记】操作系统：设计与实现
  • 锂电池充电芯片 XSP30支持PD/QC等多种快充协议支持最大充电电流2A
  • Origin绘制四元相图
  • [Linux]学习笔记系列 -- mm/shrinker.c 内核缓存收缩器(Kernel Cache Shrinker) 响应内存压力的回调机制
  • 深入解析PCIe 6.0拓扑架构：从根复合体到端点的完整连接体系
  • 宜春城区光纤铺设及接口实地调研
  • C5仅支持20MHZ带宽，如果路由器5Gwifi处于40MHZ带宽信道时，会出现配网失败
  • Pytest 插件方法：pytest_runtest_makereport
  • Stream API 讲解
  • Day17_【机器学习—在线数据集 鸢尾花案例】
  • 宜春城区SDH网图分析
  • 漫谈《数字图像处理》之浅析图割分割
  • 从9.4%到13.5%：ICDM2025录取率触底反弹，竞争压力稍缓
  • 新工具-mybatis-flex学习及应用
  • 大模型应用开发笔记（了解篇）
  • 使用 Bright Data Web Scraper API + Python 高效抓取 Glassdoor 数据：从配置到结构化输出全流程实战