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

目录

一、链表

1.1. 链表的概念及结构

1.2. 链表的实现

---

专栏：数据结构(Java版)

个人主页：手握风云

一、链表

1.1. 链表的概念及结构

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

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

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

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

1.2. 链表的实现

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

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类里面对这些方法进行重写。

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();
}

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;//表示当前链表的头节点}@Overridepublic void addFirst(int data) {}@Overridepublic void addLast(int data) {}@Overridepublic void addIndex(int index, int data) {}@Overridepublic boolean contains(int key) {return false;}@Overridepublic void remove(int key) {}@Overridepublic void removeAllKey(int key) {}@Overridepublic int size() {return 0;}@Overridepublic void clear() {}@Overridepublic void display() {}
}

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

    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已经是最后一个节点了，不需要管最后一个nextthis.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的引用从第一个节点指向第二个节点呢？

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

    @Overridepublic 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方法来获取链表的节点数，就可以这样写：

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

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

    @Overridepublic 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指向自己。

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

    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方法来寻找链表的尾部。

    @Overridepublic 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步。我们可以通过两行代码来实现这一过程。

node.next = cur.next;
cur.next = node;

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

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

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位置插呢？这时就会越界访问。我们就需要写一个方法来检查访问是否合法。

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

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

public class IndexOutOf extends RuntimeException{public IndexOutOf() {}public IndexOutOf(String message) {super(message);}
}try {mySingleList.addIndex(6,99);}catch (IndexOutOf e) {e.printStackTrace();}

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

cur.next = del.next;

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就不会对第一个节点进行判断，从而就不会删除。

    @Overridepublic 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--;}