硅基计划3.0 学习总结贰顺序表与链表

技术文档

图 (493)

文章目录

- 一、顺序表——ArrayList
- - 1. 实现自己MyArrayList
  - - 1. 实现add基础方法
    - 2. 实现指定位置加元素add方法
    - 3. 完善数组打印方法display
    - 4. 完善根据下标找元素get
    - 5. 完善判断数字是否在数组中contains
    - 6. 根据数字找下标indexOf
    - 7. 更新指定下标元素set
    - 8. 获取数组有效长度size
    - 9. 清空数组clear
    - 10. 指定数字删除
  - 2. 使用ArrayList
  - 3. 遍历ArrayList
  - 4. 练练手
  - - 1. 杨辉三角
    - 2. 简易牌组游戏
  - 5. 小结
- 二、链表LinkList——单向
- - 1. 创造链表creatList
  - 2. 遍历链表display
  - 3. 获取链表长度sieze
  - 4. 遍历链表寻找数字是否存在contains
  - 5. 头插法插入数字addFirst
  - 6. 尾插法插入数字addLast
  - 7. 任意位置插入
  - 8. 删除数字第一次出现的节点remove
  - 9. 删除所有为指定数字的节点removeAllKey
  - 10. 清空链表
  - 11. 小试牛刀
  - - 1. 反转链表
    - 2. 寻找中间节点
    - 3. 找到链表中倒数第K个节点
    - 4. 链表分割
    - 5. 有序链表拼接
    - 6. 判断回文列表
    - 7. 链表相交
    - 8. 判断列表是否有环并求出其入口点
- 三、链表LinkList——双向
- - 1. 头插法
  - 2. 尾插法
  - 3. 是否包含指定数字
  - 4. 求链表长度
  - 5. 打印链表
  - 6. 插入节点到指定位置
  - 7. 删除指定数字第一次出现的节点
  - 8. 删除指定数字全部节点
  - 9. 清空链表
  - 10. 测试功能的代码用例
  - 11. Java官方提供LinkedList类

前置知识：线性表表示的是有前驱和后继的表，除了首尾
前驱和后继：都有前一个数和后一个数

一、顺序表——ArrayList

指的是从逻辑上和物理上都是连续的表，因其特性（连着的嘛），根据数组的性质，我们可以把顺序表看成数组
我们知道ArrayList中有很多方法，但是有些方法不妨我们先自己实现下，理解其原理

1. 实现自己MyArrayList

//我们先定义一个接口，来放我们要实现的方法public interface IArrayList { // 新增元素,默认在数组最后新增 void add(int data); // 在 pos 位置新增元素 void add(int pos, int data); // 判定是否包含某个元素 boolean contains(int toFind); // 查找某个元素对应的位置 int indexOf(int toFind); // 获取 pos 位置的元素 int get(int pos); // 给 pos 位置的元素设为 value void set(int pos, int value); //删除第⼀次出现的关键字key void remove(int toRemove); // 获取顺序表⻓度 int size(); // 清空顺序表 void clear(); // 打印顺序表，注意：该⽅法并不是顺序表中的⽅法，为了⽅便看测试结果给出的 void display();}//我们在定义自己的MyArrayList类public class MyArrayList implements IArrayList{ private int [] array; private int usedSize; public static final int SIZE = 10;//默认大小 //默认构造⽅法 MyArrayList(){ array = new int[SIZE]; } // 将顺序表容量设置为capacity MyArrayList(int capacity){ array = new int[capacity]; } @Override public void add(int data) { } @Override public void add(int pos, int data) { } @Override public boolean contains(int toFind) { return false; } @Override public int indexOf(int toFind) { return 0; } @Override public int get(int pos) { return 0; } @Override public void set(int pos, int value) { } @Override public void remove(int toRemove) { } @Override public int size() { return 0; } @Override public void clear() { } @Override public void display() { }}

构造方法我提供类两种，如果你指定了大小就按照你的大小来，否则就使用默认大小为10的数组

1. 实现add基础方法

我们要求我们指定一个数字data，把它存在顺序表的末尾
我们直接让有效数字的下标的元素等于我们的data就好了，为什么？
因为加入你的有效数字是4个，根据数组0下标起始，此时你的4下标还没有元素，我们直接存就好了，再让有效数字++一下

@Override public void add(int data) { array[usedSize] = data; usedSize++; }

但是，这个代码就没有问题了吗，那我问你，如果你数组满了能存吗，嗯？
因此我们还要写一个判断数组是否满了的方法isFull()

private boolean isFull(){ return usedSize == array.length; }

那我们满了是不是需要扩容啊，那我们在判断满了后还要写一个扩容方法growTo()

