Java数据结构-认识链表

文章目录

一.链表的概念及结构

1.链表的概念

链表是一种

物理存储结构上

非连续的

存储结构

。数据元素中的逻辑顺序是通过链表中的

引用链接次序

实现的

2.链表的分类

链表情况非常多样，组合起来共有八种

• 单向、双向
• 带头、不带头
• 循环、非循环 但是这里我们重点讲两种：单向不带头非循环链表、双向不带头非循环链表

二.单向不带头非循环链表

1.创建节点类型

这里我们创建一个

ListNode

类来作为节点类型，包含两个成员变量：

val域

用来储存数据，

next

用来存储下一个节点的地址。
再创建一个带参的构造方法来实例化对象，同时给

val

赋值，next的默认值是null。接下来我们用代码来实现一下：

classListNode{publicint val;publicListNode next;//next存储的是下一个节点的地址，所以他的类型是一个节点类型publicListNode(int val){this.val = val;}}

然后我们在MyLinkedList里创建一个节点类型：

head

。可能大家会有疑问了，为什么在MyLinkedList里创建，而不是在节点里创建呢？因为head是

链表的头

，而不是节点的头，节点只有两个属性：

next

和

val

。
准备工作做完，我们就可以具体实现链表的增删查改等操作啦！

2.头插法

头插法就是从链表的头部插入节点

node

，然后使新节点node成为头节点head

具体代码实现如下：

//头插法publicvoidaddFirst(int data){ListNode node =newListNode(data);
        node.next =this.head;this.head = node;}

3.尾插法

尾插法跟头插法的不同之处在于，尾插法的第一次插入必须判断链表是否为空，即

头节点是否为null

，如果为null，那么新插入的节点直接变成头节点即可。除此之外，我们需要引入一个局部变量：

cur来遍历链表

，当

cur.next为空

的时候，说明此时的

cur就是尾节点

，我们只需要在cur后面插入新节点node即可

具体的代码实现如下：

//尾插法publicvoidaddLast(int data){ListNode node =newListNode(data);if(this.head ==null){this.head = node;//说明是第一次插入，直接让node变成head}else{ListNode cur =this.head;while(cur.next !=null){
                cur = cur.next;}// cur走完了所有节点 : cur.next = null
            cur.next = node;}}

4.打印单链表

链表的打印和顺序表的打印大同小异，只需要遍历链表就行了。不过需要注意的是，我们不能用头节点head来遍历，因为遍历完head就找不到了，所以我们需要用局部变量

cur来代替head遍历

具体的代码实现如下：

//打印链表长度publicvoiddisplay(){ListNode cur =this.head;while( cur !=null){System.out.print(cur.val +" ");
            cur = cur.next;}System.out.println();}

5.查找key是否在单链表中

传入关键字key，使用

局部变量cur遍历单链表

，当cur.val等于key时，说明单链表中包含key，返回true，否则遍历完没找到，返回false

具体的代码实现如下：

//查找关键字key是否包含在单链表当中publicbooleancontains(int key){ListNode cur =this.head;while(cur !=null){if(cur.val == key){returntrue;}
            cur = cur.next;}returnfalse;}

6.得到单链表的长度

跟顺序表做法大同小异，还是用

cur遍历单链表

，同时创建一个计数器count，只要节点不为null，

count++

，最后返回count的值就是该单链表的长度

具体的代码实现如下：

//得到单链表的长度publicintsize(){int count =0;ListNode cur =this.head;while(cur!=null){
            count++;
            cur = cur.next;}return count;}

7.任意位置插入，第一个数据节点为0号下标

跟顺序表类似，插入的时候，我们都要判断其位置是否合法。然后我们需要创建一个

findIndex

方法用于

查找插入位置的前一个节点

具体的代码实现如下：

//先找到index-1位置 节点的地址，就是cur位置publicListNodefindIndex(int index){ListNode cur =this.head;while(index-1!=0){
            cur=cur.next;
            index--;}return cur;}//任意位置插入,第一个数据节点为0号下标publicvoidaddIndex(int index,int data){if(index<0|| index>size()){//先判断index坐标的合法性System.out.println("index位置不合法！");return;}if(index ==0){//头插法addFirst(data);return;}if(index ==size()){//尾插法addLast(data);return;}ListNode cur =findIndex(index);ListNode node =newListNode(data);
        node.next = cur.next;
        cur.next = node;}

8.删除第一次出现关键字为key的节点

删除的时候，我们要先判断单链表是否为空(

头节点是否为null

)。如果不为空，我们要看需要删除的节点是否为头节点，如果是，我们直接将

头节点的下一节点设置为头节点

。如果要删除的节点不是头节点，我们可以写一个方法来

