0%

Java算法与数据结构之链表

发表于 更新于 分类于
本文字数： 10k 阅读时长 ≈ 10 分钟

链表

一、链表介绍

  1. 链表是以节点的方式来存储,是链式存储
  2. 每个节点包含 data 域， next 域：指向下一个节点.
  3. 如图：发现链表的各个节点不一定是连续存储.
  4. 链表分带头节点的链表和没有头节点的链表，根据实际的需求来确定

单链表

链表通过指针将一组零散的内存块串联在一起，内存块称为链表的“结点”。每个链表的结点除了存储数据之外，还需要记录链上的下一个结点的地址，叫作后继指针 next。链表有两个特殊的结点，分别是第一个结点（头结点）和最后一个结点（尾结点）。头结点用来记录链表的基地址，用它可以遍历得到整条链表。尾结点指向一个空地址 NULL，表示这是链表上最后一个结点。

双向链表

双向链表支持两个方向，每个结点同时有后继指针 next 指向后面的结点，还有一个前驱指针 pre 指向前面的结点。双向链表需要额外的两个空间来存储后继结点和前驱结点的地址，存储同样的数据，双向链表要比单链表占用更多的内存空间。

循环链表

循环链表跟单链表的区在尾结点指针是指向链表的头结点。和单链表相比，循环链表的优点是从链尾到链头比较方便。当要处理的数据具有环型结构特点时，采用循环链表实现代码会简洁很多。

内存结构图

单链表(带头结点) 逻辑结构图

二、单链表应用实例

使用head头的单链表实现对水浒传英雄的增删改查等操作

测试类

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
public class SingleLinkedListDemo {
    public static void main(String[] args) {
        //进行测试
        //创建节点
        HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
        HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟");
        HeroNode hero3 = new HeroNode(3, "吴用", "智多星");
        HeroNode hero4 = new HeroNode(4, "林冲", "豹子头");

        //创建
        SingleLinkedList singleLinkedList = new SingleLinkedList();
//        singleLinkedList.add(hero1);
//        singleLinkedList.add(hero2);
//        singleLinkedList.add(hero3);
//        singleLinkedList.add(hero4);

        //根据编号顺序添加
        singleLinkedList.addByOrder(hero1);
        singleLinkedList.addByOrder(hero4);
        singleLinkedList.addByOrder(hero3);
        singleLinkedList.addByOrder(hero2);

        singleLinkedList.list();
        //测试修改节点的代码
        System.out.println("修改2号：");
        HeroNode newHeroNode = new HeroNode(2, "小卢", "玉麒麟。。。");
        singleLinkedList.update(newHeroNode);
        //显示
        System.out.println("修改后情况！");
        singleLinkedList.list();

        //删除一个节点
        System.out.println("删除1号：");
        singleLinkedList.delete(1);
        System.out.println("删除后的链表情况");
        singleLinkedList.list();
    }
}

（1）添加节点

第一种方式，直接添加到链表的尾部

第二种方式，插入节点，可以根据排名插入到指定位置

思路：

  1. 需要按照编号的顺序添加
  2. 首先找到新添加的节点的位置, 是通过辅助变量(指针), 通过遍历来搞定
  3. newNode.next = temp.next
  4. 将temp.next = newNode

（2）删除节点

思路：

  1. 我们先找到 需要删除的这个节点的前一个节点 temp
  2. temp.next = temp.next.next
  3. 被删除的节点，将不会有其它引用指向，会被垃圾回收机制回收

（3）修改节点

思路：

  1. 通过遍历找到该节点，然后直接重新赋值
  2. temp.data= newNode.data

（4）查询节点

链表的随机访问第 k 个元素，必须根据指针一个结点一个结点地依次遍历，直到找到相应的结点。

详细代码如下：

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
//定义一个SingleLinkedList 管理我们的英雄
class SingleLinkedList {
    //先初始化一个头节点， 头节点不要动, 不存放具体数据
    private HeroNode head = new HeroNode(0, "", "");

    //添加节点到单项链表
    //思路，当不考虑编号顺序时
    //1.找到当前链表的最后节点
    //2.将最后这个节点的next 指向 新的节点
    public void add(HeroNode heroNode) {

        //head节点不能动，因此需要一个辅助遍历temp
        HeroNode temp = head;
        //遍历链表，找到最后
        while (true) {
            //找到链表最后
            if (temp.next == null) {
                break;
            }
            //如果没有找到就把temp后移
            temp = temp.next;
        }
        //当退出while循环时，temp就指向了链表的最后
        //将最后这个节点的next 指向 新的节点
        temp.next = heroNode;
    }