private void growTo(){//扩容两倍 array = Arrays.copyOf(array,2*array.length); }

当然，我们还可以指定扩容几倍，因此我重载了下方法

private void growTo(int size){//扩容任意倍 array = Arrays.copyOf(array,size*array.length); }

因此此时add()方法最终是

//将data存在末尾 @Override public void add(int data) { if(isFull()){//判断是否是空 //我们要进行扩容操作 growTo(); } array[usedSize] = data; usedSize++; }

2. 实现指定位置加元素add方法

我们先想下要怎么去加，是不是要让你指定位置的元素数字往后移，你才有位置去加啊
但是你移动是从前面的数字往后移吗，这样会导致数据丢失
硅基计划3.0 学习总结贰顺序表与链表
就跟我图里面的一样，这样是不是会导致后面的数据丢失了，因此我们需要从后面开始往前面循环
但是你又要注意了，你的有效数字现在是3个，那你能从下标为3开始吗，不可以，显然越界了
那你想循环的结束条件是什么，是不是走到你指定位置得位置就好了，此时原始数组中你的数字也完成了移动，就变成了这样
硅基计划3.0 学习总结贰顺序表与链表
此时你直接插入元素就好了
但是你在想想，数组满了能插入吗，是不是要扩容
还有，你的插入位置能是负数吗，下标有负的吗
还有，你插入的位置能超过有效数字边界吗，那这样就没有意义了
因此我们再写个方法验证pos合法性

private void posIsNormal(int pos) throws PosException { if(pos < 0 || pos > usedSize){ throw new PosException(\"下标非法\"); } }

对于下标非法，我自定义了一个异常类PosException，继承了RuntimeException类

public class PosException extends RuntimeException{ public PosException() { } public PosException(String message) { super(message); }}

最终在指定位置添加元素的方法如下

@Override public void add(int pos, int data) { try { posIsNormal(pos); } catch (PosException e) { throw new RuntimeException(e); } if(isFull()){ growTo(); } for (int i = usedSize-1; i >= pos ; i--) { array[i+1] = array[i]; } //此时我们放入元素 array[pos] = data; //记得有效元素个数++一下 usedSize++; }

3. 完善数组打印方法display

请注意打印的终止条件是有效元素个数，不能是数组长度，否则越界（超过有效数字范围就没有数字了啊）

@Override public void display() { for (int i = 0; i < usedSize; i++) { System.out.println(array[i]); } }

4. 完善根据下标找元素get

那我们按照之前思路，是不是先要检查下标的合法性，你想想我们刚刚写的方法，如果下标和有效元素个数一样，它不会抛出异常
但是你想想，我有效元素个数对应的下标应该是我有效元素个数-1才对呀
那如果下标是我的有效元素个数，是不是就会越界，因此我们重新定义一个判断下标是否合法的方法

private void posIsNormalPlus(int pos) throws PosException{ if(pos < 0 || pos >= usedSize){ throw new PosException(\"寻找元素下标非法\"); } }

但是你又想，空的数组能获取到指定下标的元素吗，不行，因此我们还要写一个方法来判断是否是空数组

public boolean isEmpty(){ return usedSize == 0; }

那我们是不是可以在定义一个空数组异常CapacityException，，继承了RuntimeException类

public class CapacityException extends RuntimeException{ public CapacityException() { } public CapacityException(String message) { super(message); }}

因此完整的根据下标找元素代码如下所示

@Override public int get(int pos) throws CapacityException{ try { posIsNormalPlus(pos); }catch (PosException e){ throw new RuntimeException(e); } if(isEmpty()){ throw new CapacityException(\"空数组非法\"); } return array[pos]; }

但是有个小问题，当你的指定的下标是0并且usedSize也是0的时候会抛出异常，但是这也是一种异常情况，不影响

5. 完善判断数字是否在数组中contains

@Override public boolean contains(int toFind) { for (int i = 0; i < usedSize; i++) { if(toFind == array[i]){ return true; } } return false; }

不用担心空数组的问题，空数组循环根本进不来

6. 根据数字找下标indexOf

@Override public int indexOf(int toFind) { for (int i = 0; i < usedSize; i++) { if(array[i] == toFind){ return i; } } return -1; }

为什么可以return-1呢，因为你下标根本不存在-1嘛，返回了这个值就代表找不到

7. 更新指定下标元素set

老样子，想判断下标合法性，再更新

@Override public void set(int pos, int value) { posIsNormalPlus(pos); array [pos] = value; }

8. 获取数组有效长度size

@Override public int size() { return usedSize; }

9. 清空数组clear

@Override public void clear() { usedSize = 0; }

为什么直接把usedSize置为0就好了，你这么想，我把有效元素个数变成了0，那我不就相当于数组消失了吗，后续我再添加元素的时候我直接覆盖就好了

10. 指定数字删除

那我们要删除数字是不是得先知道数字的下标呀，因此我们先调用indexOf()方法得到下标
如果找不到就说找不到
如果找得到，我们再使用循环让后一个元素盖住前一个元素就好了

@Override public void remove(int toRemove) { int index = indexOf(toRemove); if(index == -1){ System.out.println(\"找不到\"); return; } for (int i = index; i < usedSize-1; i++) { array[i] = array[i+1]; } //如果是引用类型，最后一个多余的元素要置为null usedSize--;//不要忘了有效数字个数要减少 }

为什么循环结束是usedSize-1呢，因为会产生越界，这个之前解释过了

2. 使用ArrayList

因为ArrayList是以泛型实现，因此我们要明确包装类
因为其实现了RandomAccess接口，因此其可以随机访问
因为其实现了Cloneable接口，因此其可以被克隆
因为其实现了Serializasle接口，因此其可被序列化
ArrayList可以被动态扩容
其在单线程中可用，在多线程可用可用Vector或者是CopeOnWriteArray

我们打开源码，这些是成员变量
硅基计划3.0 学习总结贰顺序表与链表

我们看其构造方法
其中有一个带参的构造方法如下

public ArrayList(int initialCapacity) { if (initialCapacity > 0) { this.elementData = new Object[initialCapacity]; } else if (initialCapacity == 0) { this.elementData = EMPTY_ELEMENTDATA; } else { throw new IllegalArgumentException(\"Illegal Capacity: \"+ initialCapacity); } }

你看如果你给的值为0，就调用我们的空数组，否则就new一个新数组

但同时还有个不带参的构造方法，空数组等于空数组，它怎么放元素呢？

public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; }

这个问题我们先按下不表，带回来解释

还有一个带参的构造方法

public ArrayList(Collection<? extends E> c) { Object[] a = c.toArray(); if ((size = a.length) != 0) { if (c.getClass() == ArrayList.class) { elementData = a; } else { elementData = Arrays.copyOf(a, size, Object[].class); } } else { // replace with empty array. elementData = EMPTY_ELEMENTDATA; } }

这个构造方法意思就是你传入的类型只能是Collection类及其子类，其子类范围很广的
因此我们new对象可以这么来做

public static void main(String[] args) { ArrayList<Integer> arrayList = new ArrayList<>(); arrayList.add(1); arrayList.add(4); ArrayList<Integer> arrayLists = new ArrayList<>(arrayList); arrayLists.add(8); System.out.println(arrayLists); }

诶，可以使用另一个集合类去实例化当前的集合类
然后你打印的内容包括了之前集合类的内容：[1, 4, 8]

ArrayList内部也有很多方法
对于remove()方法，如果你直接写想要删除的数字，默认删除的是下标，因此如果你写的很大，比如remove(9999)会产生越界
因此如果你想删除对应数字，应该remove(new Integer(9999))

但是我们重点来看subList方法
这个方法可以截取顺序表中的一部分，范围是左闭右开List list = arrayList.subList(0,2);，此时list对象中就存的是我们刚刚截取的顺序表
但是，如果你把list中元素改了，神奇的是原来arrayList中数字也发生了改变
打印结果：[1, 4]---->[10, 4]
为什么呢？因为subList方法在截取的时候里面存的是地址，你把地址指向的数字改了，那远顺序表对应元素不就改了吗

小问题：List和ArrayList区别是什么呢？
List list = new ArrayList();和ArrayList <Integer。 arrayList = new ArrayList();
首先是其内部拓展性，ArrayList能够调用的方法比List更多，但是可读性List更胜一筹
因为你ArrayList你看不出来其实现了List接口

我们来解答之前的疑惑：“但同时还有个不带参的构造方法，空数组等于空数组，它怎么放元素呢？”
我们可以点开add方法看下

public boolean add(E e) { modCount++; add(e, elementData, size); return true; }

可以看到又调用了一个add方法，点开

private void add(E e, Object[] elementData, int s) { if (s == elementData.length) elementData = grow(); elementData[s] = e; size = s + 1; }

我们看到了，即使是空数组，里面也调用了grow()方法，默认大小是10，我们点开grow()看看

private Object[] grow(int minCapacity) { int oldCapacity = elementData.length; if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { int newCapacity = ArraysSupport.newLength(oldCapacity,  minCapacity - oldCapacity, /* minimum growth */  oldCapacity >> 1  /* preferred growth */); return elementData = Arrays.copyOf(elementData, newCapacity); } else { return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)]; } }

可以看到进行的是1.5被的扩容，然后你看到了newLength，想着我能不能自己定义扩容几倍，想重写，但是grow()被private修饰了，无法重写

3. 遍历ArrayList

有几种方法，第一个就是耳熟能详的遍历数组

//普通遍历 for (int i = 0; i < arrayList.size(); i++) { System.out.print(arrayList.get(i)+\" \"); }

第二个是强遍历

//强遍历for(Integer x:arrayList){ System.out.print(x+\" \");

第三个就是使用迭代器，我们点开ArrayList的迭代器iterator，发现其父类List也有迭代器，发现其父类的父类Collcetion还是有迭代器，最终再其共同父类发现了最开始的迭代器方法
现在你可能有个问题，为什么这么多父类都有迭代器方法呢？
这是为了在不断的继承中扩展能力，职责分离，也是为了支持多态，每一次继承接口的能力扩展

//Iterator接口中Iterator<T> iterator();//Collection接口中Iterator<E> iterator();//List接口中Iterator<E> iterator();//ArrayList类中public Iterator<E> iterator() { return new Itr(); } /** * An optimized version of AbstractList.Itr */ private class Itr implements Iterator<E> { int cursor; // index of next element to return int lastRet = -1; // index of last element returned; -1 if no such int expectedModCount = modCount; // prevent creating a synthetic constructor Itr() {}

因此我们就可以使用迭代器，其返回类型是Iterator即最原始的接口类，这也是为了多态

//使用迭代器Iterator <Integer> it = arrayList.iterator();while(it.hasNext()){ System.out.print(it.next()+\" \");}

这段代码意思就是检测it对象位置下一个是否存在数字，存在就打印，it往下走一个位置，直到其之后不存在数据为止

但是我们用Iterator只能单向遍历，即从前往后
但是我们使用ListIterator可以反着遍历，只不过为了保持代码简洁性平时少用
当然其也可以正向或者反向打印，原理都差不多

ListIterator <Integer> lit = arrayList.listIterator();//正向打印while(lit.hasNext()){ System.out.print(lit.next()+\" \");}System.out.println();//反向打印while(lit.hasPrevious()){ System.out.print(lit.previous()+\" \");}

4. 练练手

1. 杨辉三角

题目链接
我们刚刚已经学了顺序表，我们就想想如何使用顺序表实现它

给出提示：二维数组（顺序表）List<List>

我们先思考下，杨辉三角每一行都和上一行有关系，那是不是我可以把每一行看成一个一维数组，在二维数组中每个元素即是一维数组
那我通过二维顺序表中第i个元素（即第i行）获取上一个元素（即第i-1）行中的上方元素和左上方元素就好了
然后第一列和最后一列永远都是1不变，画个图给大家看下
硅基计划3.0 学习总结贰顺序表与链表
因此我们就来实现下

//杨辉三角 public static void main(String[] args) { Scanner sc = new Scanner(System.in); int row = sc.nextInt();//求第几行 List <List<Integer>> ret = new ArrayList<>();//二维数组 List <Integer> list = new ArrayList<>();//第一行的一维数组 list.add(1);//给第一行第一个数组加上数字1 ret.add(list);//第一行的元素添加到二维数组的第一个元素即第一行 for (int i = 1; i < row; i++) { //先处理每一行第一个元素都是1 List <Integer> currentRow = new ArrayList<>();//当前行 currentRow.add(1);//当前行第一个元素是1 //此时我们需要获取到上一行的信息 List<Integer> previousRow = ret.get(i-1);//定义一个临时二维数组获取上一行信息 for (int j = 1; j < i; j++) {//列数不能超过行数 //存储上一行的同一列和左边一列的数字 int value = previousRow.get(j)+previousRow.get(j-1); //循环在一直往后走，因此只要满足条件就行 currentRow.add(value); } //此时就剩下最后一个数字1 currentRow.add(1); //再把每一行添加到二维数组中 ret.add(currentRow); } }

你是不是想说第二行的时候上一行只有一个数，这样会不会越界，其实第二行的时候第二层循环根本进不来，自然就不会越界

2. 简易牌组游戏

我们先定义一个卡片类，存放每一个卡片信息

public class Card { private int value;//牌值 private String pattern;//牌的图案 public Card(int value, String pattern) { this.value = value; this.pattern = pattern; } @Override public String toString() { return \"Card{\" + \"value=\" + value + \", pattern=\'\" + pattern + \'\\\'\' + \'}\'; }}

同时我们再定义一个卡组，来初始化和洗刷我们的牌，每一个方法都在注释中有讲解

public class CardGame { public static final String[] cardType = {\"▲\", \"⬛\", \"○\", \"◆\", \"☆\"}; //返回值是List一维数组，即对象数组 public List<Card> cardBuy() { //五组牌，每中图案十张牌 List<Card> cardList = new ArrayList<>(10); for (int i = 0; i < 5; i++) {//对每种图案的牌进行初始化 for (int j = 1; j <= 10; j++) {//每种图案对应10张牌，每种图案生成十张牌 String suit = cardType[i];//当前循环对应的是第几种图案 int rank = j;//牌值 Card card = new Card(rank, suit);//每张牌就是一个对象 cardList.add(card);//要把每张牌添加到牌组中 } } return cardList; } public void shuffle(List<Card> cardList) {//洗牌 Random random = new Random(); //按顺序倒着换牌，就避免了前面换过了一次又换 //你看假如我第41个牌和第4个牌换了 //那么我下一次的随机数生成范围就只有0~40 //而若如果正着来，加入我第4行和第45行换了 //那我下一次随机数生成范围要保证不重复，还得要+5，才能保证不在原本范围内 for (int i = cardList.size() - 1; i > 0; i--) { //为什么i不能等于0，因为Radom类中不允许为0不然就异常 int index = random.nextInt(i); //我们还要写一个交换方法 swap(cardList, i, index); } } private void swap(List<Card> cardList, int i, int j) {//交换牌 //定义一个中间类，不能直接使用中间变量交换 Card temp = cardList.get(i); cardList.set(i, cardList.get(j)); cardList.set(j, temp); }}

好，接下来我们就要写怎么抓牌了，我们采用三个人轮流抓五张牌，即一个人最多抓五次
我们思考下如何确定这个牌属于谁呢，我们想到了，可以使用顺序表
定义一个二维顺序表以每个元素存放每个人牌组

public static void main(String[] args) { CardGame cardGame = new CardGame(); List<Card> cardList = cardGame.cardBuy(); cardGame.shuffle(cardList); //先定义三个人的牌组 List <Card> arrayList1 = new ArrayList<>(); List <Card> arrayList2 = new ArrayList<>(); List <Card> arrayList3 = new ArrayList<>(); //定义二维顺序表存放每个人牌组信息 List<List<Card>> arrayList = new ArrayList<>(); arrayList.add(arrayList1); arrayList.add(arrayList2); arrayList.add(arrayList3); for (int i = 0; i < 5; i++) { for (int j = 0; j < 3; j++) { //每次摸牌删除0下标的牌，删除后后面的牌会往前补齐 Card card = cardList.remove(0); //获取每个人牌组，让每个人牌组中拿一张牌 arrayList.get(j).add(card); } } }

5. 小结

对于顺序表，每次空间不够就扩容1.5倍，势必会导致空间的浪费
并且每次插入数据的时候都需要去移动原有数据，如果我们要频繁更新数据，这时间复杂度必然大
因此顺序表适用于静态数据类型或者是数据查找等不频繁更新数据的场景

1750851495471

二、链表LinkList——单向

链表和我们顺序表的接口类似，只不过它们在物理上不连续，但是在逻辑上内部是有联系的
它们是由一个个节点（结点）组成的
分为很多种：单向和双向、带头和不带头、循环和非循环
平常我们用到的大多数都是单向不带头非循环和单向带头非循环

我们先来看图，对于链表，每个节点是由值域和地址域组成的
值域里存放数值，值域里存放下一个节点的地址

我们先来看单向不带头非循环节点示意图
硅基计划3.0 学习总结贰顺序表与链表
我们可以知道，其头节点并不稳定，会改变位置

我们再来看下单向带头非循环节点示意图
硅基计划3.0 学习总结贰顺序表与链表
我们可以知道插入新的节点的时候头节点并不会改变，还是在原来位置

再来解释下什么是双向：我们刚刚的两个图都是只存了下一个节点的地址，只能从前往后遍历，反而双向就是存了下一个节点和上一个节点的地址，也就是说可以从后往前遍历
接着看什么是循环：就是说遍历到最后一个节点的时候，里面存的是第一个节点的地址，又可以倒回去

要使得节点有值和地址，数组肯定不行，那只能是类了，但是你不可能定义那么多类，那最后只能是定义内部类了

我们先定义一个链表类MyLinkList，然后在定义一个内部类LinkNode，这个内部类表示每个节点的信息
再在外部类MyLinkList中定义一个成员变量headAdress用来表示头节点地址
再定义一个接口用来拓展当前链表类MyLinkList功能

//ILink接口public interface ILink { //头插法 void addFirst(int data); //尾插法 void addLast(int data); //任意位置插⼊,第⼀个数据节点为0号下标 void addIndex(int index,int data); //查找是否包含关键字key是否在单链表当中 boolean contains(int key); //删除第⼀次出现关键字为key的节点 void remove(int key); //删除所有值为key的节点 void removeAllKey(int key); //得到单链表的⻓度 int size(); //清空链表 void clear(); //展示链表 void display();}//自定义链表类MyLinkListpublic class MyLinkList implements ILink{ static class LinkNode { public int value; public LinkNode nextAdress;//用类名表示下一个节点地址 //节点不用构造函数，待会需要让其指向下一个节点地址 public LinkNode(int value) { this.value = value; } } //存的是链表首节点的地址 public LinkNode headAdress; @Override public void addFirst(int data) { } @Override public void addLast(int data) { } @Override public void addIndex(int index, int data) { } @Override public boolean contains(int key) { return false; } @Override public void remove(int key) { } @Override public void removeAllKey(int key) { } @Override public int size() { return 0; } @Override public void clear() { } @Override public void display() { }}

我们现在要开始创建链表了，发现没有创建链表的方法，那不妨我们自己定义一个creatList()

1. 创造链表creatList

我们首先new几个节点对象，然后传值
此时我们思考下，nexxtAdress如何存下一个节点地址呢？
我们想到了，因为引用存的是地址，因此我们可以利用引用去引用下一个节点对象
最后不要忘了头节点的引用

@Override public void creatListSimple() { LinkNode l1 = new LinkNode(10); LinkNode l2 = new LinkNode(13); LinkNode l3 = new LinkNode(19); LinkNode l4 = new LinkNode(22); l1.nextAdress = l2; l2.nextAdress = l3; l3.nextAdress = l4; this.headAdress = l1; }

2. 遍历链表display

你想，我们遍历是不是可以使用头节点进行遍历，打印当前节点的值，然后头节点地址就变成下一个节点地址，到最后一个节点发现这个节点中地址是null，那就说明到头了
但是此时有个问题，你是用的头节点地址进行遍历，那你遍历完之后头节点岂不是不是原来的地方了
因此我们还要定义一个临时地址来帮助我们遍历链表

@Override public void display() { //定义一个临时地址代替head往后遍历 LinkNode currentAdress = headAdress; while(currentAdress != null){ System.out.println(); currentAdress = currentAdress.nextAdress; } }

3. 获取链表长度sieze

这个也是跟刚刚逻辑一样，为了防止头节点丢失，定义一个临时节点代替头节点行动

@Override public int size() { int count = 0; LinkNode currentAdress = headAdress; while(currentAdress != null){ count++; currentAdress = currentAdress.nextAdress; } return count; }

4. 遍历链表寻找数字是否存在contains

也是一样的定义中间节点代替头节点行动

@Override public boolean contains(int key) { LinkNode currentAdress = headAdress; while(currentAdress != null){ if(currentAdress.value == key){ return true; } currentAdress = currentAdress.nextAdress; } return false; }

5. 头插法插入数字addFirst

头插法指的就是把数字放入第一个节点位置，此时你插入的数字即变成了新的头节点
你想想，你插入节点后是不是要和后面的节点绑定，因此你需要绑定原来的头节点的地址
然后新的头节点指向就是你新插入的节点的地址了

@Override public void addFirst(int data) { LinkNode currentAdress = new LinkNode(data); currentAdress.nextAdress = headAdress; headAdress = currentAdress; }

Q：为什么不先让head往前走，指向我们新插入的节点再让新插入的节点的nextAdress再和原来头节点的地址进行绑定呢？
A：因为这样会导致原本的头节点地址丢失

为什么不用判断原本的头节点为空的情况？
如果你第一个节点是空的，根据我们刚刚的代码currentAdress.nextAdress = null，headAdress = null，本身就是第一个节点了，不用判断是不是空的了

使用链表我们无需移动元素，时间复杂度仅为O(1)

6. 尾插法插入数字addLast

我们先判断链表中有没有节点，没有的话我们直接让新插入的节点充当第一个节点
如果链表中本身存在节点，我们就要去寻找尾节点在哪里（即找到地址）
我们先定义一个临时节点替代头节点去遍历整个链表，找到尾节点后，让尾节点中的nextAdress地址赋予我们新插入节点的地址就可以了

@Override public void addLast(int data) { LinkNode news = new LinkNode(data); if(headAdress == null){ headAdress = news; } //找尾节点 LinkNode currentAdress = headAdress; while(currentAdress.nextAdress != null){ currentAdress = currentAdress.nextAdress; } currentAdress.nextAdress = news; }

7. 任意位置插入

首先我们得先判断你插入的下标是不是合法的
因此我们定义一个数组下标异常类IndexOutOfBoundException

public class IndexOutOfBoundException extends RuntimeException { public IndexOutOfBoundException() { } public IndexOutOfBoundException(String message) { super(message); }}

还有处理头插和尾插的情况
接着我们再来想，之前我不是说过了单向链表我们不知道前一个节点的地址
因此我们还要写个方法searchIndex获取我们插入下标的前一个节点的地址

//可能还要其他方法来调用这个方法 private LinkNode searchIndex(int index){ int length = size(); if(index <0 || index > length){ throw new IndexOutOfBoundException(\"下标异常\"); } LinkNode currentAdress = headAdress; int count = 0; while (count != index -1){ currentAdress = currentAdress.nextAdress; count++; } return currentAdress; }

在while循环中为什么是减1为终止条件
因为你要赋予下一个节点的地址，相当于新插入节点的前一个节点了
你看，比如我想插入下标为4的地方，那我的循环到下标为2的地方就停住了，然后currentAdress = currentAdress.nextAdress;，此时我currentAdress中存的就是下标为3的地址，不就是我们正要找的吗

我们回到任意位置插入的方法中，找到前一个节点地址后，我们还要判断有没有找到，如果没找到直接返回，如果找到了我们就插入
但是问题是怎么插入呢（我们采用插在我们指定下标的前面）？
我们先定义一个新的节点，接收我们给的数值，然后让我们新的这个节点的nextAdress赋予下一个节点的地址，让新入的节点先和后面节点建立联系
然后通过我们刚刚的找到新入的节点的上一个节点的地址，让上一个节点的,nextAdress赋予我们新插入节点的地址
此时我们新插入的节点就和前面与后面建立了联系，成功插入

@Override public void addIndex(int index, int data) { if(index < 0 || index > size()){ throw new IndexOutOfBoundException(\"数组下标异常\"); } if(index == 0){//头插法 addFirst(data); } if(index == size()){//尾插法 addLast(data); } //正式的任意位置插入数字 LinkNode currentAdress = searchIndex(index); if(currentAdress == null){ return; } LinkNode node = new LinkNode(data); node.nextAdress = currentAdress.nextAdress; currentAdress.nextAdress = node; }

最后我们来测试下目前各个功能是否正常

public static void main(String[] args) { MyLinkList myLinkList = new MyLinkList(); myLinkList.creatListSimple(); System.out.print(\"原本链表：\"); myLinkList.display(); System.out.print(\"求链表个数：\"); System.out.print(myLinkList.size()); System.out.print(\"头插:\"); myLinkList.addFirst(999); myLinkList.display(); System.out.print(\"尾插：\"); myLinkList.addLast(666); myLinkList.display(); System.out.print(\"任意位置插：\"); myLinkList.addIndex(2,888); myLinkList.display(); System.out.print(\"验证数字存在性：888是否存在：\"); System.out.print(myLinkList.contains(888)); System.out.println(); System.out.print(\"最终链表展示：\"); myLinkList.display(); }

打印结果是正常的
硅基计划3.0 学习总结贰顺序表与链表

8. 删除数字第一次出现的节点remove

有了之前的思想，你现在是不是知道饿了，删除节点和增加节点，说白了就是改变节点中地址域的指向，那我们删除节点，可以直接修改地址域的指向，让某个节点不在链表中不就好了吗
你是不是会担心内存没有回收，不用担心，Java的垃圾回收机制非常成熟

好了我们来想如何删除数字第一次出现的节点，那我们要想删除它，是不是要让前一个节点的地址域不再指向这里，而是指向我们要删除的节点的后一个节点呀，那说白了就是前一个节点的nextAdress = 要删除的节点的nextAdress
好现在问题又来了，我们如何去找到我们要删除的节点的前一个节点呢？

那是不是我们要遍历链表，看链表中有没有我们要找的前驱节点，我们一样定义一个临时变量代替头节点去遍历，来我们写个方法findNodePre

private LinkNode findNodePre(int key){ LinkNode current = headAdress; while(current != null){ //表示的是下一个节点的值 if(current.nextAdress.value == key){ //找到了就返回 return current; } //继续下一个节点 current = current.nextAdress; } //找不到就返回空结果 return null; }

好，我们写完遍历找前驱节点后，我们继续想，如果我们删的节点是头节点呢？如果我们直接删，是不是会导致整个链表丢失呢？
所以我们还要判断是头节点的情况，如果是头节点情况，我们直接让头节点的位置给到下一个节点就好了

@Override public void remove(int key) { if(headAdress == null){ return; } if(headAdress.value == key){ headAdress = headAdress.nextAdress; return; } LinkNode previous = findNodePre(key); if(previous == null){ //没找到的情况 return; } LinkNode delete = previous.nextAdress; previous.nextAdress = delete.nextAdress; }

硅基计划3.0 学习总结贰顺序表与链表

9. 删除所有为指定数字的节点removeAllKey

我们刚刚是删除第一个对应数字第一个出现的节点，现在需要删除列表中所有数字为指定值的节点
我们想，我们想如果从前往后遍历一次，用一个变量current代替头节点行动，够吗
显然不够，那我们就要利用双指针法去定义了
我们还是按照刚刚删除一个节点的思路，要想找到我们需要删除的节点，是不是就要找到它的前驱节点，对的，因此我们定义两个“指针”previous和current
好，我们想，当我们在遍历链表的时候，如果current找到了我们要删除的节点，那previous所处的节点（此时是current所处的节点的前一个）
如果不是我们要找的节点，我们的双指针就继续向后遍历
硅基计划3.0 学习总结贰顺序表与链表

@Override public void removeAllKey(int key) { if(headAdress == null){ return; } LinkNode previous = headAdress; LinkNode current = headAdress.nextAdress; while(current != null){ if(current.value == key){ previous.nextAdress = current.nextAdress; current = current.nextAdress; }else{ //找不到就继续向后遍历 previous = current; current = current.nextAdress; } } }

好，我们的代码就真的没有问题了吗
硅基计划3.0 学习总结贰顺序表与链表
我们给到这样的测试用例，发现如果你的列表全都是你要删除的数，最后竟然还剩一个，那就很有意思了，没删干净啊，我们调试看看

我们发现条件判断的是current而非previous，即没有判断第一个是不是指定的值，这样就造成了漏判
那我们是不是想既然头节点也是我们要删的节点，那我们直接让头节点变成下一个节点（因为此时节点只有一个了，头节点赋值为下一个节点相当于直接被null，直接被回收了）
此时我们再测试下代码看看
硅基计划3.0 学习总结贰顺序表与链表
好，删干净了，舒服了

@Override public void removeAllKey(int key) { if(headAdress == null){ return; } LinkNode previous = headAdress; LinkNode current = headAdress.nextAdress; while(current != null){ if(current.value == key){ previous.nextAdress = current.nextAdress; current = current.nextAdress; }else{ //找不到就继续向后遍历 previous = current; current = current.nextAdress; } } //补充头节点漏判的情况 if(headAdress.value == key){ headAdress = headAdress.nextAdress; } }

10. 清空链表

这个我们直接让头节点置为null就好，Java的垃圾回收机制非常成熟，不用担心内存释放的问题

@Override public void clear() { this.headAdress = null; }

11. 小试牛刀

先说明一点，做题网站可能没有调试功能，如果遇到问题需要调试，我们可以自己到编译器上解决

1. 反转链表

题目链接
这道题有迭代和递归两个思路，我们先来讲大家都容易明白的迭代的思路

迭代主要就是采用头插法把链表中除了头节点以外的节点拿进来，一个个往前插入，是不是就正好逆序了
那我们先锚定头节点，待会不要让头节点变化了
锚定好之后我们再让头节点作为新的链表顺序的最后一个节点，破除与后面节点的关系
我们除了定义current中间变量代替头节点行动，因为要交换，我们还要定义一个临时节点去交换值currentNode
对于current就是等于头节点的下一个节点，而currentNode则是current所在节点的下一个节点
然后我们让current中节点域的指向的下一个节点的地址变成头节点的地址，让后让current成为新的头节点此时我们完成了对current所在节点的逆置
然后呢我们就让current变成currentNode，然后此时的currentNode再等于此时current所在的下一个节点，开启下一轮循环
整体流程示意图
硅基计划3.0 学习总结贰顺序表与链表

接着讲递归思路，可能很难懂，毕竟这玩意属实比较抽象
递归终止条件就是当头节点是空的时候就说明压根没有链表，递归啥
如果头节点的地址域即头节点下一个节点是空的时候，说明此时的节点就已经是头节点了，不用再递归了
递归当前的节点，就需要翻转后续的节点，假设总共有K个节点，若当前是递归第一个节点，则要递归k-1个节点，若当前是递归第二个节点，则要递归k-2个节点…
递归一直把头节点的head递归到列表最后，此时开始回归，第一次回归的时候return的newHead得到的值就是0x58，此时head为0x36，然后让0x58中的地址域指向0x36，即代码head.next.next = head
以下是示意图
硅基计划3.0 学习总结贰顺序表与链表

public LinkNode reverseListPlus(LinkNode headAdress) { //没有节点 if(headAdress == null){ return headAdress; } //单个节点 if(headAdress.nextAdress == null){ return headAdress; } LinkNode newHead = reverseListPlus(headAdress.nextAdress); headAdress.nextAdress.nextAdress = headAdress; //防止成环 headAdress.nextAdress = null; //返回后面列表的头节点 return newHead; }

2. 寻找中间节点

如果是奇数个节点就正常返回，如果是偶数个节点就返回中间的第二个节点
题目链接
我先说说一般的思路，我们先求出链表的长度，除以2得到一个结果，然后定义一个临时变量current代替头节点遍历链表，我们让current走的距离等于我们刚刚除以2得出的结果
但是，这样要遍历两遍，那有没有只需要遍历一遍的方法呢？

诶，我们请到了今天的主角，快慢双指针
在奇数个节点的链表中，我们让较快的那个指针每次走两个节点，让慢的那个指针每次走一个节点，当较快的那个指针到达最后一个节点的时候，我们较慢的那个指针也到了我们想要的位置
在偶数个节点之中，我们还是让较快的那个指针每次走两个节点，让慢的那个指针每次走一个节点，当较快的指针中的地址域是空的时候（代表走到了最后一个节点了），此时slow就是我们要找的中间位置

public LinkNode middleNode() { //链表中没有节点的情况 if(headAdress == null){ return headAdress; } //链表中只有一个节点的情况 if(headAdress.nextAdress == null){ return headAdress; } LinkNode fastNode = headAdress; LinkNode slowNode = headAdress; while(fastNode != null && fastNode.nextAdress != null){ //快的指针走两步 fastNode = fastNode.nextAdress.nextAdress; slowNode = slowNode.nextAdress; } return slowNode; }

3. 找到链表中倒数第K个节点

这题常规思路还是先求出链表长度，然后根据倒数第几个节点，定义中间变量current，然后让currrent走上 $链表长度 - k$ 步即可，对应的位置就是要求的节点

但是还是要把链表遍历两次，那有没有一次的呢？有的有的，兄弟有的
还是我们的熟人快慢双指针，只不过这次快慢指针走的步数不一样，你想如果输入倒数第二个节点，那较快的指针只需要在头节点current地方向后走一步就好
如果是倒数第三个节点，走两步，倒数第N个节点，走N-1步
接着再和较慢的指针同时行动，一起向后遍历链表
如果你输入的k值过大，会导致空指针异常（越界了）

public int kthToLast(int k) { if(k <0){ return -1; } LinkNode fastNode = headAdress; LinkNode slowNode = headAdress; int count = 0;//走几步的计数器 //先让较快的指针先走，确定位置 while(count != k-1){ fastNode = fastNode.nextAdress; //处理如果输入的k值过大 //导致球倒数的第几个节点超出了链表范围 if(fastNode == null){ return -1; } count++; } //此时快慢指针一起行动 while(fastNode.nextAdress != null){ fastNode = fastNode.nextAdress; slowNode = slowNode.nextAdress; } //找到了就返回慢指针的对应数值 return slowNode.value; }

4. 链表分割

题目链接
这个题目乍一看很难，起始你理清了思路就会变得相对容易
这个题的意思就是在链表中找到比指定数字小的节点，把它们放在放在比指定数字小的节点的前面，还不能改变顺序
其实你可以这么想，既然我不能改变顺序，那我是不是可以定义两个链表，一个放比指定数字小的节点，一个放其他节点，然后再把它们串起来不就好了吗
好，我们的思路就是定义一个变量current代替头节点遍历链表，小于指定数字的节点放在一个链表中，大于等于的放在另一个链表中
串起来后返回第一个链表的地址（返回存放小的链表的地址）

public LinkNode partition(int x) { //定义第一个节点，存放大于x的值 LinkNode bigLeft = null;//定义头节点 LinkNode bigRight = null;//定义尾节点 //定义第二个节点，存放小于x的值 LinkNode smallLeft = null;//定义头节点 LinkNode smallRight = null;//定义尾节点 LinkNode current = headAdress; while(current != null){ if (current.value < x) { if (smallLeft == null){//要先考虑第一次插入的情况  smallLeft = smallRight = null; }else{  //插入节点  smallRight.nextAdress = current;  //此时尾节点往后移，说明此链表已经插入了一个数字  smallRight= bigRight.nextAdress; } }else{ if(bigLeft == null){//要先考虑第一次插入的情况  bigLeft = bigRight = null; }else{  //插入节点  bigRight.nextAdress = current;  //此时尾节点往后移，说明此链表已经插入了一个数字  bigRight = bigRight.nextAdress; } } //在原链表继续向后遍历 current = current.nextAdress; } smallRight.nextAdress = bigLeft; return smallLeft; }

好，当你满心欢喜运行代码，结果直接报错，直接报空指针异常，为什么呢？
那我问你，你要找比你指定的数要小的，难道就一定有比你数字小的或者是比你数字大的数吗？
不一定，所以我们在最终连接两个链表之前，先看看比指定数字小的链表有没有节点，如果是空则证明没有比你指定数字小的数
好，此时就没问题了吗？不是，还有个很隐蔽的错误
此时你的节点是连接好了，那我问你，你连接好之后的尾节点的地址域是不是空的
下面请看图示
硅基计划3.0 学习总结贰顺序表与链表

5. 有序链表拼接

题目链接
这一题你肯定会这么想，既然是要合并两个有序列表，那我如果假设下面那个链表数字比较大，那我上面那个链表的第一个节点的地址域直接指向下面这个链表的第一个节点不就好了吗
很好，但是你要想，你上面那个链表的后面节点是不是丢失了
硅基计划3.0 学习总结贰顺序表与链表

那要怎么办呢，那我们是不是可以定义一个中间节点，它来帮我们拼接这些节点
我们可以先定义新的头节点newHead，然后定义中间变量temp指向它，代替newHead行动
然后我们就让两个链表各自遍历
如果第一个链表的第一个节点小于第二个链表的第二个节点，那么此时我们就要把第一个链表的第一个节点拿过来，怎么拿？
就是让temp的地址域指向它，然后第一个链表中节点就往后走一个链表一 = 链表一.next，temp向后走
反之就是让temp地址域指向另一个节点，这个链表向后走一个节点，temp向后走
到了最后还要在判断一下，如果一个链表走完了，那另一个链表无需再判断了，剩下的元素一定比当前链表的最大的元素还要大，我们直接链接就好了
硅基计划3.0 学习总结贰顺序表与链表

class Solution { public ListNode mergeTwoLists(ListNode list1, ListNode list2) { //定义傀儡节点 ListNode newHead = new ListNode(); //定义临时节点代替行动 ListNode temp = newHead; while(list1 != null && list2 != null){ if(list1.val < list2.val){ temp.next = list1; //向后走 list1 = list1.next; //临时变量也向后走 }else{ temp.next = list2; list2 = list2.next; } temp = temp.next; } //判空，比如一个列表走完了另一个还没走完 //其实也不用判断了，两个列表比较完了，那剩下列表中数字一定是有序的 //此时temp在list2末尾，只需要把剩下的list1节点连接上就好 if(list1 != null){ temp.next = list1; } //此时temp在list1末尾，只需要把剩下的list2节点连接上就好 if(list2 != null){ temp.next = list2; } return newHead.next; }}

6. 判断回文列表

题目链接
看到还问，可能你就想定义双指针，但是，单向链表是无法定义双指针的，那要怎么办呢
你这样想了，我是不是可以先找到中间节点，然后让中间节点后面的节点逆置，这样就可以定义双指针比较了
如果是偶数个节点，在最后的比较的时候，当我们的头节点的地址域和slow节点的地址域重合的时候，因为前面已经判断是回文了，此时如果满足条件，直接返回true就好

public class PalindromeList { public boolean chkPalindrome(ListNode head) { //先找中间节点 ListNode fast = head; ListNode slow = head; while(fast != null && fast.next != null){ //顺序不可以反，因为偶数个节点会有空指针异常 fast = fast.next.next; slow = slow.next; } //再逆置中间节点之后的节点 //此时slow可以当成新的头节点 ListNode current = slow.next; while(current != null){ //临时节点 ListNode currentNext = current.next; //指向头节点 current.next = slow; //头节点改变 slow = current; //往后走 current = currentNext; } //判断回文，此时slow已经在最右边，可以使用双指针比较 while(head != slow){ //判断不满足回文的情况直接return if(head.val != slow.val){ return false; } //如果是偶数个节点呢 if(head.next == slow){ return true; } head = head.next; slow = slow.next; } //如果循环走完都没见进入if语句，证明确实是回文序列 return true; }}

7. 链表相交

题目链接
现在有个理想情况，假如两个链表都是长度一致的，这样上面链表走一步，下面也走一步，相遇的时候就是公共节点
但是可能两个链表长度不一样，还记得之前求倒数第k个节点的时候，我们让fast指针走几步的方法吗，对，我们现在就是看看两个链表长度差值是多少，这样我们让较长的那个链表的fast指针先走几步，之后在让fast和slow两个指针一起行动，它们相遇的时候就是要的公共节点
好，我们如何确定哪个链表长哪个链表短一点呢？
我们通过长度比较，做差值，当然前提先遍历下链表，看看长度
长度小于0那就把快慢指针交换下，否则我们就让fast和slow指针回到起点
然后让fast走刚刚算出的几步，之后再和slow一起行动，相遇就说明找到了

public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { //此时假设headA是长度较长的链表，headB是长度较短的链表 ListNode fast = headA; ListNode slow = headB; //求长度 int lengthA = 0; int legnthB = 0; //遍历链表 while(fast != null){ lengthA ++; fast = fast.next; } while(slow != null){ legnthB++; slow = slow.next; } //判断哪个链表长 int length = lengthA - legnthB; //此时我们的假设就不成立了，看来是headB链表更长一点 if(length <0){ fast = headB; slow = headA; length = legnthB-lengthA; }else{ //如果是headA链表更长一点 //此时fast和slow走到后面去了，我们要让它们回来 fast = headA; slow = headB; } //我们让长的链表走是上差值长度 while(length != 0){ fast = fast.next; length--; } //再共同行动 while(fast != slow){ fast = fast.next; slow = slow.next; } //但是当你走完了发现链表没有交点，也要判断啊 if(fast == null){ return null; } return fast; }}

8. 判断列表是否有环并求出其入口点

判断是否有环题目链接
判断是否有环并求其入口点题目链接
判断有没有环说白了就是最后一个节点与前面的某些节点相关联
那要怎么才能判定环呢，直接遍历又是死循环，这是典型的追击问题
你看，你成了一个环，那我们可以定义两个快慢指针，快的走两步，慢的走一步，当快的进入环的时候，慢的肯定还没有进来
在最坏的情况下，快的走完一圈了慢的才进来，然后因为它们之间有速度差，当它们相遇的时候就说明有环
否则没有环慢的永远追不上快的

public class Solution { public boolean hasCycle(ListNode head) { ListNode fast = head; ListNode slow = head; //如果链表不循环的话一直让fast走到结尾为止 while(fast != null && fast.next != null){ fast = fast.next.next; slow = slow.next; //判断循环：相遇 if(fast == slow){ return true; } } return false; }}

好，我知道你要说了，那我为什么快的不能走三步呢，诶，你仔细想想，我那个走的快的是不是可能和慢的错过呢
比如你快的走完一圈了，此时慢的也进来了，你们本应该相遇，结果走得快的直接把你跳过了，就错过了见面的机会，其他也是同样道理
但是你说既然快的和慢的差一步，那我能不能快的走三步，慢的走两步呢
诶，你的问题很好，我们来数学分析下
$设： f a s t 步长： 3$ 、 $s l o w 步长： 2$ 、 $则步长差： 1$
$相遇条件：当 s l o w 走了 S 步时， f a s t 走了 (3/2) S 步$ 、 $相遇方程： (3/2) S - S = (1/2) S = k L$

问题
分数步数：S必须是偶数，否则会出现半步步数（现实中不可能）
整数约束：要求 (1/2)S = kL，即 S = 2kL
可能错过：当环长L较小时，可能跳过相遇点

好，我们现在开始找环的入口，怎么找呢？
我们画图来讲解
硅基计划3.0 学习总结贰顺序表与链表
好，我们直接晚上上面那题的代码就好

public class Solution { public ListNode detectCycle(ListNode head) { ListNode fast = head; ListNode slow = head; while(fast != null && fast.next != null) { fast = fast.next.next; slow = slow.next; if(fast == slow) { break;//相遇了直接跳出来 } } //此时快慢指针相遇了，先判断有没有环 if(fast == null || fast.next == null){ return null; } //此时开始是有坏的 fast = head; while(fast != slow){ fast = fast.next; slow = slow.next; } return fast; }}

三、链表LinkList——双向

好我们继续来讲双向链表，双向链表说白了就是在单向链表基础上增加了一个表示上一个节点的地址域，而且除了头节点还有尾节点
以后我用nextAddress称为下一个节点地址域，previousAddress称为上一个节点的地址域
硅基计划3.0 学习总结贰顺序表与链表
好，我们老样子定义外部类MyLinkListPlus，然后定义静态内部类ListNode
还是一样的定义借口然后重写方法

//ILinkPlus借口类public interface ILinkPlus { //头插法 void addFirst(int data); //尾插法 void addLast(int data); //任意位置插⼊,第⼀个数据节点为0号下标 void addIndex(int index,int data); //查找是否包含关键字key是否在单链表当中 boolean contains(int key); //删除第⼀次出现关键字为key的节点 void remove(int key); //删除所有值为key的节点 void removeAllKey(int key); //得到单链表的⻓度 int size(); void display(); void clear();}//MyLinkListPlus类中public class MyLinkListPlus {//双向链表 static class ListNode{ public int value; public ListNode previousAddress;//前驱节点 public ListNode nextAddress;//后继节点 public ListNode(int value) { this.value = value; } } //标记头 public ListNode headAddress; //标记尾 public ListNode lastAddress; @Override public void addFirst(int data) { } @Override public void addLast(int data) { } @Override public void addIndex(int index, int data) { } @Override public boolean contains(int key) { return false; } @Override public void remove(int key) { } @Override public void removeAllKey(int key) { } @Override public int size() { return 0; } @Override public void display() { } @Override public void clear() { }}

好，我们来添加方法

1. 头插法

双向链表头插法跟单向一样，就是改变nextAddress指向的节点，再改变头节点位置，不过还要再把下一个节点的previousAddress加上

 @Override public void addFirst(int data) { //先创造我们的data节点 ListNode node = new ListNode(data); //如果一个节点也没有 if(headAddress == null){ headAddress = node; lastAddress = node; }else{ //三步走：关联头节点后续节点、原头节点前驱节点为新插入的节点 //头节点变成新插入的节点 node.nextAddress = headAddress.nextAddress; headAddress.previousAddress = node; headAddress = node; } }

2. 尾插法

因为是双向的节点，你就不需要再去找尾节点了

@Override public void addLast(int data) { ListNode node = new ListNode(data); //如果一个节点也没有 if(headAddress == null){ headAddress = node; lastAddress = node; }else{ lastAddress.nextAddress = node; node.previousAddress = lastAddress; //尾节点变新插入的节点 lastAddress = node; } }

3. 是否包含指定数字

@Override public boolean contains(int key) { ListNode current = headAddress; while(current != null){ if(current.value == key){ return true; } current = current.nextAddress; } return false; }

4. 求链表长度

@Override public int size() { int count = 0; ListNode current = headAddress; while(current != null){ count++; current = current.nextAddress; } return count; }

5. 打印链表

@Override public void display() { ListNode current = headAddress; while(current != null){ System.out.println(current.value+\" \"); current = current.nextAddress; } }

6. 插入节点到指定位置

这个是示意图
硅基计划3.0 学习总结贰顺序表与链表
因此我们还定义了一个根据下标找对应节点的地址

@Override public void addIndex(int index, int data) { //下标不合法 if(index < 0 || index >size()){ return; } //头插 if(index == 0){ addFirst(data); } //尾插，不用担心越界，因为此时刚好超过了链表末尾的节点一位 if(index == size()){ addLast(data); } //我们得找到对应下标的地址 ListNode current = find(data); ListNode node = new ListNode(data);//新插入的节点 node.nextAddress = current; current.previousAddress.nextAddress = node; node.previousAddress = current.previousAddress; current.previousAddress = node; } private ListNode find(int data){ ListNode current = headAddress; while(current != null){ current = current.nextAddress; data--; } return current; }

7. 删除指定数字第一次出现的节点

@Override public void remove(int key) { ListNode cur = headAddress; while (cur != null) { //如果找到了我们要删除的节点 if(cur.value == key) { //此时是头节点的情况 if(cur == headAddress) {  //头节点后移  headAddress = headAddress.nextAddress;  if(headAddress == null) { //只有一个节点的情况下 lastAddress = null;  }else { //让现在的头节点和原头节点断开联系 headAddress.previousAddress = null;  }  //此时是除头节点以外的情况  }else {  //尾节点情况  if(cur.nextAddress == null) { //让尾节点的上一个节点的下一个地址域置空 cur.previousAddress.nextAddress = cur.nextAddress; //尾节点前移 lastAddress = lastAddress.previousAddress;  }else { //切断当前节点与任意节点的联系 cur.previousAddress.nextAddress = cur.nextAddress; cur.nextAddress.previousAddress = cur.previousAddress;  } } return; } cur = cur.nextAddress; } }

8. 删除指定数字全部节点

我们刚刚是删了第一次，那我们循环就不用return了，直接让它删完不就行了吗

@Override public void removeAllKey(int key) { ListNode cur = headAddress; while (cur != null) { //如果找到了我们要删除的节点 if(cur.value == key) { //此时是头节点的情况 if(cur == headAddress) {  //头节点后移  headAddress = headAddress.nextAddress;  if(headAddress == null) { //只有一个节点的情况下 lastAddress = null;  }else { //让现在的头节点和原头节点断开联系 headAddress.previousAddress = null;  }  //此时是除头节点以外的情况 }else {  //尾节点情况  if(cur.nextAddress == null) { //让尾节点的上一个节点的下一个地址域置空 cur.previousAddress.nextAddress = cur.nextAddress; //尾节点前移 lastAddress = lastAddress.previousAddress;  }else { //切断当前节点与任意节点的联系 cur.previousAddress.nextAddress = cur.nextAddress; cur.nextAddress.previousAddress = cur.previousAddress;  } } //不用return，找到第一次出现的节点我们就继续删 //return; } cur = cur.nextAddress; } }

9. 清空链表

我猜你肯定会这么想，我直接头和尾置为null，反正Java会垃圾回收
但是这么做不专业，其实应该要把每个节点置为null

@Override public void clear() { ListNode current = headAddress; while(current != null){ ListNode currentNext = current.nextAddress; current.previousAddress = null; current.nextAddress = null; //如果是引用类型，不要忘记把值域也置为null //current.val = null; current = currentNext; } //此时只剩下一个节点 headAddress = null; lastAddress = null; }

10. 测试功能的代码用例

public static void main(String[] args) { MyLinkList myLinkList = new MyLinkList(); System.out.println(\"头插和尾插测试\"); myLinkList.addFirst(10); myLinkList.addFirst(15); myLinkList.addLast(22); myLinkList.addLast(30); myLinkList.addLast(30); myLinkList.display(); System.out.println(); System.out.println(\"===指定位置插入测试===\"); myLinkList.addIndex(2,15); myLinkList.display(); System.out.println(); System.out.println(\"===是否包含数字测试===\"); System.out.println(myLinkList.contains(15)); System.out.println(myLinkList.contains(25)); System.out.println(\"===删除数字第一次出现的节点测试===\"); myLinkList.remove(15); myLinkList.display(); System.out.println(); System.out.println(\"===删除数字的所有出现的节点测试===\"); myLinkList.removeAllKey(30); myLinkList.display(); System.out.println(); System.out.println(\"===求链表长度和清空链表测试===\"); System.out.println(myLinkList.size()); myLinkList.clear(); myLinkList.display(); System.out.println(); }

硅基计划3.0 学习总结贰顺序表与链表
看来功能一切正常，完毕

11. Java官方提供LinkedList类

我们查看这个类的源码，发现其实现了Deque借和List接口，而Deque借口就是我们下个文章要讲的栈和队列
但是这也就说明了LinkedList不支持随机访问，需要遍历链表去访问指定元素（除头尾）

LinkedList类中有很多方法
而我们熟知的add方法默认是尾插法
indexOf返回的是第一次出现指定数字的地址
lastIndexOf则是返回的是最后一次出现指定数字的地址
addAll则代表可以插入另一个链表中的元素（俗称不同链表之间的相互连接）
subList同样是截取和LinkList单向链表差不多
我们看到双向链表中有个带一个参数构造方法，发现跟LinkList类一样，可以用一个链表集合构造另一个链表集合
以下是一些测试用例

public static void main(String[] args) { LinkedList <Integer> linkedList1 = new LinkedList<>(); System.out.println(\"尾插法：\"); linkedList1.add(10); linkedList1.add(15); linkedList1.add(25); linkedList1.add(15); System.out.println(\"链表打印：\"+\"\\n\"+linkedList1); System.out.println(\"第一次出现的下标：\"+\"\\n\"+linkedList1.indexOf(15)); System.out.println(\"最后一次出现的下标：\"+\"\\n\"+linkedList1.lastIndexOf(15)); System.out.print(linkedList1); LinkedList <Integer> linkedList2 = new LinkedList<>(linkedList1); System.out.print(\"||||\"); linkedList2.add(999); linkedList2.add(888); System.out.print(\"链接上面那个链表后：\"+linkedList2); }

打印的结果就是这样的
硅基计划3.0 学习总结贰顺序表与链表

好，我们再来遍历链表，一样的，直接打印（内部有重写toString方法），循环遍历，强遍历，迭代器，链表迭代器，倒着遍历等等都可以

System.out.println(\"===以下是遍历代码实现===\"); System.out.println(\"直接打印：\"+linkedList2); //循环 for (int i = 0; i < linkedList2.size(); i++) { System.out.print(linkedList2.get(i)+\" \"); } System.out.println(); //强遍历，用int也可以，会自动拆箱 for (Integer x : linkedList2){ System.out.print(x+\" \"); } System.out.println(); //迭代器 Iterator <Integer> it = linkedList2.iterator(); while(it.hasNext()){ System.out.print(it.next()+\" \"); } System.out.println(); //链表迭代器 ListIterator <Integer> listIterator = linkedList2.listIterator(); while(listIterator.hasNext()){ System.out.print(listIterator.next()+\" \"); } System.out.println(); //倒着遍历 while(listIterator.hasPrevious()){ System.out.print(listIterator.previous()+\" \"); }

硅基计划3.0 学习总结贰顺序表与链表
但是由于链表它插入和删除无需移动元素，因此如果需要频繁更新数据则可以使用链表
个人认为否则还是建议选顺序表，毕竟顺序表在内存中都是连续的，方便查找

文章错误不可避免，期待您的指正，我们共同进步

Git码云仓库链接

END

硅基计划3.0 学习总结 贰 顺序表与链表

文章目录

一、顺序表——ArrayList

1. 实现自己MyArrayList

1. 实现add基础方法

2. 实现指定位置加元素add方法

3. 完善数组打印方法display

4. 完善根据下标找元素get

5. 完善判断数字是否在数组中contains

6. 根据数字找下标indexOf

7. 更新指定下标元素set

8. 获取数组有效长度size

9. 清空数组clear

10. 指定数字删除

2. 使用ArrayList

3. 遍历ArrayList

4. 练练手

1. 杨辉三角

2. 简易牌组游戏

5. 小结

二、链表LinkList——单向

1. 创造链表creatList

2. 遍历链表display

3. 获取链表长度sieze

4. 遍历链表寻找数字是否存在contains

5. 头插法插入数字addFirst

6. 尾插法插入数字addLast

7. 任意位置插入

8. 删除数字第一次出现的节点remove

9. 删除所有为指定数字的节点removeAllKey

10. 清空链表

11. 小试牛刀

1. 反转链表

2. 寻找中间节点

3. 找到链表中倒数第K个节点

4. 链表分割

5. 有序链表拼接

6. 判断回文列表

7. 链表相交

8. 判断列表是否有环并求出其入口点

三、链表LinkList——双向

1. 头插法

2. 尾插法

3. 是否包含指定数字

4. 求链表长度

5. 打印链表

6. 插入节点到指定位置

7. 删除指定数字第一次出现的节点

8. 删除指定数字全部节点

9. 清空链表

10. 测试功能的代码用例

11. Java官方提供LinkedList类

相关问题

公告

DeepSeek全套部署资料免费下载

免费可商用字体批量下载

硅基计划3.0 学习总结贰顺序表与链表