寻找该节点的前驱节点

，然后将要删除的节点的下一节点

del.next

赋值给前驱节点的下一节点

cur.next

具体的代码实现如下：

//先找到key节点的前驱节点publicListNodesearchPrev(int key){ListNode cur =this.head;while(cur.next !=null){if(cur.next.val == key){//如果找到该前驱节点，返回前驱节点curreturn cur;}
            cur = cur.next;//未找到就继续遍历链表}returnnull;//如果循环完都没找到，就返回null}//删除第一次出现关键字为key的节点publicvoidremove(int key){if(this.head ==null){System.out.println("链表为空，不能删除！");return;}if(this.head.val == key){//要删除的位置就在头节点this.head =this.head.next;return;}ListNode cur =searchPrev(key);//调用刚刚写的函数来寻找前驱curif(cur ==null){System.out.println("没有你要删除的节点！");return;}ListNode del = cur.next;
        cur.next = del.next;}

9.删除所有值为key的节点

首先还是要判断单链表是否为空，如果为空则返回null。然后设置

prev为cur的前驱

，cur从

head.next

开始遍历，遇到cur.val为key值时，删除该节点然后继续遍历，遍历完后再来处理头节点，判断head是否为key值，是的话进行删除操作即可

具体代码实现如下：

//删除所有值为key的节点publicListNoderemoveAllKey(int key){if(this.head ==null)returnnull;ListNode prev =this.head;ListNode cur =this.head.next;while(cur!=null){if(cur.val == key){//假如cur节点是要删除的节点，将cur节点删去再继续遍历
                 prev.next = cur.next;
                 cur = cur.next;}else{//cur节点不是要删除的节点，继续往后遍历
                prev = cur;
                cur = cur.next;}}//最后处理头，判断头节点的val域是不是key值if(this.head.val == key){this.head =this.head.next;}returnthis.head;}

10.清空单链表

• 暴力清空：直接将头节点置空

//清空单链表publicvoidclear(){this.head =null;}

• 温柔清空：将节点一个一个释放

//清空单链表publicvoidclear(){while(this.head !=null){ListNode curNext = head.next;this.head.next =null;this.head = curNext;}}

三.双向不带头循环链表

1.创建节点类型

这里我们创建一个

ListNode

类来作为节点类型，包含三个成员变量：

val

域用来储存数据，

next

用来存储下一个节点的地址，

prev

用来存储上一个节点的地址。
再创建一个带参的构造方法来实例化对象，同时给

val

赋值，next和prev的默认值是null。接下来我们用代码来实现一下：

classListNode{publicint val;publicListNode prev;publicListNode next;publicListNode(int val){this.val = val;}}

然后，我们在MyLinkedList里创建两个节点类型，分别是

head

和

last

，head指向双链表的

头节点

，last指向双链表的

尾节点

。下面，我们来进行双链表的增删查改！

2.头插法

同样的，我们还是要先判断

第一次插入节点node时

链表是否为空，如果

链表为空

，那么我们的head和last都要指向node。插入时，我们可以画图来理解：

具体的代码实现如下：

//头插法publicvoidaddFirst(int data){ListNode node =newListNode(data);//先判断是不是第一次插入if(this.head ==null){this.head = node;this.last = node;}else{
                node.next =this.head;this.head.prev = node;this.head = node;//最后将头节点改为node}}

3.尾插法

跟头插法一样，

第一次插入节点node

时同样要考虑

链表是否为空

。为空则将head节点和last节点都绑定为node节点即可。不为空时，我们同样通过画图理解来更改位置，最后将

last节点改为node节点

即可

具体的代码实现如下：

//尾插法publicvoidaddLast(int data){ListNode node =newListNode(data);//跟头插法一样，还是要先判断是不是第一次插入if(this.head ==null){this.head = node;this.last = node;}else{this.last.next = node;
                node.prev =this.last;this.last = node;}}

4.打印双链表

跟单链表做法相同，使用

局部变量cur

来代替head遍历双链表

具体的代码实现如下：

//打印双链表publicvoiddisplay(){//和单链表的打印方式一样ListNode cur =this.head;while(cur !=null){System.out.print(cur.val +" ");
                 cur = cur.next;}System.out.println();}

5.查找key是否在双链表中

做法也跟单链表相同，使用

局部变量cur

代替head遍历链表，

cur.val的值等于key值

时就返回true

具体的代码实现如下：

//查找是否包含关键字key是否在双链表当中publicbooleancontains(int key){ListNode cur =this.head;while(cur !=null){if(cur.val == key){returntrue;}
                cur = cur.next;}returnfalse;}

6.得到双链表的长度

