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

目录

一、链表

1.1. 链表的概念及结构

1.2. 链表的实现

专栏：数据结构(Java版)

个人主页：手握风云

一、链表

1.1. 链表的概念及结构

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

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

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

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

1.2. 链表的实现

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

```java
public class MySingleList {
    static class ListNode{
        private int val;
        private ListNode next;

        public ListNode(int val) {
            this.val = val;
        }
        //因为不知道下一个节点是谁，所以这里的构造函数的参数里不写next。
    }
     public ListNode head;//表示当前链表的头节点
     public int listSize;
}

```

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

```java
public interface Ilist {

    //头插法
    void addFirst(int data);

    //尾插法
    void addLast(int data);

    //任意位置插⼊第⼀个数据节点为0 号下标
    void addIndex(int index,int data);

    //查找是否包含关键字key是否在单链表当中
    boolean contains(int key);

    public void remove(int key);

    //删除所有值为 key的节点
    public void removeAllKey(int key);

    //得到单链表的⻓度
    int size();

    public void clear();
    public void display();
}

```


```java
public class MySingleList implements Ilist{
    static class ListNode{
        private int val;
        private ListNode next;

        public ListNode(int val) {
            this.val = val;
        }
        //因为不知道下一个节点是谁，所以这里的构造函数的参数里不写next。

        public ListNode head;//表示当前链表的头节点
    }

    @Override
    public void addFirst(int data) {

    }

    @Override
    public void addLast(int data) {

    }

    @Override
    public void addIndex(int index, int data) {

    }

    @Override
    public boolean contains(int key) {
        return false;
    }

    @Override
    public void remove(int key) {

    }

    @Override
    public void removeAllKey(int key) {

    }

    @Override
    public int size() {
        return 0;
    }

    @Override
    public void clear() {

    }

    @Override
    public void display() {

    }
}

```

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

```java
    public ListNode head;//表示当前链表的头节点
    public void CreateList(){
        ListNode node1 = new ListNode(11);
        ListNode node2 = new ListNode(22);
        ListNode node3 = new ListNode(33);
        ListNode node4 = new ListNode(44);
        //这些数据之间没有连续性

        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        //node4已经是最后一个节点了，不需要管最后一个next

        this.head = node1;//这样可以从第一个节点开始去遍历我们的数组
    }


public class Main {
    public static void main(String[] args) {
        MySingleList mySingleList = new MySingleList();
        mySingleList.CreateList();
        System.out.println("=========");
    }
}
```

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

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

```java
//基本变量通过自增的方式来赋值
int a = 10;
a = a + 1;

//同理，引用变量也可以采用上述方法
head = head.next;
```


```java
    @Override
    public void display() {
        while(head != null){
            System.out.print(head.val+" ");
            head = head.next;
        }
        System.out.println();
    }
```

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

运行结果如下：

但这种写法也有致命的缺点，如果说这个方法有返回值呢，head遍历完我们的链表之后，head引用变为了null，返回的值也会成一个null，如果我们再用ListCode创建一个cur变量，head引用保持不动，把head的引用赋值给cur，再让cur去遍历链表。

比如我们通过size方法来获取链表的节点数，就可以这样写：

```java
    @Override
    public int size() {
        ListNode cur = head;
        int count = 0;
        while(cur != null){
            cur = cur.next;
            count++;
        }
        return count;
    }
```

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

```java
    @Override
    public boolean contains(int key) {
        ListNode cur1 = head;
        while(cur1 != null){
            if(cur1.val == key){
                return true;
            }
            cur1 = cur1.next;
        }
        return false;
    }

        System.out.println(mySingleList.contains(44));
        System.out.println(mySingleList.contains(45));
```

可能有的老铁在写这个方法会写出cur1.next != null，因为最后一个节点的next为null，当cur1走到最后节点时，不满足cur1.next != null，相当与根本没有遍历完这个数组。

下面我们将要进行对链表里的数据进行增删查改。我们先来实现头插和尾插。我们如果向把一个node节点(里面存的数据是10)插入head节点前面之后，node节点就变成了head节点。我们可以通过下面两行代码来实现这个过程。这里千万不能把两行代码写反，因为这样就会使得node.next指向自己。

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

```java
    public void addFirst(int data) {
        ListNode node = new ListNode(data);
        if(head == null){
            head = node;//相当于插入进一个空的链表
        }else{
            node.next = head;
            head = node;
        }
    }
    public static void main(String[] args) {
        Ilist mySingleList = new MySingleList();
        mySingleList.addFirst(10);
        mySingleList.addFirst(20);
        mySingleList.addFirst(30);
        mySingleList.addFirst(40);
        mySingleList.display();
    }
```

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

```java
    @Override
    public void addLast(int data) {
        ListNode node = new ListNode(data);
        //表示链表为空
        if(head == null) {
            head = node;
            return;
        }
        //找到链表的尾巴
        ListNode cur = head;
        while (cur.next != null) {
            cur = cur.next;
        }
        cur.next = node;
    }
```

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

```java
node.next = cur.next;
cur.next = node;
```

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

```java
private ListNode findIndex(int index){
        ListNode cur = head;
        int count = 0;
        while(count != index-1){
            cur = cur.next;
            count++;
        }
        return cur;
    }
```


```java
public void addIndex(int index, int data) {
        ListNode node = new ListNode(data);
        ListNode cur = findIndex(index);
        node.next = cur.next;
        cur.next = node;
        listSize++;
    }
```

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

```java
        if(index == 0) {
            addFirst(data);
            return;
        }

        if(index == size()) {
            addLast(data);
            return;
        }
```


```java
    private void checkIndexOfAdd(int index){
        if(index<0 || index>size()){
            throw new RuntimeException("插入的位置不合法,index="+index);
        }
    }
```


```java
public class IndexOutOf extends RuntimeException{
    public IndexOutOf() {
    }

    public IndexOutOf(String message) {
        super(message);
    }
}

try {
            mySingleList.addIndex(6,99);
        }catch (IndexOutOf e) {
            e.printStackTrace();
        }
```

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

```java
cur.next = del.next;
```

```java
rivate ListNode findNode(int key) {
        ListNode cur = head;
        while (cur.next != null) {
            if(cur.next.val == key) {
                return cur;
            }
            cur = cur.next;
        }
        return null;
    }
```

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

```java
    @Override
    public void remove(int key) {
        if(head == null) {
            return;
        }
        if(head.val == key) {
            head = head.next;
            listSize--;
            return;
        }
        ListNode cur = findNode(key);
        if(cur == null) {
            System.out.println("没有你要删除的数据");
            return;
        }
        ListNode del = cur.next;
        cur.next = del.next;
        listSize--;
    }
```