链表【Linked List】

1、链表介绍

链表是有序的列表，但是它在内存中是存储如下：

小结：
1）链表是以节点的方式来存储
2）每个节点包含data域，next域：指向下一个节点
3）链表的各个节点不一定是连续存储的

1.1 单链表介绍

单链表（带头节点）逻辑结构示意图：

创建节点HeroNode节点类

/**
 * 英雄类
 */
class HeroNode {
    public int no;
    public String name;
    public String nickName;
    public HeroNode next;

    public HeroNode(int no, String name, String nickName) {
        this.no = no;
        this.name = name;
        this.nickName = nickName;
    }

    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickName='" + nickName + '\'' +
                '}';
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

1.1.1 新增节点

思路：新增节点到链表时，首先需要找到链表的最后一个节点，即最后一个节点.next = null，找到后再将数据添加进来

class SingleLinkedList{
    // 先初始化一个头节点，不存放具体数据
    private HeroNode head = new HeroNode(0,"","");

    /**
     * 添加逻辑：
     * 1.首先找到链表next=null的节点
     *
     * @param heroNode
     */
    public void add(HeroNode heroNode) {
        // 临时变量
        HeroNode temp = head;
        while (true) {
            if (temp.next == null) {
                break;
            }
            // 如果没有找到，temp后移
            temp = temp.next;
        }
        temp.next = heroNode;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

1.1.2 新增到链表中的数据为有序不可重复数据

/**
     * 添加到队列中的位置是有序的
     * 1、首先找到新添加的节点的位置，是通过辅助变量（指针）
     * 2、新的节点.next = temp.next
     * 3、将temp.next = 新节点
     *
     * @param heroNode
     */
    public void addbyOrder(HeroNode heroNode) {
        // 因为单链表，找的temp是位于添加位置的前一个节点，否则插入不了
        HeroNode temp = head;
        // 标识添加的编号是否存在，默认为false
        boolean flag = false;
        while (true) {
            if (temp.next == null) {
                // 说明temp已在链表最后
                break;
            }
            if (temp.next.no > heroNode.no) {
                // 找到temp下一个节点与需要插入的节点的no进行比较大小，如果大于，则找到插入的位置【在temp节点的后面】
                break;
            }
            if (temp.next.no == heroNode.no) {
                // 如果temp的下一个节点的编号与需要插入的编号相等，说明需要添加的数据已存在，则不能再添加
                flag = true;
                break;
            }
            // 如果没有找到，则需要向后移动，遍历当前链表
            temp = temp.next;
        }

        if (flag) {
            System.out.printf("需要插入的编号%d 数据已存在，不能添加\n", heroNode.no);
        } else {
            heroNode.next = temp.next;
            temp.next = heroNode;
        }
    }
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
37
38

1.1.3 遍历链表

/**
     * 显示链表数据
     */
    public void list() {
        // 判断链表是否为空
        if (head.next == null) {
            System.out.println("链表为空~");
            return;
        }
        /**
         * 遍历逻辑：
         * 1、从头节点开始
         */
        HeroNode temp = head.next;
        while (true){
            if(temp == null){
                break;
            }
            System.out.println(temp);
            temp = temp.next;
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

1.1.4 通过编号修改

/**
     * 修改节点信息
     *
     * @param newHeroNode
     */
    public void update(HeroNode newHeroNode) {
        HeroNode temp = head.next;
        boolean flag = false;
        while (true) {
            if (temp == null) {
                // 说明链表已经遍历完了
                break;
            }
            if (temp.no == newHeroNode.no) {
                // 说明需要修改的数据已经找到
                flag = true;
                break;
            }
            temp = temp.next;
        }

        if (flag) {
            // 需要修改的数据已经找到
            temp.name = newHeroNode.name;
            temp.nickName = newHeroNode.nickName;
        } else {
            System.out.printf("需要修改的数据编号%d没有找到\n", newHeroNode.no);
        }
    }
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

1.1.5 通过编号删除

/**
     * 根据编号删除指定数据
     *
     * @param no
     */
    public void del(int no) {
        HeroNode temp = head.next;
        boolean flag = false;
        while (true) {
            if (temp == null) {
                // 链表已经遍历完了
                break;
            }
            if (temp.next.no == no) {
                // 说明已经找到需要删除节点的前一个节点
                flag = true;
                break;
            }
            temp = temp.next;
        }

        if (flag) {
            temp.next = temp.next.next;
        } else {
            System.out.printf("需要删除的数据编号%d没有找到\n", no);
        }
    }
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

单链表面试题

1、计算链表中的有效节点个数

/**
     * 计算链表中的有效节点个数
     *
     * @param singleLinkedList
     * @return
     */
    public static int getSize(SingleLinkedList singleLinkedList) {
        int size = 0;
        HeroNode temp = singleLinkedList.getHead();
        while (true) {
            if (temp.next == null) {
                break;
            }
            size++;
            temp = temp.next;
        }
        return size;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

2、查询单向链表的倒数第k个节点

/**
     * 查询单向链表的倒数第k个节点
     * 思路：
     * 1、思考倒数第k个节点，有效节点数 - k
     * 2、找到正数位置后，从头节点的下一个节点开始遍历查找
     */
    public static HeroNode getHeroNodeByIndex(SingleLinkedList singleLinkedList, int index) {
        // 找到链表的头节点
        HeroNode head = singleLinkedList.getHead();
        if (head.next == null) {
            System.out.println("链表为空");
            return null;
        }
        HeroNode cur = head.next;
        // 链表的有效节点数
        int size = getSize(singleLinkedList);
        for (int i = 0; i < size - index; i++) {
            cur = cur.next;
        }
        return cur;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21