做法还是与单链表相同。设置一个计数器count，局部变量cur来代替head遍历，

cur不为0时

，

count++

，最后返回

count

就是双链表的长度

具体的代码实现如下：

//打印双链表publicvoiddisplay(){//和单链表的打印方式一样ListNode cur =this.head;while(cur !=null){System.out.print(cur.val +" ");
                 cur = cur.next;}System.out.println();}

7.任意位置插入，第一个数据节点为0号下标

插入的时候，我们要先判断

index位置的合法性

。然后我们创建一个findIndex方法来寻找

要插入的位置

。注意，跟单链表不同，单链表是寻找插入位置的前驱！

具体的代码实现如下：

//找到要插入节点的位置publicListNodesearchIndex(int index){ListNode cur =this.head;while(index !=0){
                cur = cur.next;
                index--;}return cur;}//任意位置插入,第一个数据节点为0号下标publicvoidaddIndex(int index,int data){ListNode node =newListNode(data);if(index<0|| index>size()){//先判断index位置的合法性System.out.println("该位置不合法！");}if(index ==0){//头节点插入，采用头插法addFirst(data);}if(index ==size()){//尾节点插入，采用尾插法addLast(data);}ListNode cur =searchIndex(index);
            node.next = cur.prev.next;
            cur.prev.next = node;
            node.prev = cur.prev;
            cur.prev = node;}

8.删除第一次出现关键字为key的节点

首先还是判断链表是否为空，不为空我们再去寻找删除的节点，要删除的节点有三种情况：

• 要删除的节点在头节点：直接将头节点的下一节点设置为新的头节点，再将新头节点的前驱置为空即可
• 要删除的节点在中间节点：只需要通过画图，然后改四个位置即可
• 要删除的节点在尾节点：将尾节点前驱的next置为尾节点的next（也就是null），再将尾节点的前驱设为新的尾节点

具体的代码实现如下：(这段代码可能难理解，建议画图自己写一遍)

//删除第一次出现关键字为key的节点publicvoidremove(int key){ListNode cur =this.head;while(cur !=null){if(cur.val == key){if(cur == head){//首先判断要删除的节点是不是头节点this.head =this.head.next;//先将头节点往后移一位if(head !=null){//如果双链表不是只有一个节点this.head.prev =null;//再将现在头节点的前驱置为空}else{//如果双链表只有一个节点，即head为空了this.last =null;//要把last也置为空}}else{
                         cur.prev.next = cur.next;//将cur的next，赋给cur前驱的nextif(cur.next !=null){//说明不是尾节点，是中间位置
                             cur.next.prev = cur.prev;}else{//说明是尾节点，只需要将last往前移一位this.last =this.last.prev;}}return;}
                 cur = cur.next;}}

9.删除所有值为key的节点

我们在上一段代码发现删除完一个节点后就不再执行了。既然要删除所有的节点，那我们删掉return即可，即代码删除完一个节点后

不返回

，继续执行

具体的代码实现如下：

//删除所有值为key的节点publicvoidremoveAllKey(int key){ListNode cur =this.head;while(cur !=null){if(cur.val == key){if(cur == head){//首先判断要删除的节点是不是头节点this.head =this.head.next;//先将头节点往后移一位if(head !=null){//如果双链表不是只有一个节点this.head.prev =null;//再将现在头节点的前驱置为空}else{//如果双链表只有一个节点，即head为空了this.last =null;//要把last也置为空}}else{
                         cur.prev.next = cur.next;//将cur的next，赋给cur前驱的nextif(cur.next !=null){//说明不是尾节点，是中间位置
                             cur.next.prev = cur.prev;}else{//说明是尾节点，只需要将last往前移一位this.last =this.last.prev;}}//删完cur继续往后走，不return}
                 cur = cur.next;}}

10.清空双链表

• 暴力清空：将头节点和尾节点都置为空
• 温柔清空：先将head一个一个清空，最后将last也置空

//清空双向链表publicvoidclear(){while(head !=null){ListNode curNext = head.next;
                 head.next =null;
                 head.prev =null;
                 head = curNext;}
             last =null;//最后将last也全部置为空}

四.顺序表和链表的区别

1.从组织上看

• 顺序表底层是一个数组，是逻辑上和物理上都连续的
• 链表是一个由若干节点组成的数据结构，逻辑上是连续的，但是物理/内存上不一定连续

2.从操作上看

• 顺序表适合查找相关操作，因为可以使用下标直接获取某一位置的元素
• 链表适合需要频繁插入、删除操作。不需要像顺序表一样移动元素，只需要修改指向
• 顺序表满了后还需要扩容，扩容空间也不一定能完全利用，空间利用率不高。而链表随用随取，不用担心空间的浪费