目录
一.链表概念
二.链表的分类
三.无头单向非循环链表的实现
3.1创建简单链表
3.2 链表基本方法实现
3.3四大基本功能
3.3.1.增加元素结点
3.3.2.查找元素结点
3.3.3.删除元素结点
3.3.4.结点信息修改
四.LinkedList是什么?
五.LinkedList使用方法
总结
😽个人主页: tq02的博客_CSDN博客-C语言,Java,Java数据结构领域博主
🌈梦的目标:努力学习,向Java进发,拼搏一切,让自己的未来不会有遗憾。
🎁欢迎各位→点赞👍 + 收藏⭐ + 评论📝+关注✨
本章讲解内容:链表 的讲解
使用编译器:IDEA
一.链表概念
链表是一种物理存储结构上非连续存储结构,数据元素的逻辑顺序是通过链表中的引用链接次序实现的 。
逻辑结构:
注: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() | 清空 |
总结
链表入门很简单,但是却有很多很难的题目,而我们只有将这些题目全部掌握了,对之后的栈、堆等题有更加深刻的知识。
题目推荐:1、移除链表元素 2、反转单链表 3、返回链表中间节点 文章来源:https://www.toymoban.com/news/detail-433527.html
4、 合并两个有序链表 5、 合并两个有序链表 6. 相交链表 7、回文链表文章来源地址https://www.toymoban.com/news/detail-433527.html
到了这里,关于Java语言----LinkedList 和 链表的实现的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!