【java数据结构】链表
此篇博客希望对你有所帮助（帮助里了解链表（单链表和双向链表），java集合框架中，实现List接口，LinkedList类），不懂的或有错误的也可在评论区留言，错误必改评论必回！！！持续关注，下一篇博客是链表的例题，相信例题可以帮你更加清晰准确理解链表！！！
一、引出链表
1.1 ArrayLIst存在的缺陷
1.ArrayLIst 底层使用连续的空间，任意位置插入或删除元素时，需要将该位置后序元素整体往前或往后挪动，故时间复杂度为O（n）;
2.增容需要申请空间，拷贝数据，释放旧空间，会有不小的消耗；
3.增容一般呈2倍增长，势必会有一定的空间浪费。例如当容量为100，瞒不了以后增容到200，我们再继续插入5个数据，后面没有数据插入了，那么就浪费了95个空间。
因此Java集合框架有引入了LinkedList，即链表结构。
1.2 链表
1.2.1 链表的概念以及结构
链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的引用链表次序实现的。
链表由一系列节点（链表中每一个元素称为节点）组成，节点可以在运行时动态生成。每个节点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个节点地址的指针域。
实例：
最后一个节点的next没有指向下一个节点的地址，所以最后一个节点的next值为null。
1.2.2 链表分类
- 单向链表，双向链表
- 带头链表，不带头链表
- 循环的，非循环的
排列组合后一共8种链表，其中单向、不带头、非循环以及双向、不带头、非循环的链表最为重要，也是本文主要介绍的链表类型。
二、单向，不带头，非循环链表
2.1 单链表的实现
public class MySingleLinkedList {
//头插法
public void addHead(int data){
}
//尾插法
public void addLast(int data){
}
//任意位置插入
public void addindex(int index,int data){
}
//查找是否包含关键字Key是否在单链表中
public boolean contains(int key){
}
//删除第一次出现关键字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;
public ListNode(int val){
this.val=val;
}
}
打印链表
public void display() {
LinkedNode cur = head;
while (cur != null) {
System.out.println(cur.val + " ");
cur = cur.next;
}
}
得到单链表长度
public int size(){
ListNode cur=head;
int len=0;
while(cur!=null){
cur=cur.next;
len++;
}
return len;
}
头插法
public void addHead(int data) {
ListNode node = new ListNode(data);
node.next = head;
head = node;
}
尾插法
public void addLast(int data) {
ListNode node = new ListNode(data);
if (head == null) {
head =last= node;
return;
}
ListNode cur=head;
while (cur.next != null) {
cur = cur.next;
}
cur.next=node;
}
任意位置插入
//任意位置插入
public void addindex(int index, int data) {
int len = size();
if (index < 0 || index > len) {
return;
}
if (index == 0) {
addHead(data);
return;
}
if (index == len) {
addLast(data);
return;
}
ListNode node =new ListNode(data);
ListNode cur=head;
while(index!=0){
cur=cur.next;
index--;
}
node.next=cur.next;
cur.next=node;
}
查找是否包含关键字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) {
//先判断头节点是不是null值和key值
if(head==null){
return;
}else if(head.val==key){
head=head.next;
return;
}
ListNode cur=head.next;
ListNode prev=head;
while(cur!=null){
if(cur.val==key){
prev.next=cur.next;
return;
}
cur=cur.next;
prev= prev.next;
}
}
删除所有key的节点
public void removeAllKey(int key) {
if(head==null) {
return;
}
ListNode cur=head.next;
ListNode prev=head;
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 void clear() {
while(head!=null){
head=head.next;
}
System.out.println("==========");
// while(head!=null){
// ListNode cur=head.next;
// head=null;
// head=cur;
// }
System.out.println("=========");
ListNode cur = head;
while (cur != null) {
ListNode curN = cur.next;
cur.next = null;
cur = curN;
}
head=null;
System.out.println("==========");
// ListNode cur = head;
// while (cur != null){
// head = cur.next;
// cur = null;
// cur = head;
// }
}
主函数
可以用这个主函数进行测试
public static void main(String[] args) {
MySingleLinkedList m = new MySingleLinkedList();
m.addHead(1);
m.addHead(3);
m.addHead(4);
m.addHead(299);
m.addHead(6);
m.addHead(299);
m.addLast(8);
m.addindex(2,299);
m.addindex(2,299);
m.addindex(2,299);
m.addindex(2,299);
m.addindex(2,299);
// m.remove(299);
// m.removeAllKey(299);
m.clear();
m.display();
}
2.2 单链表的优缺点
优点：
- 插入和删除操作方便：在单链表中，插入和删除节点时，只需修改相邻节点的指针，而不需要移动大量数据，因此操作效率较高。
- 适合动态存储：单链表可以随时插入和删除节点，因此适合动态存储数据。
- 空间利用率高：单链表不需要连续的存储空间，因此可以更有效地利用内存空间。
缺点：
- 查找效率低：在单链表中，查找某个元素需要从头节点开始遍历整个链表，因此查找效率较低。
- 只能单向遍历：单链表只能从头到尾遍历，无法从尾到头遍历，这限制了其在某些应用场景中的灵活性。
三、双向，不带头，非循环链表
双向链表中每个节点包括三个部分：一个是存储数据元素的数据域，二个是存储下一个节点地址的指针域，三是存储上一个节点地址的指针域。
3.1 双链表的实现
public class MyLinkedList {
//头插法
public void addHead(int data){
}
//尾插法
public void addLast(int data){
}
//任意位置插入
public void addindex(int index,int data){
}
//查找是否包含关键字Key是否在单链表中
public boolean contains(int key){
}
//删除第一次出现关键字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 LinkedNode{
public int val;
public LinkedNode prev;
public LinkedNode next;
public LinkedNode(int val){
this.val=val;
}
}
public LinkedNode head;
public LinkedNode last;
打印双链表
public void display() {
LinkedNode cur = head;
while (cur != null) {
System.out.println(cur.val + " ");
cur = cur.next;
}
}
得到双链表的长度
public int size() {
int len = 0;
LinkedNode cur = head;
while (cur != null) {
len++;
cur = cur.next;
}
return len;
}
头插法
public void addHead(int data) {
LinkedNode node = new LinkedNode(data);
if (head == null) {
head = last = node;
} else {
head.prev = node;
node.next = head;
head = node;
}
}
尾插法
public void addLast(int data) {
LinkedNode node = new LinkedNode(data);
if (head == null) {
head = last = node;
}
node.prev = last;
last.next = node;
last = node;
}
任意位置插入
public void addindex(int index, int data) {
int len = size();
if (index < 0 || index > len) {
return;
}
if (index == 0) {
addHead(data);
return;
}
if (index == len) {
addLast(data);
return;
}
LinkedNode node=new LinkedNode(data);
LinkedNode cur = head;
while (index != 0) {
cur = cur.next;
index--;
}
node.next = cur;
cur.prev.next = node;
node.prev = cur.prev;
cur.prev = node;
}
查找是否包含关键字Key是否在双链表中
public boolean contains(int key) {
if (head == null) {
return false;
}
LinkedNode 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;
} else if (head.val == key) {
head = head.next;
return;
}
LinkedNode cur = head;
while (cur != null) {
if (cur.val == key) {
cur.prev.next = cur.next;
if (cur.next != null) {
cur.next.prev = cur.prev;
} else {
last = last.prev;
}
return;
}
cur = cur.next;
}
}
删除所有key的节点
public void removeAllKey(int key) {
if (head == null) {
return;
}
while (head.val == key) {
head = head.next;
}
LinkedNode cur = head;
while (cur != null) {
if (cur.val == key) {
cur.prev.next = cur.next;
if (cur.next != null) {
cur.next.prev = cur.prev;
} else {
last = last.prev;
}
}
cur = cur.next;
}
}
清空双链表
public void clear() {
LinkedNode cur = head;
while (cur != null) {
LinkedNode curN = cur.next;
cur.prev=null;
cur.next = null;
cur = curN;
}
head=last=null;
}
3.2 双链表的优缺点
优点：
- 双链表允许从任意节点向前或向后遍历，这使得在链表中间插入和删除节点时更加灵活。
- 在已知节点位置的情况下，双链表可以在常数时间（O(1)）内完成插入和删除操作，因为可以直接访问前驱和后继节点。
- 与数组不同，双链表在插入和删除操作时不需要移动大量数据或重新分配内存，因此具有更好的动态性能。
缺点：
- 每个节点需要额外的指针来存储前驱节点的引用，这增加了节点的内存占用。与单链表相比，双链表需要更多的内存空间。
- 双链表在插入和删除节点时需要更新更多的指针（前驱和后继），这增加了编程的复杂性，特别是在处理边界条件时（如头节点和尾节点）。
- 由于节点在内存中不连续存储，双链表在遍历时的缓存命中率可能较低，导致访问速度较慢，尤其是在需要频繁访问链表节点的情况下。
- 与数组相比，双链表不支持随机访问，即不能直接通过索引访问任意位置的元素，这可能导致在某些算法中性能较差。
四、LinkedList类
LinkedList是java集合框架中实现List接口的一种类， LinkedList的底层是双向，不带头非循环链表！
4.1 LinkedList实现的接口
接口说明：
1.LinkedList实现了List接口
2.LinkedList底层实现双链表
3.LinkedList没有实现RandomAccess接口，因此LinkedList不支持随机访问
4.LinkedList的任意位置插入和删除元素的效率比较高，时间复杂度为O(1)
5.LinkedList比较适合任意位置插入场景
4.2 LinkedList的使用
4.2.1 LinkedList的构造
4.2.2 LinkedList的其他方法
4.2.3 LinkedList的遍历
1.使用for-each遍历
System.out.println("==== for-each遍历 ====");
for (int x :
list) {
System.out.println(x);
}
2.使用for循环遍历
System.out.println("==== for循环遍历 ====");
for (int i = 0; i < list.size(); i++) {
System.out.println(list.get(i)+" ");
}
3.使用迭代器正向遍历
System.out.println("==== 使用迭代器正向遍历 ====");
ListIterator<Integer> it1=list.listIterator();
while(it1.hasNext()){
System.out.println(it1.next()+" ");
}
4.使用迭代器反向遍历
System.out.println("==== 使用迭代器反向遍历 ====");
ListIterator<Integer> it2=list.listIterator(list.size());
while(it2.hasPrevious()){
System.out.println(it2.previous()+" ");
}
mian函数
public class Main {
public static void main(String[] args) {
LinkedList<Integer> list = new LinkedList<>();
list.add(1);
list.add(2);
list.add(34);
list.add(5);
list.add(6);
list.add(7);
System.out.println("==== for-each遍历 ====");
for (int x :
list) {
System.out.println(x);
}
System.out.println("==== for循环遍历 ====");
for (int i = 0; i < list.size(); i++) {
System.out.println(list.get(i) + " ");
}
System.out.println("==== 使用迭代器正向遍历 ====");
ListIterator<Integer> it1 = list.listIterator();
while (it1.hasNext()) {
System.out.println(it1.next() + " ");
}
System.out.println("==== 使用迭代器反向遍历 ====");
ListIterator<Integer> it2 = list.listIterator(list.size());
while (it2.hasPrevious()) {
System.out.println(it2.previous() + " ");
}
}
}
4.3 LinkedList类和ArrayList类的区别
