提示：多练才是王道,加油ヾ(◍°∇°◍)ﾉﾞ
Java链表1. 链表的引入2. 链表的分类3. 单链表模拟实现3.1 典型题目4. LinkedList4.1 LinkedList的模拟实现4.2 LinkedList常见方法总结4.2.1 声明及实例化4.2.2 构造方法4.2.3 遍历4.2.4 其他常用方法5. ArrayList和LinkedList比较
1. 链表的引入在上篇博客中,我们讲解了ArrayList,它是基于动态数组实现的,虽然它支持随机访问且效率高(O(1)),但是插入/删除的效率低,需要大量元素的整体搬移,时间复杂度为O(n),且当容量不够时的扩容会产生很大的性能开销.
而LinkedList的出现解决了这些问题,LinkedList基于双向链表,插入/删除更高效(O(1)):只要找到对应位置节点,修改前后指针即可,不需整体搬移元素;且没有扩容问题,LinkedList节点动态分配,不存在数组容量不足的问题.
当然LinkedList也带来了新的问题,比如随机访问性能差(O(n)),额外内存开销大等.
2. 链表的分类根据三个指标:单向/双向,带头/不带头,循环/非循环,可以将链表分出8种(2x2x2):
其中单向不带头非循环和双向不带头非循环两种在题目中用得最多.接下来也只介绍这两个.
但是需要强调的是,Java标准集合框架(Java.util包)中,官方只提供了双向链表的实现,即LinkedList,因为它提供了功能性和性能的最佳平衡.
那为什么还要将链表分为8种,还要学单链表?
答:链表分为8种是从数据结构与算法的抽象层面来讨论的,追求的是对空间问题的全覆盖,从单/双,循环/非循环,带头/不带头这几个维度进行组合,从理论上是完整且严谨的,它告诉你所有可能的选择.而学习单链表是理解链表概念的基础,它最简单,最能清晰展现"节点"和"指针"的核心思想.
标准库的设计目标是为大多数开发者解决大多数常见问题提供通用,高效的工具,因此功能优先,双向链表的功能远比单链表强大,虽然多耗费一点内存,但是开销是能接受的.整体来说,提供了功能性和性能的最佳平衡.
生动比喻:
理论上的8种链表：就像汽车工程师学习发动机的原理。他们有直列、V型、水平对置、转子、电动等多种模型。他们需要了解每一种的优缺点和适用场景。标准库提供的双向链表：就像普通人去4S店买车。市面上大部分家用车都使用一种经过市场验证、在成本、性能和可靠性上取得最佳平衡的发动机（比如直列四缸或V6）。你不会要求4S店为你提供所有8种发动机选项，因为那既不经济，也不实用。3. 单链表模拟实现链表定义和各方法实现:
public class MySingleLinkedList
{
//节点定义为内部类
class ListNode
{
public int val;
public ListNode next;
public ListNode(int val) {
this.val = val;
}
}
public ListNode head;
//代表链表的头结点
//穷举法创建链表(事实上并不是这么创建的)
public void createList() {
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);
head=node1;
node1.next=node2;
node2.next=node3;
node3.next=node4;
node4.next=node5;
node5.next=null;
}
public void display() {
ListNode node=head;
while(node!=null) {
System.out.print(node.val+" ");
node=node.next;
}
System.out.println();
}
public int size() {
ListNode node=head;
int count=0;
while(node!=null) {
count++;
node=node.next;
}
return count;
}
public void addAtHead(int val) {
ListNode node=new ListNode(val);
node.next=head;
head=node;
}
public void addAtTail(int val) {
ListNode node=new ListNode(val);
ListNode cur=head;
if(head==null) {
//若head为空,不能访问head.next
head=node;
return;
}
while(cur.next!=null) {
cur=cur.next;
}
cur.next=node;
}
public void addAtIndex(int index,int val) {
//判断index的合法性
try {
checkPos(index);
}catch(IndexNotLegalException e) {
e.printStackTrace();
}
//头插尾插
if(index==0) {
addAtHead(val);
return;
}
if(index==size()-1) {
addAtTail(val);
return;
}
//找到cur的前一个节点
ListNode node=new ListNode(val);
ListNode cur=head;
int count=0;
while(count!=index-1){
//cur要走index-1步,才能走到cur前面的节点
cur=cur.next;
count++;
}
//连接
node.next=cur.next;
cur.next=node;
}
private void checkPos(int pos) throws IndexNotLegalException{
if(pos<
0 || pos>
size()) {
throw new IndexNotLegalException("Index不合法");
}
}
public boolean contains(int val) {
ListNode cur=head;
while(cur!=null) {
if(cur.val==val) return true;
cur=cur.next;
}
return false;
}
//删除第一次出现的val
public void remove(int val) {
if(head==null) return;
if(head.val==val) {
head=head.next;
return;
}
ListNode cur=head;
while(cur.next!=null) {
if(cur.next.val==val) {
cur.next=cur.next.next;
return;
}
cur=cur.next;
}
}
//删除所有val
public void removeAllKey(int val) {
//1.判空
if(head==null) return;
//2.定义prev和cur
ListNode prev=head;
ListNode cur=head.next;
//3.开始判断并删除
while(cur!=null) {
if(cur.val==val) {
prev.next=cur.next;
} else {
prev=cur;
}
cur=cur.next;
}
//4.处理头结点
if(head.val==val) {
head=head.next;
}
}
public void clear() {
// head=null;//最直接的方式
ListNode cur=head;
while(cur!=null) {
ListNode curN=cur.next;
cur.next=null;
cur=curN;
}
head=null;
}
}
addAtIndex方法抛出的异常:
public class IndexNotLegalException
extends RuntimeException {
public IndexNotLegalException() {
}
public IndexNotLegalException(String message) {
super(message);
}
}
测试类:
public class Test
{
public static void main(String[] args) {
MySingleLinkedList msl=new MySingleLinkedList();
// msl.createList();
// msl.display();
// System.out.println(msl.size());
// System.out.println("======测试头插=====");
// msl.addAtHead(12);
// msl.addAtHead(23);
// msl.addAtHead(34);
// msl.addAtHead(56);
// msl.display();
// System.out.println("======测试尾插=====");
// msl.addAtTail(1);
// msl.addAtTail(2);
// msl.addAtTail(3);
// msl.display();
// System.out.println("========测试在index插入节点========");
// msl.addAtIndex(0,100);
// msl.addAtIndex(1,100);
// msl.addAtIndex(5,100);
// msl.display();
// System.out.println("=====测试contains方法=====");
// System.out.println(msl.contains(100));
// System.out.println(msl.contains(99));
// System.out.println("=====测试remove方法=====");
//// msl.remove(100);
// msl.removeAllKey(100);
// msl.display();
// System.out.println("=====测试clear方法=====");
// msl.clear();
// msl.display();
msl.addAtTail(10);
msl.addAtTail(10);
msl.addAtTail(10);
msl.addAtTail(10);
msl.removeAllKey(10);
msl.display();
}
}
比较基础,就不再一个一个讲了~~
3.1 典型题目206. 反转链表 - 力扣（LeetCode）
876. 链表的中间结点 - 力扣（LeetCode）
面试题 02.02. 返回倒数第 k 个节点 - 力扣（LeetCode）
21. 合并两个有序链表 - 力扣（LeetCode）
链表分割_牛客题霸_牛客网
链表的回文结构_牛客题霸_牛客网
160. 相交链表 - 力扣（LeetCode）
141. 环形链表 - 力扣（LeetCode）
142. 环形链表 II - 力扣（LeetCode）
4. LinkedList4.1 LinkedList的模拟实现LinkedList定义和各方法实现:
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 tail;
//得到单链表的长度
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=tail=node;
else {
node.next=head;
head.prev=node;
head=node;
}
}
//尾插法
public void addLast(int data){
ListNode node=new ListNode(data);
if(head==null) head=tail=node;
else {
tail.next=node;
node.prev=tail;
tail=node;
}
}
//任意位置插入,第一个数据节点为0号下标
public void addIndex(int index,int data){
try {
checkIndex(index);
}catch(IndexOutOfBoundsException e){
e.printStackTrace();
}
if(index==0) {
addFirst(data);
return;
}
if(index==size()) {
addLast(data);
return;
}
//处理中间位置,首先要先找到index
ListNode cur=head;
ListNode node=new ListNode(data);
int count=index;
while(count!=0) {
cur=cur.next;
count--;
}
node.next=cur;
cur.prev.next=node;
node.prev=cur.prev;
cur.prev=node;
}
private void checkIndex(int index) throws IndexNotLegalException{
if(index<
0 || index>
size()) {
throw new IndexNotLegalException("add时index不合法");
}
}
//删除第一次出现关键字为key的节点
public void remove(int key){
ListNode cur=head;
while(cur!=null) {
if(cur.val==key) {
//找到了要删除的那个节点
//若该节点是head
if(head.val==key) {
head=head.next;
if (head != null) {
//这个if处理的是,该链表只有一个节点,删除完头之后,链表为空的情况(若此时还继续下去的话,就空指针异常了)
head.prev=null;
}
else {
tail=null;
//空链表,尾结点也要置为空
}
} else {
//该节点不是head
cur.prev.next=cur.next;
if(cur.next==null) {
//该节点是tail
tail=cur.prev;
}else {
//该节点不是head也不是tail
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) {
//找到了要删除的那个节点
//若该节点是head
if(head.val==key) {
head=head.next;
if (head != null) {
//这个if处理的是,该链表只有一个节点,删除完头之后,链表为空的情况(若此时还继续下去的话,就空指针异常了)
head.prev=null;
}
else {
tail=null;
//空链表,尾结点也要置为空
}
} else {
//该节点不是head
cur.prev.next=cur.next;
if(cur.next==null) {
//该节点是tail
tail=cur.prev;
}else {
//该节点不是head也不是tail
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=tail=null;
}
}
add时抛出的异常:
public class IndexNotLegalException
extends RuntimeException {
public IndexNotLegalException() {
}
public IndexNotLegalException(String message) {
super(message);
}
}
测试类:
public static void main1(String[] args) {
//模拟实现LinkedList
MyLinkedList list=new MyLinkedList();
list.addFirst(1);
list.addFirst(2);
list.addFirst(3);
list.display();
list.addLast(10);
list.addLast(20);
list.addLast(30);
list.display();
list.addIndex(0,100);
list.addIndex(2,100);
list.addIndex(8,100);
list.display();
list.remove(1);
list.display();
System.out.println("删除所有的100");
list.removeAllKey(100);
list.display();
}
4.2 LinkedList常见方法总结4.2.1 声明及实例化
查看LinkedList在源码中的第一可以看到,它实现了List和Deque接口,意味着它既能当做List使用,又能当做队列使用:
当做List使用,同样有两种写法,按需求选取:
特性LinkedList list1=…List list2=…引用类型具体类(LinkedList)接口(List)可调用的方法所有LinkedList的方法+所有List接口的方法仅限List接口中定义的方法灵活性低,代码与LinkedList强绑定,难以更换实现高,只需修改new后面的实现即可,前面代码通常无需改动推荐程度不常用,除非你明确需要用到LinkedList的特有功能更常用,符合面向对象设计原则4.2.2 构造方法同ArrayList一样,除了不含参数的构造方法外,还能创建包含指定集合中所有元素的新链表:
例如:
上述代码创建了一个包含Integer类型元素的ArrayList,并以其为数据源初始化了一个LinkedList.
4.2.3 遍历几种遍历方法和ArrayList一样一样的
for循环
for-each循环
迭代器
4.2.4 其他常用方法方法解释boolean add(E e)尾插evoid add(int index,E element)将e插入到index位置boolean addAll(Collecctionc)尾插c中的元素E remove(int index)删除index位置的元素boolean remove(Object o)删除遇到的第一个oE get(int index)获取index位置元素E set(int index,E element)将下标index位置元素设置为elementvoid clear()清空boolean contains(Object o)判断是否包含oint indexOf(Object o)返回第一个o所在的下标int lastIndexOf(Object o)返回最后一个o的下标List subList(int fromIndex,int toIndex)截取部分list5. ArrayList和LinkedList比较核心差别对比表:
特性ArrayListLinkedList底层数据结构动态数组(Object[] elementData)双向链表(Node first,last)内存占用较小(仅存储数据本身和数组开销)较大(每个节点都需要额外的内存存储前后节点的引用)访问性能极快O(1)通过索引直接计算内存地址来访问慢O(n)必须从头部或尾部开始遍历链表插入/删除性能平均较慢O(n)需要移动后续元素快O(1)但前提是已经定到了操作位置尾部插入很快O(1)头尾插入时定位过程很快O(1)中间/头部插入很慢(需要移动元素)中间插入时定位过程慢O(n)扩容机制需要动态扩容(复制数组)无需扩容,按需动态增加节点如何选择:
选择ArrayList的场景:
需要频繁随机访问元素元素数量大致可知(避免频繁扩容)追求更好的内存效率和CPU缓存局部性(数组在内存中是连续的)选择LinkedList的场景:
需要频繁在列表头部或中间进行插入和删除操作不确定元素数量需要实现Deque(双端队列)的功能