✅作者简介：大家好，我是再无B～U～G，一个想要与大家共同进步的男人😉😉
🍎个人主页：再无B～U～G-CSDN博客
目标：
1.掌握LinkedList
2.简单模拟实现LinkedList
1.LinkedList的使用
1.1 什么是LinkedList
LinkedList 的官方文档
LinkedList
的底层是双向链表结构
(
链表后面介绍
)
，由于链表没有将元素存储在连续的空间中，元素存储在单独的节点中，然后通过引用将节点连接起来了，因此在在任意位置插入或者删除元素时，不需要搬移元素，效率比较高。
双向不循环链表图：
在集合框架中，LinkedList也实现了List接口，具体如下：
【说明】
1. LinkedList 实现了 List 接口2. LinkedList 的底层使用了双向链表3. LinkedList 没有实现 RandomAccess 接口，因此 LinkedList 不支持随机访问4. LinkedList 的任意位置插入和删除元素时效率比较高，不用移动（时间复杂度为 O(1)）5. LinkedList比较适合任意位置插入的场景
2 LinkedList的使用
2.1. LinkedList的构造
|
方法
|
解释
|
|
LinkedList
()
|
无参构造
|
|
public LinkedList(Collection<? extends E> c)
|
使用其他集合容器中元素构造
List
|
public static void main(String[] args) {
// 构造一个空的LinkedList
List<Integer> list1 = new LinkedList<>();
List<String> list2 = new java.util.ArrayList<>();
list2.add("JavaSE");
list2.add("JavaWeb");
list2.add("JavaEE");
// 使用ArrayList构造LinkedList
List<String> list3 = new LinkedList<>(list2);
}2.2. LinkedList的其他常用方法介绍
|
方法
|
解释
|
|
boolean
add
(E e)
| 尾插 e |
|
void
add
(int index, E element)
| 将 e 插入到 index 位置 |
|
boolean
addAll
(Collection<? extends E> c)
|
尾插
c
中的元素
|
|
E
remove
(int index)
|
删除
index
位置元素
|
|
boolean
remove
(Object o)
|
删除遇到的第一个
o
|
|
E
get
(int index)
|
获取下标
index
位置元素
|
|
E
set
(int index, E element)
|
将下标
index
位置元素设置为
element
|
|
void
clear
()
|
清空
|
|
boolean
contains
(Object o)
|
判断
o
是否在线性表中
|
|
int
indexOf
(Object o)
|
返回第一个
o
所在下标
|
|
int
lastIndexOf
(Object o)
|
返回最后一个
o
的下标
|
|
List<E>
subList
(int fromIndex, int toIndex)
|
截取部分 list
|
public static void main(String[] args) {
LinkedList<Integer> list = new LinkedList<>();
list.add(1); // add(elem): 表示尾插
list.add(2);
list.add(3);
list.add(4);
list.add(5);
list.add(6);
list.add(7);
System.out.println(list.size());
System.out.println(list);
// 在起始位置插入0
list.add(0, 0); // add(index, elem): 在index位置插入元素elem
System.out.println(list);
list.remove(); // remove(): 删除第一个元素，内部调用的是removeFirst()
list.removeFirst(); // removeFirst(): 删除第一个元素
list.removeLast(); // removeLast(): 删除最后元素
list.remove(1); // remove(index): 删除index位置的元素
System.out.println(list);
// contains(elem): 检测elem元素是否存在，如果存在返回true，否则返回false
if(!list.contains(1)){
list.add(0, 1);
}
list.add(1);
System.out.println(list);
System.out.println(list.indexOf(1)); // indexOf(elem): 从前往后找到第一个elem的位置
System.out.println(list.lastIndexOf(1)); // lastIndexOf(elem): 从后往前找第一个1的位置
int elem = list.get(0); // get(index): 获取指定位置元素
list.set(0, 100); // set(index, elem): 将index位置的元素设置为elem
System.out.println(list);
// subList(from, to): 用list中[from, to)之间的元素构造一个新的LinkedList返回
List<Integer> copy = list.subList(0, 3);
System.out.println(list);
System.out.println(copy);
list.clear(); // 将list中元素清空
System.out.println(list.size());
}2.3. LinkedList的遍历
public static void main(String[] args) {
LinkedList<Integer> list = new LinkedList<>();
list.add(1); // add(elem): 表示尾插
list.add(2);
list.add(3);
list.add(4);
list.add(5);
System.out.println(list.size());
//正常遍历
for (int i = 0; i < size; i++) {
System.out.print(list.get(i)+" ");
//list.remove(i);
}
// foreach遍历
for (int e:list) {
System.out.print(e + " ");
}
System.out.println("====Iterator===");
Iterator<Integer> it = list.iterator();
while (it.hasNext()) {
System.out.print(it.next() +" ");
}
System.out.println();
// 使用迭代器遍历---正向遍历
ListIterator<Integer> it = list.listIterator();
while(it.hasNext()){
System.out.print(it.next()+ " ");
}
System.out.println();
// 使用反向迭代器---反向遍历
ListIterator<Integer> rit = list.listIterator(list.size());
while (rit.hasPrevious()){
System.out.print(rit.previous() +" ");
}
System.out.println();
}
3. ArrayList和LinkedList的区别
|
不同点
| ArrayList | LinkedList |
|
存储空间上
|
物理上一定连续
|
逻辑上连续，但物理上不一定连续
|
|
随机访问
|
支持
O(1)
|
不支持：
O(N)
|
|
头插
|
需要搬移元素，效率低
O(N)
| 只需修改引用的指向，时间复杂度为O(1) |
|
插入
|
空间不够时需要扩容
| 没有容量的概念 |
|
应用场景
|
元素高效存储
+
频繁访问
| 任意位置插入和删除频繁 |
4.LinkedList的模拟实现
总体结构
4.1双向链表代码节点结构
4.2得到双向链表的长度
遍历打印
4.3查找是否包含关键字key是否在单链表当中
4.4头插法
4.5尾插法
4.6任意位置前面插入
附带两个私有函数
4.7删除第一次出现关键字为key的节点
4.8删除所有值为key的节点
4.9释放链表
在IDEA中，LinkedList的底层逻辑是双向链表，可以当做栈和堆使用。
5.代码
MyLinkedList类
public class MyLinkedList {
static class ListNode {
public int val;
public ListNode prev;//前驱
public ListNode next;//后继
public ListNode(int val) {
this.val = val;
}
}
public ListNode head;//标志头节点
public ListNode last;//标志尾结点
//得到双向链表的长度
public int size(){
int count = 0;
ListNode cur = head;
while (cur != null) {
count++;
cur = cur.next;
}
return count;
}
//打印链表
public void display(){
ListNode cur = head;
while (cur != null) {
System.out.print(cur.val+" ");
cur = cur.next;
}
System.out.println();
}
//查找是否包含关键字key是否在单链表当中
public boolean contains(int key){
ListNode cur = head;
while (cur != null) {
if(cur.val == key) {
return true;
}
cur = cur.next;
}
return false;
}
//头插法
public void addFirst(int data){
ListNode node = new ListNode(data);
if(head == null) {
//是不是第一次插入节点
head = last = node;
}else {
node.next = head;
head.prev = node;
head = node;
}
}
//尾插法
public void addLast(int data){
ListNode node = new ListNode(data);
if(head == null) {
//是不是第一次插入节点
head = last = node;
}else {
last.next = node;
node.prev = last;
last = last.next;
}
}
//任意位置前面插入
public void addIndex(int index,int data){
try {
checkIndex(index);
}catch (IndexNotLegalException e) {
e.printStackTrace();
}
if(index == 0) {
addFirst(data);
return;
}
if(index == size()) {
addLast(data);
return;
}
//1. 找到index位置
ListNode cur = findIndex(index);
ListNode node = new ListNode(data);
//2、开始绑定节点
node.next = cur;
cur.prev.next = node;
node.prev = cur.prev;
cur.prev = node;
}
//找到双向链表key节点
private ListNode findIndex(int index) {
ListNode cur = head;
while (index != 0) {
cur = cur.next;
index--;
}
return cur;
}
private void checkIndex(int index) {
if(index < 0 || index > size()) {
throw new IndexNotLegalException("双向链表插入index位置不合法: "+index);
}
}
//删除第一次出现关键字为key的节点
public void remove(int key){
ListNode cur = head;
while (cur != null) {
if(cur.val == key) {
//开始删除 处理头节点
if(cur == head) {
head = head.next;
if(head != null) {
head.prev = null;
}else {
//head == null 证明只有1个节点
last = null;
}
}else {
cur.prev.next = cur.next;
if(cur.next == null) {
//处理尾巴节点
last = last.prev;
}else {
cur.next.prev = cur.prev;
}
}
return;//删完一个就走
}
cur = cur.next;
}
}
//删除所有值为key的节点
public void removeAllKey(int key){
ListNode cur = head;
while (cur != null) {
if(cur.val == key) {
//开始删除 处理头节点
if(cur == head) {
head = head.next;
if(head != null) {
//如果有后面的节点
head.prev = null;
}else {
//head == null 证明只有1个节点
last = null;
}
}else {
cur.prev.next = cur.next;
if(cur.next == null) {
//处理尾巴节点
last = last.prev;
}else {
cur.next.prev = cur.prev;
}
}
//return;//删完一个就走
}
cur = cur.next;
}
}
//释放链表
public void clear(){
ListNode cur = head;
while (cur != null) {
ListNode curN = cur.next;
//cur.val = null;
cur.prev = null;
cur.next = null;
cur = curN;
}
head = last = null;
}
}
IndexNotLegalException类
public class IndexNotLegalException extends RuntimeException{
public IndexNotLegalException() {
}
public IndexNotLegalException(String message) {
super(message);
}
}
Test类
import java.util.LinkedList;
import java.util.List;
//双向链表
public class Test {
public static void main(String[] args) {
MyLinkedList myLinkedList = new MyLinkedList();
myLinkedList.addLast(1);
myLinkedList.addLast(2);
myLinkedList.addLast(3);
myLinkedList.addLast(4);
myLinkedList.addLast(5);
myLinkedList.addIndex(3,99);
myLinkedList.addLast(1);
myLinkedList.addLast(1);
myLinkedList.addLast(1);
myLinkedList.addLast(1);
myLinkedList.removeAllKey(1);
myLinkedList.display();
}
}
好了今天就到这里了，感谢观看。
![[YOLOv8] 用YOLOv8实现指针式圆形仪表智能读数(三)](https://img-blog.csdnimg.cn/direct/b34ffab5de594b65bea399b5aec80191.png)
