《Java初阶数据结构》----3.＜线性表---LinkedList与链表＞
目录
前言
大家好，我目前在学习java。之前也学了一段时间，但是没有发布博客。时间过的真的很快。我会利用好这个暑假，来复习之前学过的内容，并整理好之前写过的博客进行发布。如果博客中有错误或者没有读懂的地方。热烈欢迎大家在评论区进行讨论！！！
喜欢我文章的兄弟姐妹们可以点赞，收藏和评论我的文章。喜欢我的兄弟姐妹们以及也想复习一遍java知识的兄弟姐妹们可以关注我呦，我会持续更新滴，
望支持！！！！！！一起加油呀！！！！
语言只是工具，不能决定你好不好找工作，决定你好不好找工作的是你的能力！！！！！
学历本科及以上就够用了！！！！！！！！！！！！！！！！！！
本篇博客主要讲解Java基础语法中的
一、链表的简介
1.1链表的概念
1.2链表的八种结构
重点掌握两种结构：
1.3单链表的常见方法
三、单链表的模拟实现
四、LinkedList的模拟实现（双链表）
4.1 什么是LinkedList
4.2LinkedList的使用（及实现）
五、ArrayList和LinkedList的区别
一、链表的简介
1.1链表的概念
链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的 。
1.2链表的八种结构
下面三种情况组合起来就有八种2^3。
1. 单向或者双向
2.带头或者不带头
3. 循环或者非循环
重点掌握两种
1.无头单向非循环链表（单链表）：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
2.无头双向链表（双链表）：在Java的集合框架库中LinkedList底层实现就是无头双向循环链表。
1.3单链表的常见方法
// 1、无头单向非循环链表实现
public class SingleLinkedList {
//头插法
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){
}
//删除所有值为key的节点
public void removeAllKey(int key){
}
//得到单链表的长度
public int size(){
return -1;
}
public void clear() {
}
public void display() {}
}三、单链表的模拟实现
用内部类的方式定义链表节点。
//链表是由每一个节点组成的，每一个节点都是一个对象，
// 如果我们去抽象他，它有两个域，节点是链表的一部分，所以我们把节点定义成内部类
static class ListNode{
public int val;//节点的值域，整型
public ListNode next;//下一个节点的地址，要表示节点的地址，因此是ListNode类型
//由于new新的节点对象时，值可以知道，但是下一个节点的地址是未知的
//因此我们创建构造方法时，只初始化val的值，next的值默认为null。
public ListNode(int val) {
this.val = val;
}
}再定义一个头结点
//对于链表本身，还应该有个head，来表示当前链表的头结点，这是我们链表的头结点
//而不是节点的头结点。因此是链表的属性，切勿放到节点类之中。节点类只有两个属性，值域和下一个节点的地址域
//要表示节点的地址，因此是ListNode类型
public ListNode head;简单的初始化链表
public void easyCreateList(){
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;
}遍历打印链表
//注意：head必须一直指向第一个节点的位置，从而来找到这个链表
//因此我们定义一个ListNode类型的cur。
public void display(){
ListNode cur = head;
if (cur == null){
System.out.print("当前链表为空，无法打印");
}
while (cur != null){
System.out.printf(cur.val+" ");
cur = cur.next;
}
System.out.println();
}从某节点开始打印链表
public void display(ListNode listNode){
ListNode cur = listNode;
if (cur == null){
System.out.print("当前链表为空，无法打印");
}
while (cur != null){
System.out.printf(cur.val+" ");
cur = cur.next;
}
System.out.println();
}求链表的长度
//求链表的长度
public int size(){
int count = 0;
ListNode cur = head;
while (cur != null){
count++;
cur = cur.next;
}
return count;
}是否链表是否包含关键字key
//是否链表是否包含关键字key
public boolean contains(int key){
ListNode cur = head;
while (cur != null){
if(key == cur.val){
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);
ListNode cur = head;
if (cur == null){
head = node;
return;
}
//找到链表的尾节点
while (cur.next != null){
cur = cur.next;
}
cur.next = node;
}在指定位置插入元素
//在指定位置插入元素
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;
}
// ListNode node = new ListNode(data);
// ListNode pre = head;
// int count = 0;
// while (true){
// pre = pre.next;
// count++;
// if (index == count+1){
// node.next = pre.next;
// pre.next = node;
// break;
// }
// }
ListNode cur = findIndexSubOne(index);
ListNode node = new ListNode(data);
node.next = cur.next;
cur.next = node;
}找到要删除节点的位置的前一个节点
//找到要删除节点的位置的前一个节点
private ListNode findIndexSubOne(int index){
ListNode cur = head;
for (int i = 0; i<index-1; i++){
cur = cur.next;
}
return cur;
// while (index-1 != 0){
// cur = cur.next;
// index--;
// }
// return cur;
}删除第一次出现关键字为key的节点
//删除第一次出现关键字为key的节点
public void remove(int key){
if(head == null){
System.out.println("当前链表为空，您要删除的数据不存在");
return;
}
if (head.val == key){
head = head.next;
return;
}
ListNode cur = searchPrev(key);
if (cur == null){
System.out.println("没有找到你要删除的数字");
return;
}
cur.next = cur.next.next;
}找到key的前驱
//找到key的前驱
private ListNode searchPrev(int key){
ListNode cur = head;
while (cur.next!=null){
if (cur.next.val == key){
return cur;
}
cur = cur.next;
}
return null;
}删除链表中元素
public void removeAllKey(int key){
if(head == null){
System.out.println("当前链表为空，无法删除！");
return;
}
ListNode cur = head.next;
ListNode prev = head;
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 ListNode reverseList(ListNode head){
if(head == null){
return null;
}
if(head.next == null){
return head;
}
ListNode cur = head.next;
head.next = null;
while (cur != null){
ListNode curNext = cur.next;
cur.next = head;
head = cur;
cur = curNext;
}
return head;
} public void reverseList(){
if(head == null){
return;
}
if(head.next == null){
return;
}
ListNode cur = head.next;
head.next = null;
while (cur != null){
ListNode curNext = cur.next;
cur.next = head;
head = cur;
cur = curNext;
}
}用栈的方式逆序打印链表
//用栈的方式逆序打印链表
public void reverseStackList(){
Stack<ListNode> stack = new Stack<>();
ListNode cur = head;
while (cur != null){
stack.push(cur);
cur=cur.next;
}
while (!stack.isEmpty()){
ListNode top = stack.pop();
System.out.print(top.val+" ");
}
System.out.println();
}暴力清空链表
public void clear(){
this.head = null;
}四、LinkedList的模拟实现（双链表）
4.1 什么是LinkedList
LinkedList：的底层是双向链表结构，由于链表没有将元素存储在连续的空间中，元素存储在单独的节 点中，然后通过引用将节点连接起来了，因此在在任意位置插入或者删除元素时，不需要搬移元素，效率比较高。
在集合框架中，LinkedList也实现了List接口，具体如下：
说明
1. LinkedList实现了List接口
2. LinkedList的底层使用了双向链表
3. LinkedList没有实现RandomAccess接口，因此LinkedList不支持随机访问
4. LinkedList的任意位置插入和删除元素时效率比较高，时间复杂度为O(1)
5. LinkedList比较适合任意位置插入的场景
4.2LinkedList的使用（及实现）
1. LinkedList的构造
2. LinkedList的其他常用方法介绍
3.方法的具体实现
使用内部类构造双链表的节点，头节点，尾结点
static class ListNode{
private int val;//链表值域
private ListNode prev;//前节点地址
private ListNode next;//后节点地址
//构造方法，初始化链表节点值域
public ListNode(int val) {
this.val = val;
}
}
public ListNode head; //双向链表的头结点
public ListNode last;//双向链表的尾巴头插法
//头插法
public void addFirst(int data){
ListNode node = new ListNode(data);
if (head == null){
head = node;
last = node;
return;
}
head.prev =node;
node.next = head;
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;
}链表长度
//链表长度
public int size(){
int count = 0;
ListNode cur = head;
while (cur != null){
cur = cur.next;
count++;
}
return count;
}打印链表
//打印链表
public void display(){
ListNode cur = head;
if (cur == null){
System.out.println("该链表为空，无法打印！");
return;
}
while (cur != null){
System.out.print(cur.val+" ");
cur = cur.next;
}
System.out.println();//方便测试看数据
}链表是否包含某元素
//链表是否包含某元素
public boolean contains(int key){
ListNode cur = head;
if (cur == null){
System.out.println("该链表为空!");
return false;
}
while (cur != null){
if(cur.val == key){
return true;
}
cur = cur.next;
}
return false;
}检查下标是否异常
//检查下标是否异常
public void checkIndex(int index){
if (index<0 || index >size()){//等于size用尾插法
throw new indexOutOfException("index 不合法！"+index);
}
}在某位置添加元素
public void addIndex(int index, int data) {
checkIndex(index);
if (index == 0) {
addFirst(data);
return;
}
if(index == size()) {
addLast(data);
return;
}
ListNode node = new ListNode(data);
// while (index !=0){
// cur = cur.next;
// index--;
// }
ListNode cur = searchIndexNode(index);
node.prev=cur.prev;
node.next=cur;
cur.prev.next = node;
cur.prev = node;
}找到第n个节点的位置
//双链表，由于知道了前一个节点的位置
//因此插进第n个元素时直接找到第n个节点的位置就可以
private ListNode searchIndexNode(int index){
ListNode cur =head;
while (index !=0){
cur = cur.next;
index--;
}
return cur;
}删除第一个出现的某元素
删除链表中所有这个元素
后续会添加完整的代码
五、ArrayList和LinkedList的区别
原文地址：https://blog.csdn.net/m0_73456341/article/details/140646896
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！