【数据结构与算法】详解单向无头非循环链表的基本操作

链表的概念

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。

链表的种类

链表的种类有很多，常见的链表结构有单向和双向，循环和非循环，带头节点和不带头节点这几种结构，把这些结构组合一下就有8种链表结构，这些不要求全部掌握，我们只需要掌握单向非循环不带头结点的链表，并且了解双向非循环不带头节点的链表这两种即可。什么
因此，接下来就来实现单向非循环不带头结点链表的基本操作。

单链表基本操作的实现

链表有数据域和指针域，因此我们在实现链表的两个结构使用类抽象出来，如下：

static class ListNode {
        public int val;//数据域
        public ListNode next;//指针域
        public ListNode(int val) {
            this.val = val;
        }
    }
    public ListNode head;
1
2
3
4
5
6
7
8

头插法

单链表是用户不断申请存储单元和改变链接关系而得到的一种特殊数据结构，将链表的左边称为链头，右边称为链尾。头插法建单链表是将链表右端看成固定的，链表不断向左延伸而得到的。头插法最先得到的是尾结点。

头插法每次插入数据都是在头节点的左边进行插入，头插法很简单，不需要考虑特殊情况，即使头节点为空，也不用担心，因为是将插入结点的指针域指向头节点，即使头节点为空，插入结点的指针域就是null，然后在将头节点指向刚才插入的那个结点就可以了，代码实现如下：

public void addFirst(int data){
        ListNode node = new ListNode(data);
        node.next = head;
        head = node;
    }
1
2
3
4
5

尾插法

若将链表的左端固定，链表不断向右延伸，这种建立链表的方法称为尾插法。尾插法建立链表时，头指针固定不动，故必须设立一个搜索指针，向链表右边延伸，在最后一个结点进行插入。尾插法最先得到的是头结点。

