数据结构(Java版)第六期：LinkedList与链表(一)

目录
一、链表
1.1. 链表的概念及结构
1.2. 链表的实现

---

   

专栏：数据结构(Java版)

  

个人主页：手握风云

  

一、链表

1.1. 链表的概念及结构

       链表是⼀种物理存储结构上⾮一连存储结构，数据元素的逻辑顺序是通过链表中的引⽤链接序次实现的。与火车类似，火车头、车厢与每一届车厢之间由火车链连接起来。在物理上，链表是不一定一连的，但在逻辑上一定是一连的。

        如下图所示，链表的结构分为两个域，一个域用来储存数据，另一个域用来储存下一个节点(类似于火车的一节车厢)的地点。 与顺序表不同的是，链表的地点在物理上不一连，但在逻辑上是一连的。最后一个节点相当于“车尾”，里面存的地点为null。这就是一个单向、不带头、非循环的链表。类似地，还有双向、带头、循环的链表。但考试考最多的说就是单链表。

      什么是带头的链表呢？如下图所示，第一个节点可以存任何数据，但存取的数据是没故意义的，唯一的作用就是起到一个“排头兵”的作用。不带头的链表呢，相当于它的head会变的，比如我们把第一个节点删掉，那么第二个节点就会成为head。

        那么什么又是循环链表呢？如下图所示，最后一个节点指向了第一个节点或第二个节点，就可以构成循环链表，但一般环境下，我们都是指向第一个节点。

1.2. 链表的实现

      接下来我们要通过代码来实现链表，我们就可以定义一个MySingleList类，链表当中有许多的节点，基于面向对象的头脑，我们可以利用内部类来定义我们的节点。

1. public class MySingleList {
2.     static class ListNode{
3.         private int val;
4.         private ListNode next;
6.         public ListNode(int val) {
7.             this.val = val;
8.         }
9.         //因为不知道下一个节点是谁，所以这里的构造函数的参数里不写next。
10.     }
11.      public ListNode head;//表示当前链表的头节点
12.      public int listSize;
13. }

复制代码

       链表的底子已经写好了，下面要实行链表的增、删、查、改。我们可以把这些方法写在一个接口里面。接口里面的方法默认都是public，并且不需要具体的实现。然后我们在MySingleList类里面临这些方法举行重写。

1. public interface Ilist {
3.     //头插法
4.     void addFirst(int data);
6.     //尾插法
7.     void addLast(int data);
9.     //任意位置插⼊第⼀个数据节点为0 号下标
10.     void addIndex(int index,int data);
12.     //查找是否包含关键字key是否在单链表当中
13.     boolean contains(int key);
15.     public void remove(int key);
17.     //删除所有值为 key的节点
18.     public void removeAllKey(int key);
20.     //得到单链表的⻓度
21.     int size();
23.     public void clear();
24.     public void display();
25. }

复制代码

1. public class MySingleList implements Ilist{
2.     static class ListNode{
3.         private int val;
4.         private ListNode next;
6.         public ListNode(int val) {
7.             this.val = val;
8.         }
9.         //因为不知道下一个节点是谁，所以这里的构造函数的参数里不写next。
11.         public ListNode head;//表示当前链表的头节点
12.     }
14.     @Override
15.     public void addFirst(int data) {
17.     }
19.     @Override
20.     public void addLast(int data) {
22.     }
24.     @Override
25.     public void addIndex(int index, int data) {
27.     }
29.     @Override
30.     public boolean contains(int key) {
31.         return false;
32.     }
34.     @Override
35.     public void remove(int key) {
37.     }
39.     @Override
40.     public void removeAllKey(int key) {
42.     }
44.     @Override
45.     public int size() {
46.         return 0;
47.     }
49.     @Override
50.     public void clear() {
52.     }
54.     @Override
55.     public void display() {
57.     }
58. }

复制代码

     我们也可以自己创建一个链表：

