看完这篇，你也可以手撕链表

一、链表概念及其结构

1.1 链表和数组的区别

链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的 。

数组是两个元素在物理结构上紧紧相连

1.2 单向链表定义

链表属性定义

head：头节点
size：当前链表中包含的节点个数

每—列火车由若干个车厢组成，每个车厢就是一个Node对象，由多个Node对象组成的大实体就是链表对象。

/**
* 基于整形的单链表
* */
public class singleLinkList {
   
    //单链表头节点
    private Node head;
    //当前节点个数=有效数值的个数
    private int size;
    }
1
2
3
4
5
6
7
8
9
10

节点属性定义

val：当前节点保存的数据
next：保存下一个节点的地址

/**
 * 单链表具体的每个节点
 */
class Node {
   
    int val;//每个结点的值
    Node next;//当前节点指向下一个节点的地址
    }
1
2
3
4
5
6
7
8

二、单链表的基本操作（无虚拟头节点）

2.1 头插法

具体步骤：
1.创建新节点，并给新节点赋值
2.第一种情况：如果链表中没有头节点，新节点就是头节点，head=newNode
3.第二种情况：链表中存在头节点，需要先newNode.next=head，然后再进行head=newNode，这两个操作的顺序很重要，不可以颠倒

代码如下（示例）：

/**
     * 向当前链表插入新节点 - 头插法
     * @param val
     */
    public void addFirst(int val){
   
        Node newNode=new Node(val);
        if(head!=null){
   
            newNode.next=head;
        }
        head=newNode;
        size++;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

无论单链表最后是否为空，新节点都是单链表头插法后新的头节点head=node

2.2 遍历链表

从当前头节点开始，依次取出每个节点值，然后通过next引用走到下一个节点，直到走到链表的末尾(next = null)

head头节点是否可以遍历链表

不可以。直接使用head引用，遍历一次链表之后，链表就丢了。所以要使用一个临时变量，暂存head的值。只要拿到链表头节点就一定可以遍历整个链表。

代码如下（示例）：

/**
     * 单链表的打印方法
     * @return
     */
    public String toString(){
   
        String str="";
        Node x=head;
        while (x!=null){
   
            str+=x.val;
            str+="->";
            x=x.next;
        }
        str+="Null";
        return str;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

也可以使用for循环遍历：

2.3 在index索引处插入新元素val

核心操作：找待插入位置的前驱节点

找到前驱节点后，操作1和操作2的顺序如何？能否颠倒？
操作顺序为先2后1，不可以颠倒顺序，如果先1后2，新创建的节点又是自己连接自己。

单链表的插入和删除，最核心的就是在找前驱结点，因为链表只能从前向后操作。但是链表中的头节点很特殊，只有头节点没有前驱节点。

易错点：

1.前驱节点prev要走的步数：找到待插入位置的前驱就是让prev引用从头结点开始先后走index -1步恰好就走到前驱结点(带入具体实例即可求出）

2.index索引指的是，新节点插入后的索引值就是index

/**
     * 在单链表的任意索引位置插入新元素val
     * @param index
     */
    public void add(int index,int val){
   
        //1.判断插入索引index的合法性
        //==size就相当于尾插法
        if(index<0||index>size){
   
            System.err.println("index is illegal");
        }
        //2.找前驱节点
        //头节点需要特殊处理，头节点不存在前驱节点,直接头插法
        if(index==0){
   
            addFirst(val);
        }else{
   
            //3.索引位置合法，且不是头节点，找到相应的前驱节点
            //前驱节点从头开始遍历
            Node prev=head;
            //创建待插入新节点
            Node newNode=new Node(val);
            //index - 1需要通过画图求解
            for (int i = 0; i <index-1 ; i++) {
   
                prev=prev.next;
            }
            //此时prev已经走到待插入index的前驱节点
            newNode.next=prev.next;
            prev.next=newNode;
            size++;
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

额外知识点：面向对象的优点

链表和数组的add方法名使用规则完全相同，只需更改类就可以实现链表到数组的转换

2.4 尾插法

所有的尾插法都是在index为size的位置插入元素

//尾插法
    public void addLast(int val){
   
    //直接复用在index位置插入元素的办法
        addIndex(size,val);
    }
1
2
3
4
5
6

2.5 查询

查询第一个值为val的索引

/**
     * 查询第一个值为val元素的索引
     * @return
     */
    public int getByVal(int val){
   
        int index=0;
        //遍历链表的方法
        for (Node x=head;x!=null;x=x.next){
   
            if(x.val==val){
   
                return index;
            }
            index++;
        }
        //for循环之后没有返回相应的index，说明不存在val
        //返回一个非法索引下标
        return -1;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

判断链表中枢否存在值为val元素

/**
     * 判断链表中是否包含值为val元素
     * @param val
     * @return
     */
    public boolean contains(int val){
   
        int index=getByVal(val);
        return index!=-1;
    }
1
2
3
4
5
6
7
8
9
10

不借助方法也可以判断：直接for循环遍历链表，如果node.val==val就return true否则return false

查询索引为index的节点val

任何牵扯到index的方法都需要判断index的合法性

/**
     * index合法性判断
     * @param index
     * @return
     */
    private boolean rangeCheck(int index) {
   
        if(index<0||index>size){
   
            return false;
        }
        return true;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13

根据索引index的值，查询index位置元素的val值

/**
     * 根据索引index返回相应的val
     * @param index
     * @return
     */
    public int get(int index){
   
        if(rangeCheck(index)){
   
            Node x=head;
            for (int i = 0; i < index; i++) {
   
                x=x.next;
            }
            return x.val;
        }
        return -1;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

2.6 修改

/**
     * 修改index位置val为newVal，并放回修改前的val值
     * @param index
     * @param newVal
     * @return
     */
    public int set(int index,int newVal){
   
        if(rangeCheck(index)){
   
            Node x=head;
            for (int i = 0; i < index; i++) {
   
                x=x.next;
            }
            int oldVal=x.val;
            x.val=newVal;
            return oldVal;
        }
        System.err.println("index is illegal!set error");
        return -1;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

2.7 删除（重点）

删除核心操作：找前驱

操作1和2不能颠倒顺序

头节点需要特殊处理：头节点没有前驱
一个对象只有没有被任何引用指向，才能被JVM回收

删除索引为index的val

/**
     * 删除index位置节点，并返回该节点val
     * @param index
     * @return
     */
    public int remove(int index){
   
        if(rangeCheck(index)){
   
            //特殊处理：头删
            if(index==0){
   
                Node x=head;
                head=head.next;
                x.next=null;
                return x.val;
            }else{
   
                //删除中间节点
                //找前驱
                Node prev=head;
                for (int i = 0; i < index-1 ; i++) {
   
                    prev=prev.next;
                }
                //此时prev位于待删除节点的前驱
                Node node=prev.next;
                prev.next=node.next;
                node.next=null;
                size--;
                return node.val;
            }
        }
        System.err.println("index is illegal!remove error");
        return -1;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

node=null和node.next=null

node=null不等于node.next=null

node==null，node中包含的next引用还存在，就是图中的连线

删除第一次出现val的元素（考虑边界）

头节点需要特殊处理：

前驱节点一定不是待删除节点，在保证prev！=null的前提下，还需要保证prev.next！=null，因为我们需要判断的是prev.next.val是否为待删除节点，如果不保证prev.next！=null就可能出现空指针异常的情况！

/**
     * 删除链表中第一次出现val的节点
     * @param val
     */
    
1
2
3
4