尾插法与头插法不同，头插法不用担心头结点为空的情况，但是尾插法不同，尾插法是插入在头节点之后，如果头节点为空，就没办法将结点插入，会报空指针异常的错误。
因此我们在进行尾插之前，$要先判断头节点是否为空，如果为空，那个要插入的结点就是头节点，如果不为空，就进行尾插的操作。$
因为头节点不能够移动，头节点移动的话，链表的结构就改变了。就需要在创建一个新的指针来遍历链表，在遍历到链表的最后一个结点时进行尾插。

 public void addLast(int data){
        ListNode node = new ListNode(data);
        ListNode cur = this.head;
        if(cur == null) {
            this.head = node;
        }else {
            while (cur.next != null) {
                cur = cur.next;
            }
            //cur已经是尾巴节点了
            cur.next = node;
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13

$避雷：$之前在写尾插法的时候，没有加else，因为都是先判断头节点是否为空，不为空就进行下面的操作。乍一看没有什么问题，但是里面的问题大了，因为在头结点为空的这种情况下，如果不加else，它就也会执行cur,next = node这行代码，前面有执行了this.head = node这行代码了，它就会指向自己，这就形成闭环了。

获得链表的长度

获得链表的长度，需要我们在遍历链表的同时进行计数，我们要定义一个指针遍历链表，如果这个指针不为空，就让count自增1，直到指针为空。

     public int size(){
        int count = 0;
        ListNode cur = head;
        while(cur != null){
            count++;
            cur = cur.next;
        }
        return count;
    }
1
2
3
4
5
6
7
8
9

在任意位置插入一个数据

在任意位置插入一个数据，第一个数据节点为0号下标。
数据结构是一门很严谨的学科，稍微有一点没注意到的地方，就会出现BUG。在单链表中插入数据如果处理不好，会出现很多问题。
先看下图，如果我要在2结点的后面插入3这个结点，需要怎么做？

答案是先先遍历链表，走到2这个位置，先让3这个结点的指针域等于2这个结点的指针域，然后再把3这个结点的地址赋值给2个结点的指针域。看下图：

一定要先把2的指针域存到3的指针域中，在把3的地址赋值给2的指针域中，顺序不能颠倒。
对于上面插入数据是一般情况，我们还要考虑到在$特殊位置插入数据$，就比如说$在0位置插入数据，还有在链表的最后插入数据$ 。
如果插入位置为0时，此时插入数据就会变成头插法插入数据。
如果插入位置刚好在链表的最后，此时插入就变成尾插法插入数据。

对于插入数据，只考虑插入位置的特殊性还是不够的，$我们还要考虑到插入位置的合法性。$
插入数据的位置是否合法我们也要进行判断，如果插入位置为负数或者超过链表的最大长度时，就无法插入数据。我们要让用户知道当然位置是无法插入数据的，我们可以在判断之后输出一个插入位置不合法，以及使用自定义异常来抛一个插入位置不合法的异常。

如果插入位置合法就进行数据的插入操作。分析完之后，就可以开始写代码了。

    //任意位置插入,第一个数据节点为0号下标
    public boolean addIndex(int index,int data){
        if(index < 0||size()<index){
            System.out.println("Index位置不合法");
            throw new IndexWrongFullExcption("Index位置不合法");
        }
        //插入位置为0时，头插法
        if(index == 0){
            addFirst(data);
        }
        //当插入位置为最后
        if(index == size()){
            addLast(data);
        }
        //当插入位置为中间时，要先走index-1步
        ListNode cur = findIndexSubOne(index);
        ListNode node = new ListNode(data);
        node.next = cur.next;
        cur.next = node;
        return false;
    }
    //找到index-1位置的结点
    private ListNode findIndexSubOne(int index) {
        ListNode cur = this.head;
        while (index-1 != 0) {
            cur = cur.next;
            index--;
        }
        return cur;
    }
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

我将找到index-1位置的结点这部分写成一个方法，是方便下次可能会在其它地方用到，如果会用到，直接调用这个方法即可，就不用复制粘贴甚至是重写一遍了，可以帮助我们减轻代码量。用不到也没关系。

判断链表中是否有值为key的结点

判断链表中是否有值为key的结点，我们只需要遍历一遍单链表就可以了，在遍历时让结点的数据域与key做比较，相等就返回true，不相等就继续遍历，直到遍历完，返回false

    //查找是否包含关键字key是否在单链表当中
    public boolean contains(int key){
        ListNode cur = this.head;
        while(cur!=null){
            if(cur.val == key){
                return true;
            }
            cur = cur.next;
        }
        return false;
    }
1
2
3
4
5
6
7
8
9
10
11

删除第一个等于给定值为key的结点

如果我要删除下面图中的2这个结点应该怎么做？

答案是将2结点的指针域赋值给1这个结点的指针域，就可以实现删除。效果如下图所示：

我们在遍历链表时，1这个结点的指针域发生了改变，因此1会直接指向3这个结点，从而实现删除。
当然我们也要保证链表中有值为key的这个结点，有才能进行删除。如果没有，就输出一个没有值为key的数字之类的提示用户。
$在删除时，从第二个结点开始之后结点的删除方法都是一样的，只有头结点不一样$，我们也要把头节点想到，如果头节点的数据域为key时应该怎样删。只需要让head = head.next让头节点往后走一步就可以了，虽然很简单，但是不要忽略头节点的问题。
最特殊的还是空链表问题，如果时空链表就不用删除，直接返回就可以了。

	//删除第一次出现关键字为key的节点
    public void remove(int key){
        if(this.head == null) {
            return;
        }
        //删除头节点
        if(this.head.val == key) {
            this.head = this.head.next;
            return;
        }
        ListNode cur = findPrevOfKey(key);
        if(cur == null) {
            System.out.println("没有你要删除的数字！");
            return;
        }
        ListNode del = cur.next;
        cur.next = del.next;
    }
    private ListNode findPrevOfKey(int key) {
        ListNode cur = this.head;
        while (cur.next != null) {
            if(cur.next.val == key){
                return cur;
            }
            cur = cur.next;
        }
        return null;
    }
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

删除所有等于给定值为key的结点

删除所有等于给定值为key的结点这个只需要在上面删除第一个值为key的基础上，遍历完整个链表，删除即可。
$其中有一点不同：$前面时删除第一个值等于key的结点， 所以要先判断头节点的值是否为key，但是这个题要放在最后在进行判断，如果不放在最后可能会发生没删完这种情况。
想一下，如果先判断头结点是否为key，如果是将头节点向后走一步，但如果后面一个结点的值也为key呢？如果只判断一次，那么这个值为key的结点就留下来了。如果想先判断头节点是否为key这个问题，就要使用循环，直到头节点的值不为key或者头节点为空。

 public void removeAllKey(int key){
         if(head == null){
             return;
         }
         ListNode cur = head.next;
         ListNode prev = head;
         while(cur != null){
             if(cur.val == key){
                 prev.next = cur.next;
                 cur = cur.next;
             }else{
                 prev = cur;
                 cur = cur.next;
             }
         }
         if(head.val == key){
             head = head.next;
         }
     }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

如果觉得不够详细或者不是很懂的小伙伴，也可以去看一下我的这篇文章：【数据结构算法篇】链表面试题2—删除链表中等于给定值 val 的所有节点

打印链表

头节点不能动，所以同样需要定义一个指针cur对单链表进行遍历，cur不为空，打印数据域，cur指向下一个结点，直到指针为空时停止。

    public void display(){
        ListNode cur = this.head;
        while(cur != null){
            System.out.print(cur.val+" ");
            cur = cur.next;
        }
    }
1
2
3
4
5
6
7

清空链表

清空单链表也很简单，只需要将头结点置为空就可以了，头节点为空了，就代表头节点与后面的链表失去了联系，从而找不到后面的结点了。

    public void clear(){
         this.head = null;
    }
1
2
3

完整代码：

public class MyLinkList {
    static class ListNode {
        public int val;
        public ListNode next;
        public ListNode(int val) {
            this.val = val;
        }
    }
    public ListNode head;
    // 1、无头单向非循环链表实现

    // 头插法
    public void addFirst(int data){
        ListNode node = new ListNode(data);
        node.next = head;
        head = node;
    }
    //尾插法
     public void addLast(int data){
        ListNode node = new ListNode(data);
        ListNode cur = this.head;
        if(cur == null) {
            this.head = node;
        }else {
            while (cur.next != null) {
                cur = cur.next;
            }
            //cur已经是尾巴节点了
            cur.next = node;
        }
    }
    //任意位置插入,第一个数据节点为0号下标
    public boolean addIndex(int index,int data){
        if(index < 0||size()<index){
            System.out.println("Index位置不合法");
            throw new IndexWrongFullExcption("Index位置不合法");
        }
        //插入位置为0时，头插法
        if(index == 0){
            addFirst(data);
        }
        //当插入位置为最后
        if(index == size()){
            addLast(data);
        }
        //当插入位置为中间时，要先走index-1步
        ListNode cur = findIndexSubOne(index);
        ListNode node = new ListNode(data);
        node.next = cur.next;
        cur.next = node;
        return false;
    }
    //找到index-1位置的结点
    private ListNode findIndexSubOne(int index) {
        ListNode cur = this.head;
        while (index-1 != 0) {
            cur = cur.next;
            index--;
        }
        return cur;
    }

    //查找是否包含关键字key是否在单链表当中
    public boolean contains(int key){
        ListNode cur = this.head;
        while(cur!=null){
            if(cur.val == key){
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

   //删除第一次出现关键字为key的节点
    public void remove(int key){
        if(this.head == null) {
            return;
        }
        //删除头节点
        if(this.head.val == key) {
            this.head = this.head.next;
            return;
        }

        ListNode cur = findPrevOfKey(key);
        if(cur == null) {
            System.out.println("没有你要删除的数字！");
            return;
        }
        ListNode del = cur.next;
        cur.next = del.next;
    }
	//找到数据域为key的前面一个结点
    private ListNode findPrevOfKey(int key) {
        ListNode cur = this.head;
        while (cur.next != null) {
            if(cur.next.val == key){
                return cur;
            }
            cur = cur.next;
        }
        return null;
    }

    /** 删除所有值为key的节点
     *  可能会遇到的问题
     *  1.空链表
     *  2.头节点的值为key
     * @param key
     */
     public void removeAllKey(int key){
         if(head == null){
             return;
         }
         ListNode cur = head.next;
         ListNode prev = head;
         while(cur != null){
             if(cur.val == key){
                 prev.next = cur.next;
                 cur = cur.next;
             }else{
                 prev = cur;
                 cur = cur.next;
             }
         }
         if(head.val == key){
             head = head.next;
         }
     }
     //得到单链表的长度
     public int size(){
        int count = 0;
        ListNode cur = head;
        while(cur != null){
            count++;
            cur = cur.next;
        }
        return count;
    }
    //打印链表
    public void display(){
        ListNode cur = this.head;
        while(cur != null){
            System.out.print(cur.val+" ");
            cur = cur.next;
        }
    }
    //清空单链表
    public void clear(){
         this.head = null;
    }
}

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

自定义异常

public class IndexWrongFullExcption extends RuntimeException{
    public IndexWrongFullExcption() {

    }
    public IndexWrongFullExcption(String message) {
        
        super(message);
    }
}
1
2
3
4
5
6
7
8
9