1.     public ListNode head;//表示当前链表的头节点
2.     public void CreateList(){
3.         ListNode node1 = new ListNode(11);
4.         ListNode node2 = new ListNode(22);
5.         ListNode node3 = new ListNode(33);
6.         ListNode node4 = new ListNode(44);
7.         //这些数据之间没有连续性
9.         node1.next = node2;
10.         node2.next = node3;
11.         node3.next = node4;
12.         //node4已经是最后一个节点了，不需要管最后一个next
14.         this.head = node1;//这样可以从第一个节点开始去遍历我们的数组
15.     }
18. public class Main {
19.     public static void main(String[] args) {
20.         MySingleList mySingleList = new MySingleList();
21.         mySingleList.CreateList();
22.         System.out.println("=========");
23.     }
24. }

复制代码

       我们在对象实例化这里打一个断点来举行调试。开始的时候，头节点是空的，运行到下一行时，我们的val的值和next的地点都被CreateList方法串联起来了。

        相识了next的引用原理之后，我们就可以遍历链表来对里面的数据举行打印。我们通过上面的display方法来实现，那我们如何通过head的引用从第一个节点指向第二个节点呢？

1. //基本变量通过自增的方式来赋值
2. int a = 10;
3. a = a + 1;
5. //同理，引用变量也可以采用上述方法
6. head = head.next;

复制代码

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

复制代码

       我们来对这个方法举行调试一下，如下图所示，当head不为空时，进入while循环，当head.next指向第二个节点时val的值变为了22，next的地点也指向了第二个节点。当head指向最后一个节点时，地点变为null，跳出while循环。
 

    运行结果如下：

        但这种写法也有致命的缺点，假如说这个方法有返回值呢，head遍历完我们的链表之后，head引用变为了null，返回的值也会成一个null，假如我们再用ListCode创建一个cur变量，head引用保持不动，把head的引用赋值给cur，再让cur去遍历链表。
       比如我们通过size方法来获取链表的节点数，就可以这样写：

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

复制代码

     再比如我们去写contains方法去判断链表里是否存在关键字：

1.     @Override
2.     public boolean contains(int key) {
3.         ListNode cur1 = head;
4.         while(cur1 != null){
5.             if(cur1.val == key){
6.                 return true;
7.             }
8.             cur1 = cur1.next;
9.         }
10.         return false;
11.     }
13.         System.out.println(mySingleList.contains(44));
14.         System.out.println(mySingleList.contains(45));

复制代码

 

        可能有的老铁在写这个方法会写出cur1.next != null，因为最后一个节点的next为null，当cur1走到最后节点时，不满足cur1.next != null，相当与根本没有遍历完这个数组。
       下面我们将要举行对链表里的数据举行增删查改。我们先来实现头插和尾插。我们假如向把一个node节点(里面存的数据是10)插入head节点前面之后，node节点就变成了head节点。我们可以通过下面两行代码来实现这个过程。这里万万不能把两行代码写反，因为这样就会使得node.next指向自己。

1. node.next = head;//先让node.next的地址指向node1
2. head = node;//再通过head引用指向node，就能把node变成头节点

复制代码

1.     public void addFirst(int data) {
2.         ListNode node = new ListNode(data);
3.         if(head == null){
4.             head = node;//相当于插入进一个空的链表
5.         }else{
6.             node.next = head;
7.             head = node;
8.         }
9.     }
10.     public static void main(String[] args) {
11.         Ilist mySingleList = new MySingleList();
12.         mySingleList.addFirst(10);
13.         mySingleList.addFirst(20);
14.         mySingleList.addFirst(30);
15.         mySingleList.addFirst(40);
16.         mySingleList.display();
17.     }

复制代码

       对于尾插的实现，与头插不同的是，我们需要先找出链表的最后一个节点，然后再让cur.next = node。假如说初始的链表是空的环境下，则cur= null，cur.next就会出现空指针异常。我们就需要参考contains方法来寻找链表的尾部。

