一、什么是链表
一种常见的数据存储结构，是一种线性表，但是不会按照线性的顺序存储数据，而是每一个节点存储下一个节点的指针。
二、什么是递归算法
在链表的数据结构中，我们经常会使用到递归算法。
递归算法
是一种直接或者间接调用算法的过程，其特点有
- 描述简洁，便于理解。
- 必须要有出口，否则就是死循环。
- 递归内存消耗大，容易发生内存溢出。
- 层级调用越多， 越危险。
下列为用递归算法实现的阶乘
public static long factorial(long num){
if(num == 1)return 1;
return num*factorial(num - 1);
}
三、如何手写实现链表
链表结构如图所示
屏幕快照 2019-10-26 下午10.59.46.png
每一个链表都是由节点构成的，我们要先定义节点的数据结构。
private class Node{
// 节点存储的数据
private int data;
// 把当前自己的类型当作属性
private Node next, head;
// 有参的构造方法
public Node(int data){
this.data = data;
}
// 设置数据
public void setData(int data){
this.data = data;
}
// 获取数据
public int getData(){
return data;
}
}
为了减少代码量，我们采用内部类的形式，直接将节点类定义在链表类之中，并且采取尾插法的方式来建立链表。
增加节点代码如下:
public void addTailNode(int data){
// 后面为空直接添加
if (this.next == null){
this.next = new Node(data);
}else {
// 递归操作
this.next.addTailNode(data);
}
}
删除节点代码如下:
public void deleteNode(int data){
// 如果该节点后面不为空
if (this.next != null){
// 如果数据域相等
if (this.next.data == data){
// 隔空相连
this.next = this.next.next;
}else {
// 递归操作
this.next.deleteNode(data);
}
}
}
向前添加节点代码如下:
public boolean insetFrontNode(int index, int data){
if (this.next != null){
// 进入下一个节点
currentIndex += 1;
if (currentIndex == index){
// 新建一个节点
Node node = new Node(data);
// 新节点的下一个节点为原来节点的下一个节点
node.next = this.next;
// 原节点的下一个节点为新节点
this.next = node;
return true;
}else {
return this.next.insetFrontNode(index, data);
}
}else {
// 如果为空则到达链表末尾 直接添加元素
this.addTailNode(data);
return true;
}
}
具体代码可参考:
https://github.com/JacksonMike/Java_ultimate/blob/master/LinkedListDemo.java
四、链表的特点和适用场景
- 链表和数组都属于线性结构。
- 链表适合插入和删除。
- 但是查找元素时需要遍历，不支持随机查找，不宜过长，否则会导致性能降低。
- 链表可以实现栈或者队列等数据结构。
