链表(一)
文章目录
- 链表(一)
- 01 引入
- 02 概念及结构
- 03 单向不带头不循环链表实现
- 3.1 创建节点类型
- 3.2 简易创建一个链表
- 3.3 遍历链表每个节点
- 3.4 获取链表长度
- 3.5 查找是否包含关键字key是否在单链表当中
- 3.6 头插法
- 3.7 尾插法
- 3.8 任意位置插入
- 3.9 删除第一次出现关键字为key的节点
- 3.10 删除所有值为key的节点
- 3.11 清空
01 引入
接上文顺序表,我们可以知道ArrayList
的缺陷。当在ArrayList
任意位置插入或者删除元素时,就需要将后序元素整体往前或者往后搬移,时间复杂度为O(n)
,效率比较低,因此ArrayList
不适合做任意位置插入和删除比较多的场景。因此:java
集合中又引入了LinkedList
,即链表结构。
那么下面,让我们来了解了解链表。
02 概念及结构
链表是一种物理存储结构上非连续存储结构,数据元素的逻辑顺序是通过链表中的引用链接次序实现的 。其实就是节点组成,一个节点类似于火车一个车厢那样:
下面是一个单向带头非循环链表:
下面是链表的种类:
单向 | 双向 |
---|---|
不带头 | 带头 |
非循环 | 循环 |
通过彼此间的排列组合,一共可以分为:8种,如下:
- 单向 不带头 非循环
- 单向 不带头 循环
- 单向 带头 非循环
- 单向 带头 循环
- 双向 不带头 非循环
- 双向 不带头 循环
- 双向 带头 非循环
- 双向 带头 循环
这里着重介绍单向 不带头 非循环 和 双向 不带头 非循环。
- 无头单向非循环链表:结构简单,一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构,如哈希桶、图的邻接表等等。
- 无头双向链表:在Java的集合框架库中
LinkedList
底层实现就是无头双向循环链表。
03 单向不带头不循环链表实现
3.1 创建节点类型
链表是由一个一个节点组成的,每一个节点对应每一个对象,如果我们去抽象他,他其实有两个域值,所以我们可以把节点定义成内部类。
创建一个ListNode
类来作为节点类型,包含两个成员变量:val域
用来储存数据(数据域),next
用来存储下一个节点的地址(指针域)。
再创建一个带参的构造方法来实例化对象,同时给val
赋值,next的默认值是null
。接下来我们用代码来实现一下:
//静态内部类static class ListNode{public int val; //节点的值域public ListNode next; //下一个节点的地址//实例化节点对象public ListNode(int val){this.val = val;}}
3.2 简易创建一个链表
public ListNode head;//表示当前链表的头节点//以穷举的方式创建一个链表public void createList(){ListNode node1 = new ListNode(12);ListNode node2 = new ListNode(23);ListNode node3 = new ListNode(34);ListNode node4 = new ListNode(45);ListNode node5 = new ListNode(56);}
此时创建的链表如图:
目前各节点间不存在关系。
那么接下来的操作就是要让node1->node2->node3->node4->node5
//以穷举的方式创建一个链表public void createList(){ListNode node1 = new ListNode(12);ListNode node2 = new ListNode(23);ListNode node3 = new ListNode(34);ListNode node4 = new ListNode(45);ListNode node5 = new ListNode(56);node1.next = node2;node2.next = node3;node3.next = node4;node4.next = node5;this.head = node1;}
这里我们不妨在编译器里debug
来看看:
3.3 遍历链表每个节点
public void display() {while (head != null){System.out.println(head.val+" ");head = head.next;}}
这里我们可以在测试类中debug
一下看看:
虽然这里的确是将链表遍历完全,但是,这里的头节点head = null
那么这样就会造成一个后果,鬼都不知道头节点head
死哪里去了,那咋办?
这个后果虽然很严重,但是解决办法其实也很容易,既然head
它不能乱来,那它可以叫个分身cur
代替它去呀。
public void display() {ListNode cur = head;while (cur != null){//如果cur == null,说明把链表遍历完成System.out.println(cur.val+" ");cur = cur.next;//cur每次向后走一步}System.out.println();}
3.4 获取链表长度
这个其实也就是基于3.3 遍历链表得来的。
//得到单链表的长度public int size(){int count = 0;ListNode cur = head;if (cur!=null){while(cur != null){cur = cur.next;count++;}return count;}else{return -1;}}
3.5 查找是否包含关键字key是否在单链表当中
这个其实也一样是基于3.3 遍历链表得来的。
//查找是否包含关键字key是否在单链表当中public boolean contains(int key){ListNode cur = head;while(cur != null){if (key == cur.val){return true;}cur = cur.next;}return false;}
3.6 头插法
头插法指的是在链表的头节点位置插入一个新的节点,定义一个node
表示插入的新节点,然后将node.next = head
,head = node
,即可。
形象一点来看,如图:
//头插法public void addFirst(int data){ListNode node = new ListNode(data);node.next = head;head = node;}
3.7 尾插法
尾插法指的是:在链表的尾巴节点位置插入一个新节点,定义一个node
表示新节点,如同头插法那样,对原尾巴节点的next
进行赋值。下面是尾插链表出现的情况:
-
当链表不为空的时候,定义一个
cur
来代替head
(这里其实和遍历节点的道理一致),直到cur.next == null
的时候就跳出遍历,cur.next == node
,这样即可完成尾插。 -
当链表为空的时候,不论我们定义什么去代替
head
,都是竹篮打水一场空,都无法进入遍历,同时也会报空指针异常,解决方法其实也很简单,直接让head = node
即可。
具体分析见以下:
如图:
其实这其中也有遍历链表那味了,其思想就是遍历到链表最后一个节点,然后再进行尾插就行了。
//尾插法public void addLast(int data){ListNode node = new ListNode(data);ListNode cur = head;while (cur.next != null){cur = cur.next;}cur.next = node;}
但是这个代码是具有一定的问题的,情景如下图:
这个问题其实就是,此时head
是空的,同时我们定义一个cur= head
,那么cur
也是空,那么就无法进入到while循环中。修正如下:
//尾插法public void addLast(int data){ListNode node = new ListNode(data);ListNode cur = head;if (cur == null){head = node;return;}//找到链表的尾巴,注意是cur.next 不是curwhile (cur.next != null){cur = cur.next;}cur.next = node;}
3.8 任意位置插入
思路:
- 定义
cur
走index-1
步,找到要插入位置的前一个节点 - 进行插入
给一个情景,定义cur = index - 1
,在1号、2号间插入node
.
关键就在于我们要将0x66 -> 0x777
,null -> 0x32
,即node.next = cur.next
,cur.next = node
.
需要将head先移至2号位置(注意:用cur代替head,防止head丢失),然后
node.next = cur.next
使该节点的next域改为下一节点的地址,再cur.next = node.next
使前一节点的next
域改为该节点的地址。
//任意位置插入,第一个数据节点为0号下标public void addIndex(int index,int data){if (index < 0 || index > size()){System.out.println("index不合法");return;}if (index == 0){addFirst(data);return;}if (index == size()){addLast(data);return;}/*ListNode node = new ListNode(data);ListNode cur = head;int tmp = index - 1;while (tmp != 0){cur = cur.next;tmp--;}node.next = cur.next;cur.next = node;*///将上面这一坨封装ListNode cur = findIndexSubOne(index);ListNode node = new ListNode(data);node.next = cur.next;cur.next = node;}/*** 找到要删除节点位置的前一个节点* @param index* @return*/private ListNode findIndexSubOne(int index){ListNode cur = head;int tmp = index - 1;while (tmp != 0){cur = cur.next;tmp--;}return cur;}
3.9 删除第一次出现关键字为key的节点
效果图如下:
-
对于删除第一次出现的
key
值的节点,若不是头节点,我们只需将key
值对应的节点的前一节点的next
的域改为key
值对应的节点的next
域即可。 -
对于头节点,直接
head = head.next
即可。
- 找到要删除节点的前一个节点
- 此时要删除的节点
del = cur.next;
- 进行删除
cur.next = del.next
//删除第一次出现关键字为key的节点public void remove(int key){if (head == null){return;}//单独删除头节点if (head.val == key){head = head.next;return;}ListNode cur = searchPrev(key);if (cur == null){System.out.println("没有你要删除的数字!");return;}ListNode del = cur.next;cur.next = del.next;}/*** 找到关键字key的前驱* @param key* @return*/private ListNode searchPrev(int key){ListNode cur = head;while (cur.next != null){if (cur.next.val == key){return cur;}cur = cur.next;}return null;}
3.10 删除所有值为key的节点
情景如下:
将值为23
的删除
有种暴力的方法,我们只需要多次调用3.9
种的remove
函数即可,但是这并不是我们真正想要的,要求:遍历一遍就要删除完。
如图分析:
//删除所有值为key的节点public void removeAllKey(int key){ListNode prev = head;ListNode cur = head.next;if (head == null){return;}while (cur != null){if(cur.val == key){prev = cur.next;cur = cur.next;}else {prev = cur;cur = cur.next;}}if (head.val == key){head = head.next;}}
3.11 清空
简单粗暴:
public void clear() {this.head = null;}
温柔:
public void clear(){while(this.head != null){ListNode curNext = this.head.next;this.head.next = null;this.head = cur.next;}}