1.     @Override
2.     public void addLast(int data) {
3.         ListNode node = new ListNode(data);
4.         //表示链表为空
5.         if(head == null) {
6.             head = node;
7.             return;
8.         }
9.         //找到链表的尾巴
10.         ListNode cur = head;
11.         while (cur.next != null) {
12.             cur = cur.next;
13.         }
14.         cur.next = node;
15.     }

复制代码

     下面我们来实现比力复杂的在任意位置插入一个节点：为了方便明确，我们给每个节点都编上号。假如说我们要把新的节点插入到2号位置，那么新的节点就会变成2号位置。但我们的cur是不能走两步的，因为插入之后2号位置不知道前面的节点是谁，这个链表是单向的，以是cur不能往回走，也就是要走index-1步。我们可以通过两行代码来实现这一过程。

1. node.next = cur.next;
2. cur.next = node;

复制代码

       对于cur需要走index-1步的过程，我们可以重新写一个方法来实现。然后我们就可以把新节点插入到链表中了。

1. private ListNode findIndex(int index){
2.         ListNode cur = head;
3.         int count = 0;
4.         while(count != index-1){
5.             cur = cur.next;
6.             count++;
7.         }
8.         return cur;
9.     }

复制代码

1. public void addIndex(int index, int data) {
2.         ListNode node = new ListNode(data);
3.         ListNode cur = findIndex(index);
4.         node.next = cur.next;
5.         cur.next = node;
6.         listSize++;
7.     }

复制代码

       过程确实有点复杂，不懂的老铁可以去画画图去明确。到这里，看似我们的过程已经结束了，但我们需要思量其他的一些题目。假如我们在0号位置插或者在5号位置插，那么就相当于头插和尾插了，我们就可以直接调用addFirst和addLast方法。那假如我们在-1、-2位置插呢？这时就会越界访问。我们就需要写一个方法来检查访问是否合法。

1.         if(index == 0) {
2.             addFirst(data);
3.             return;
4.         }
6.         if(index == size()) {
7.             addLast(data);
8.             return;
9.         }

复制代码

1.     private void checkIndexOfAdd(int index){
2.         if(index<0 || index>size()){
3.             throw new RuntimeException("插入的位置不合法,index="+index);
4.         }
5.     }

复制代码

1. public class IndexOutOf extends RuntimeException{
2.     public IndexOutOf() {
3.     }
5.     public IndexOutOf(String message) {
6.         super(message);
7.     }
8. }
10. try {
11.             mySingleList.addIndex(6,99);
12.         }catch (IndexOutOf e) {
13.             e.printStackTrace();
14.         }

复制代码

       接下来我们看删除元素。删除并不是简单的跳过这个节点，还要把要删除的节点前一个和后一个连接起来。那我们先找到要删除元素的前一个元素，我们又该如何找到要删除的节点呢？

1. cur.next = del.next;

复制代码

1. rivate ListNode findNode(int key) {
2.         ListNode cur = head;
3.         while (cur.next != null) {
4.             if(cur.next.val == key) {
5.                 return cur;
6.             }
7.             cur = cur.next;
8.         }
9.         return null;
10.     }

复制代码

       通过上面这个方法，我们就可以找到我们要删除的节点。注意，我们不能写成cur != null，因为cur.next就会空指针异常。假如我们没有找到，就返回null。但是，我们需要思量一下，我们要删除第一个数据，cur已经在第一个节点，那么cur.next就不会对第一个节点举行判断，从而就不会删除。

1.     @Override
2.     public void remove(int key) {
3.         if(head == null) {
4.             return;
5.         }
6.         if(head.val == key) {
7.             head = head.next;
8.             listSize--;
9.             return;
10.         }
11.         ListNode cur = findNode(key);
12.         if(cur == null) {
13.             System.out.println("没有你要删除的数据");
14.             return;
15.         }
16.         ListNode del = cur.next;
17.         cur.next = del.next;
18.         listSize--;
19.     }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。