    //第二种方式在添加英雄时，根据排名将英雄插入到指定位置(如果有这个排名，则添加失败，并给出提示)
    public void addByOrder (HeroNode heroNode) {
        //通过一个辅助指针来帮助找到添加的位置
        //因为单链表，因为我们找的temp是位于添加位置的前一个节点，否则插入不了
        HeroNode temp = head;
        boolean flag = false;//标志添加的编号是否存在
        while (true) {
            if (temp.next == null) { //说明temp已经在链表最后
                break;
            }
            if (temp.next.no > heroNode.no) { //位置找到，就在temp的后面插入
                break;
            } else if (temp.next.no == heroNode.no) { //添加的编号存在
                flag = true; //编号存在
                break;
            }
            temp = temp.next;
        }
        //判断flag的值
        if (flag) {
            //编号存在，不能添加
            System.out.println("准备插入的编号" + heroNode.no +"已经存在了");
        } else {
            //插入到链表中，temp的后面
            heroNode.next = temp.next;
            temp.next = heroNode;
        }
    }

    //修改节点的信息，根据no编号来修改
    //
    public void update(HeroNode newHeroNode) {
        //判断链表是否为空
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }
        //找到需要修改的节点
        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.println("没有找到编号为" +newHeroNode.no + "的节点");
        }

    }

    //删除节点
    //思路
    //1.head 节点不动，需要一个temp辅助节点，找到待删除节点的前一个节点
    //2.说明我们在比较时，是temp.next.no和待删除的节点的no比较
    public void delete(int no) {
        HeroNode temp = head;
        boolean flag = false;
        while (true) {
            if (temp.next == null) {
                break;
            }
            if (temp.next.no == no) {
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag) {
            temp.next = temp.next.next;
        }else {
            System.out.println("要删除的"+ no +"这个节点不存在");
        }
    }

    //显示链表
    public void list() {
        //判断链表是否为空
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }
        //因为头节点不能动，所以需要一个辅助遍历temp
        HeroNode temp = head.next;
        while (true) {
            if (temp == null) {
                break;
            }
            //输出节点信息
            System.out.println(temp);
            //将next后移
            temp = temp.next;
        }
    }
}

//定义HeroNode，每个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;
    }
    //重写toString
    @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
HeroNode [no = 1, name = 宋江, nickname = 及时雨]
HeroNode [no = 2, name = 卢俊义, nickname = 玉麒麟]
HeroNode [no = 3, name = 吴用, nickname = 智多星]
HeroNode [no = 4, name = 林冲, nickname = 豹子头]
修改2号：
修改后情况！
HeroNode [no = 1, name = 宋江, nickname = 及时雨]
HeroNode [no = 2, name = 卢, nickname = 玉麒麟]
HeroNode [no = 3, name = 吴用, nickname = 智多星]
HeroNode [no = 4, name = 林冲, nickname = 豹子头]
删除1号
删除后的链表情况
HeroNode [no = 2, name = 卢, nickname = 玉麒麟]
HeroNode [no = 3, name = 吴用, nickname = 智多星]
HeroNode [no = 4, name = 林冲, nickname = 豹子头]

三、双链表应用实例

（1）添加节点

第一种方式，添加到尾部

思路：

  1. 先找到双向链表的最后这个节点temp
  2. temp.next = newNode
  3. newNode.pre = temp;

第二种方式，插入节点，可以根据排名插入到指定位置

思路：

  1. 需要按照编号的顺序添加

  2. 首先找到新添加的节点的位置, 是通过辅助变量(指针), 通过遍历来搞定

👉需要注意下面代码的先后顺序

1
2
3
4
5
6
newNode.next = temp.next;
   if (temp.next != null) {
      temp.next.pre = newNode;
   }
   temp.next = newNode;
   newNode.pre = temp;

（2）删除节点

思路：

  1. 因为是双向链表，因此，我们可以实现自我删除某个节点
  2. 直接找到要删除的这个节点，比如temp
  3. temp.pre.next = temp.next
  4. temp.next.pre = temp.pre;

（3）修改节点

👉双链表修改节点思路和单链表思路一样

（4）遍历节点

👉遍历方式和单链表一样，可以向前遍历也可以向后遍历

