Java语言之LinkedList和链表的实现方法
作者:tq02 时间:2023-12-19 20:18:59
一.链表概念
链表是一种物理存储结构上非连续存储结构,数据元素的逻辑顺序是通过链表中的引用链接次序实现的 。
逻辑结构:
注:1、如上图,相当于火车车厢,每一节都相连在一起。
2、各个结点连接的方式:通过地址连接,在内存当中,相邻结点在内存中不一定相邻。
3、所有结点都在 堆 中申请出来。
4、 每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域。
二.链表的分类
1.单向、双向链表
注:无论单向还是双向,都是一个结点存储着下(上)一个结点。
2.带头、不带头结点 链表
注:无头和带头结点的主要区别:有一个起始结点。
3.循环、非循环链表
循环链表,就是指:头、尾结点有联系。
在链表结构中,这是主要的链表,但是这些链表种类还可以结合,如:带头双向循环链表、双向循环链表等等。
链表的种类很多,但都大同小异,我们主要学习两种链表:
1、无头单向非循环链表:结构简单,一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构,如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
2、无头双向链表:在Java的集合框架库中LinkedList底层实现就是无头双向循环链表
三.无头单向非循环链表的实现
3.1创建简单链表
重点:每个结点存储着下一个结点的地址。
创建链表代码实现:
public class SingleLinkedList {
static class List{
int item; //存储数据
List next; //指向下一个结点
public List(int item) {
this.item = item;
}
public List() {};
}
//各种链表实现方法
//头插法
public void addFirst(int data){
}
//尾插法
public void addLast(int data){
}
//任意位置插入,第一个数据节点为0号下标
public void addIndex(int index,int data){
}
//查找是否包含关键字key是否在单链表当中
public boolean contains(int key){
return false;
}
//删除第一次出现关键字为key的节点
public void remove(int key){
}
//得到单链表的长度
public int size(){
return -1;
}
//链表的清空
public void clear() {
}
//展示链表
public void display() {}
3.2 链表基本方法实现
1.遍历链表元素
public void show() {
//这里不是定义了一个节点 这里只是一个引用
ListNode cur = head;
while (cur != null) {
System.out.print(cur.val+" ");
cur = cur.next;
}
System.out.println();
}
2.获取链表长度
public int size(){
int count = 0;
ListNode cur = head;
while (cur != null) {
count++;
cur = cur.next;
}
return count;
}
3.查询数据
public boolean contains(int key){
ListNode cur = head;
while (cur != null) {
//如果val值 是引用类型 那么这里得用equals来进行比较!!!
if(cur.val == key) {
return true;
}
cur = cur.next;
}
return false;
}
4.链表的清空
public void clear() {
//将所有结点都置空,更为安全
while (head != null) {
ListNode headNext = head.next;
head.next = null;
head = headNext;
}
}
3.3四大基本功能
3.3.1 、增加元素结点
1.头插法:将新增结点放在链表的头部。
public void addFirst(int data){
ListNode node = new ListNode(data);
node.next = head;
head = node;
}
2.尾插法:将新增结点直接连接在链表的尾部
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 指向的节点就是尾巴节点
cur.next = node;
}
3.选择下标值,添加结点
public void addIndex(int index,int data){
int len = size();
//0、判断index位置的合法性
if(index < 0 || index > len) {
throw new IndexOutOfBounds("任意位置插入数据的时候,index位置不合法: "+index);
}
if(index == 0) {
addFirst(data);
return;
}
if(index == len) {
addLast(data);
return;
}
//1、先找到index-1位置的节点
ListNode cur = findIndex(index);
//2、进行插入
ListNode node = new ListNode(data);
node.next = cur.next;
cur.next = node;
}
3.3.2.查找元素结点
查找一个元素,返回对应的下标值。
public ListNode findIndex(int index) {
ListNode cur = head;
while (index - 1 != 0) {
cur = cur.next;
index--;
}
return cur;//index-1位置的节点
}
3.3.3.删除元素结点
先找到对应的下标值,然后进行删除。删除方法,前一个结点连接到删除结点的后一个结点。
如图,先断开d2与d3的连接,然后d2直接连接d4
代码实现:
//删除第一次出现关键字为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;
}
private ListNode searchPrev(int key) {
ListNode prev = head;
while (prev.next != null) {
if(prev.next.val == key) {
return prev;
}else {
prev = prev.next;
}
}
return null;
}
3.3.4.结点信息修改
修改指定下标值的结点元素
public void searchPrev(int num,int date) {
ListNode prev = head;
for(int i=0;i<num-1;i++) {
prev = prev.next;
}
prev.val=date;
}
四.LinkedList是什么?
LinkedList的底层是双向链表结构,由于链表没有将元素存储在连续的空间中,元素存储在单独的节点中,然后通过引用将节点连接起来了,因此在在任意位置插入或者删除元素时,不需要搬移元素,效率比较高。
如图所示:1. LinkedList实现了List接口
2. LinkedList的底层使用了双向链表
3. LinkedList没有实现RandomAccess接口,因此LinkedList不支持随机访问。
4. LinkedList的任意位置插入和删除元素时效率比较高,时间复杂度为O(1)
5. LinkedList比较适合任意位置插入的场景
五.LinkedList使用方法
方法 | 解释 | |
构造方法 | LinkedList() | 无参构造 |
public LinkedList(Collection<? extends E> c) | 使用其他集合容器中元素构造List | |
常用方法 | boolean add(E e) | 尾插e |
void add(int index,E element) | 将e插入到index位置 | |
boolean addAII(Collection<? extends E> c) | 尾插c中的元素 | |
E remove(int index) | 删除index位置元素 | |
boolean remove(Object o) | 删除遇到的第一个o | |
E get( int index) | 获取下标index位置元素 | |
void clear() | 清空 |
来源:https://blog.csdn.net/m0_74097410/article/details/130320166
![](/images/zang.png)
![](/images/jiucuo.png)
猜你喜欢
idea全局搜索快捷键超详细总结(推荐!)
![](https://img.aspxhome.com/file/2023/5/62705_0s.png)
C#单例模式(Singleton Pattern)实例教程
Android View如何测量
![](https://img.aspxhome.com/file/2023/7/138567_0s.jpg)
Java编写Mapreduce程序过程浅析
![](https://img.aspxhome.com/file/2023/5/67455_0s.png)
C#四舍五入用法实例
关于springboot2整合lettuce启动卡住问题的解决方法
详解java中BigDecimal精度问题
![](https://img.aspxhome.com/file/2023/9/64039_0s.jpg)
Android绘制机器人小实例
![](https://img.aspxhome.com/file/2023/8/138798_0s.jpg)
Java实现评论回复功能的完整步骤
![](https://img.aspxhome.com/file/2023/2/97942_0s.png)
Unity3D实现攻击范围检测
如何动态替换Spring容器中的Bean
Java 二分查找算法的实现
Android运用BroadcastReceiver实现强制下线
![](https://img.aspxhome.com/file/2023/0/138300_0s.png)
rxjava+retrofit实现多图上传实例代码
jstorm源码解析之bolt异常处理方法
如何把spring boot项目部署到tomcat容器中
java图片验证码生成教程详解
![](https://img.aspxhome.com/file/2023/7/60987_0s.jpg)
android自定义View实现圆环颜色选择器
![](https://img.aspxhome.com/file/2023/8/125348_0s.gif)
浅析Spring工厂的反射和配置文件
![](https://img.aspxhome.com/file/2023/4/77964_0s.jpg)