数据结构(Java版)第六期：LinkedList与链表(一)
目录一、链表
1.1. 链表的概念及结构
1.2. 链表的实现
专栏：数据结构(Java版)
个人主页：手握风云
https://i-blog.csdnimg.cn/direct/34355f67a04f491284477e8bd7a91ebb.jpeg
一、链表
1.1. 链表的概念及结构
链表是⼀种物理存储结构上⾮一连存储结构，数据元素的逻辑顺序是通过链表中的引⽤链接序次实现的。与火车类似，火车头、车厢与每一届车厢之间由火车链连接起来。在物理上，链表是不一定一连的，但在逻辑上一定是一连的。
https://i-blog.csdnimg.cn/direct/c5ab70f2e54d419f9de944fd53b7ebe5.png
如下图所示，链表的结构分为两个域，一个域用来储存数据，另一个域用来储存下一个节点(类似于火车的一节车厢)的地点。 与顺序表不同的是，链表的地点在物理上不一连，但在逻辑上是一连的。最后一个节点相当于“车尾”，里面存的地点为null。这就是一个单向、不带头、非循环的链表。类似地，还有双向、带头、循环的链表。但考试考最多的说就是单链表。
https://i-blog.csdnimg.cn/direct/025fde1b275f43b1b176d13f94a19d8c.png
什么是带头的链表呢？如下图所示，第一个节点可以存任何数据，但存取的数据是没故意义的，唯一的作用就是起到一个“排头兵”的作用。不带头的链表呢，相当于它的head会变的，比如我们把第一个节点删掉，那么第二个节点就会成为head。
https://i-blog.csdnimg.cn/direct/4cea43390a7a4e869d53455a3a123c13.png
那么什么又是循环链表呢？如下图所示，最后一个节点指向了第一个节点或第二个节点，就可以构成循环链表，但一般环境下，我们都是指向第一个节点。
https://i-blog.csdnimg.cn/direct/4eb7ed6d326a4c569b60a6b07d064376.png
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;//表示当前链表的头节点
}
@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() {
}
}
我们也可以自己创建一个链表：
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方法串联起来了。
https://i-blog.csdnimg.cn/direct/a90da6640f314303a15f0c87aa36be8e.png
https://i-blog.csdnimg.cn/direct/6fa7cd2b744f4a939e45f4ad75f1c7e2.png
相识了next的引用原理之后，我们就可以遍历链表来对里面的数据举行打印。我们通过上面的display方法来实现，那我们如何通过head的引用从第一个节点指向第二个节点呢？
https://i-blog.csdnimg.cn/direct/e18b9c6487694f86855cce3447c7303d.png
//基本变量通过自增的方式来赋值
int a = 10;
a = a + 1;
//同理，引用变量也可以采用上述方法
head = head.next; @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循环。
https://i-blog.csdnimg.cn/direct/1ef2d0c6ba824564bb7815e46c93a2b0.png
https://i-blog.csdnimg.cn/direct/5ebbcff3485149f88dd390522c2b9381.png
https://i-blog.csdnimg.cn/direct/cb5c853f531a42738684867bd61dcc6f.png
https://i-blog.csdnimg.cn/direct/54e20572a0b54b3facf68ab9cb8bdcde.png
运行结果如下：
https://i-blog.csdnimg.cn/direct/fc1e68a5210d4d7d9e2612a897f264fc.png 但这种写法也有致命的缺点，假如说这个方法有返回值呢，head遍历完我们的链表之后，head引用变为了null，返回的值也会成一个null，假如我们再用ListCode创建一个cur变量，head引用保持不动，把head的引用赋值给cur，再让cur去遍历链表。
比如我们通过size方法来获取链表的节点数，就可以这样写：
@Override
public int size() {
ListNode cur = head;
int count = 0;
while(cur != null){
cur = cur.next;
count++;
}
return count;
} https://i-blog.csdnimg.cn/direct/b88aadc4fa7a42dcb21cbb86f59f2d65.png
再比如我们去写contains方法去判断链表里是否存在关键字：
@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)); https://i-blog.csdnimg.cn/direct/2bb9541d6ea44313ba4ec02b9462adc6.png
可能有的老铁在写这个方法会写出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变成头节点 https://i-blog.csdnimg.cn/direct/2a5c263f2e9247c39bf3d4e63bc51db0.png
https://i-blog.csdnimg.cn/direct/4f8e124c59e34ae3aa75d4f1a200aba3.png
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();
} https://i-blog.csdnimg.cn/direct/96e55cea5bc14c38b2234629b6f16cc0.png
对于尾插的实现，与头插不同的是，我们需要先找出链表的最后一个节点，然后再让cur.next = node。假如说初始的链表是空的环境下，则cur= null，cur.next就会出现空指针异常。我们就需要参考contains方法来寻找链表的尾部。
@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步。我们可以通过两行代码来实现这一过程。
https://i-blog.csdnimg.cn/direct/d3ff23fdf28e43148c0f3afb377239f8.png
https://i-blog.csdnimg.cn/direct/73f62f7c5c5c420793626ca31b03bc08.png
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();
} https://i-blog.csdnimg.cn/direct/f0239d53f1134493aeaaef885038550f.png
接下来我们看删除元素。删除并不是简单的跳过这个节点，还要把要删除的节点前一个和后一个连接起来。那我们先找到要删除元素的前一个元素，我们又该如何找到要删除的节点呢？
cur.next = del.next;
https://i-blog.csdnimg.cn/direct/ee2aff933e774d5ba92cc33f6666ba76.png
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就不会对第一个节点举行判断，从而就不会删除。
@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--;
}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]