代码实现如下：

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
public class DoubleLinkedListDemo {
    public static void main(String[] args) {
        System.out.println("双向链表");
        //创建节点
        HeroNode2 hero1 = new HeroNode2(1, "宋江", "及时雨");
        HeroNode2 hero2 = new HeroNode2(2, "卢俊义", "玉麒麟");
        HeroNode2 hero3 = new HeroNode2(3, "吴用", "智多星");
        HeroNode2 hero4 = new HeroNode2(4, "林冲", "豹子头");

        DoubleLinkedList doubleLinkedList = new DoubleLinkedList();
//        doubleLinkedList.add(hero1);
//        doubleLinkedList.add(hero2);
//        doubleLinkedList.add(hero3);
//        doubleLinkedList.add(hero4);

        //根据编号顺序添加
        doubleLinkedList.addByOrder(hero1);
        doubleLinkedList.addByOrder(hero4);
        doubleLinkedList.addByOrder(hero3);
        doubleLinkedList.addByOrder(hero2);
        doubleLinkedList.list();

        System.out.println("修改4号");
        HeroNode2 newHeroNode = new HeroNode2(4, "林冲...", "豹子...");
        doubleLinkedList.update(newHeroNode);
        System.out.println("修改后：");
        doubleLinkedList.list();

        System.out.println("删除吴用");
        doubleLinkedList.delete(3);
        System.out.println("删除后：");
        doubleLinkedList.list();
    }
}

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

    public HeroNode2 getHead() {
        return head;
    }

    //添加一个节点到双向链表的最后
    public void add(HeroNode2 heroNode) {

        //head节点不能动，因此需要一个辅助遍历temp
        HeroNode2 temp = head;
        //遍历链表，找到最后
        while (true) {
            //找到链表最后
            if (temp.next == null) {
                break;
            }
            //如果没有找到就把temp后移
            temp = temp.next;
        }
        //当退出while循环时，temp就指向了链表的最后
        //形成一个双向链表
        temp.next = heroNode;
        heroNode.pre = temp;
    }

    //第二种方式在添加英雄时，根据排名将英雄插入到指定位置(如果有这个排名，则添加失败，并给出提示)
    public void addByOrder (HeroNode2 heroNode) {
        //通过一个辅助指针来帮助找到添加的位置
        //因为单链表，因为我们找的temp是位于添加位置的前一个节点，否则插入不了
        HeroNode2 temp = head;
        boolean flag = false;//标志添加的编号是否存在
        while (true) {
            if (temp.next == null) { //说明temp已经在链表最后
                break;
            }
            if (temp.next.no > heroNode.no) { //位置找到，就在temp的后面插入
                break;
            } else if (temp.next.no == heroNode.no) { //添加的编号存在
                flag = true; //编号存在
                break;
            }
            temp = temp.next;
        }
        //判断flag的值
        if (flag) {
            //编号存在，不能添加
            System.out.println("准备插入的编号" + heroNode.no +"已经存在了");
        } else {
            //插入到链表中，temp的后面
            //这里格外要注意下面的先后顺序
            heroNode.next = temp.next;
            if (temp.next != null) {
                temp.next.pre = heroNode;
            }
            temp.next = heroNode;
            heroNode.pre = temp;
        }
    }


    //修改节点的信息，根据no编号来修改，和单项链表一样
    public void update(HeroNode2 newHeroNode) {
        //判断链表是否为空
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }
        //找到需要修改的节点
        HeroNode2 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.println("没有找到编号为" +newHeroNode.no + "的节点");
        }

    }

    //删除节点
    //思路
    // 1. 因为是双向链表，因此，我们可以实现自我删除某个节点
    //2. 直接找到要删除的这个节点，比如temp
    //3. temp.pre.next = temp.next
    //4. temp.next.pre = temp.pre;
    public void delete(int no) {
        if (head.next == null) {
            System.out.println("链表为空，无法删除");
            return;
        }
        HeroNode2 temp = head.next; //辅助变量
        boolean flag = false;
        while (true) {
            if (temp == null) {
                break;
            }
            if (temp.no == no) {
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag) {
            temp.pre.next = temp.next;
            //如果是最后一个节点，就不需要执行下面这句话，否则出现空指针
            if (temp.next != null) {
                temp.next.pre = temp.pre;
            }
        }else {
            System.out.println("要删除的"+ no +"这个节点不存在");
        }
    }

    //显示链表,遍历链表
    public void list() {
        //判断链表是否为空
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }
        //因为头节点不能动，所以需要一个辅助遍历temp
        HeroNode2 temp = head.next;
        while (true) {
            if (temp == null) {
                break;
            }
            //输出节点信息
            System.out.println(temp);
            //将next后移
            temp = temp.next;
        }
    }
}

//定义HeroNode2，每个HeroNode 对象就是一个节点
class HeroNode2 {
    public int no;
    public String name;
    public String nickname;
    public HeroNode2 next; //指向下一个节点
    public HeroNode2 pre; //指向前一个节点

    //构造器
    public HeroNode2 (int no, String name, String nickname) {
        this.no = no;
        this.name = name;
        this.nickname = nickname;
    }
    //重写toString
    @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
双向链表
HeroNode [no = 1, name = 宋江, nickname = 及时雨]
HeroNode [no = 2, name = 卢俊义, nickname = 玉麒麟]
HeroNode [no = 3, name = 吴用, nickname = 智多星]
HeroNode [no = 4, name = 林冲, nickname = 豹子头]
修改4号
修改后：
HeroNode [no = 1, name = 宋江, nickname = 及时雨]
HeroNode [no = 2, name = 卢俊义, nickname = 玉麒麟]
HeroNode [no = 3, name = 吴用, nickname = 智多星]
HeroNode [no = 4, name = 林冲..., nickname = 豹子...]
删除吴用
删除后：
HeroNode [no = 1, name = 宋江, nickname = 及时雨]
HeroNode [no = 2, name = 卢俊义, nickname = 玉麒麟]
HeroNode [no = 4, name = 林冲..., nickname = 豹子...]

四、单向环形链表应用场景

Josephu（约瑟夫、约瑟夫环）问题

详细可以看这篇

单向环形链表和Josephu

加油！！！😘😘

北以晨光 wechat
欢迎您扫一扫上面的微信公众号，订阅我的博客！
------ 本文结束感谢您的阅读 ------
相关文章