推荐阅读
算法day01_ 27. 移除元素、977.有序数组的平方
算法day02_209.长度最小的子数组
算法day03_ 59.螺旋矩阵II
目录
- 推荐阅读
- 链表理论知识
- 单向链表（单链表）
- 定义单链表
- 单链表添加下一个节点
- 单链表中插入一个节点
- 单链表中删除下一节点
- 遍历单链表
- 双向链表（双链表）
- 定义双链表
- 双链表增加新节点
- 双链表插入一节点
- 双链表删除一节点
- 循环单链表
- 定义循环单链表
- 循环单链表中插入一节点
- 循环单链表中删除一节点
- 遍历循环单链表
- 数组与链表性能比较
链表理论知识
链表（Linked list）是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存入下一个节点的地址。
链表的入口节点称为链表的头结点也就是head
链表是通过指针域的指针链接在内存中各个节点，它在内存中不是连续分布的，而是散乱分布在内存中的某个地址上。
单向链表（单链表）
链表中存入当前节点的值（数据域）和指向下一个节点的指针（指针域）
单链表相关操作
定义单链表
// 定义一个单链表
public class Node {
private int data;//存储数据域
private Node nextNode;//存储指向下一个的指针
//编写构造方法
public Node(){
}
public Node(int data){
this.data=data;
}
public Node(int data,Node nextNode){
this.data=data;
this.nextNode=nextNode;
}
// 获取下一个节点的方法
public Node nextNode() {
return this.nextNode;
}
// 获取节点中的数据
public int getData() {
return this.data;
}
}
单链表添加下一个节点
//在单链表中添加、插入一个节点
public Node append(Node node){
//获得当前节点
Node currentNode=this;
//循环往后找，直到该节点为空
while (true){
//获得下一个节点
Node nextNode=currentNode.nextNode;
// 如果下一个节点为 Null, 当前节点已经是最后一个节点
if (nextNode==null){
break;
}
//赋值给当前节点
currentNode=nextNode;
}
//把添加的节点追加到当前的节点上
currentNode.nextNode=node;
return this;
}
单链表中插入一个节点
//插入节点
public void after(Node node){
//取出下一节点，用作下下节点
Node newNode=this.nextNode;
//把插入节点作为下一节点
this.nextNode=node;
//把下下节点作为插入节点的下一个节点
node.nextNode=newNode;
}
单链表中删除下一节点
删除操作主要就是将当前节点的指针指向下下一个节点。
//删除下一节点
public void remove(){
//取出下下一节点
Node newNode= this.nextNode.nextNode;
//把下下一个节点设置为当前节点的下一个节点
this.nextNode=newNode;
}
遍历单链表
//遍历链表
public void showList(){
//当前链表
Node currentNode=this;
while (true){
System.out.println(currentNode.data+",");
//取出下一节点
Node nextNode=currentNode.nextNode;
//如果为空，跳出循环
if (nextNode==null){
System.out.println();
break;
}
}
}
双向链表（双链表）
当前节点的值（数据域）（指针域） 一个指向前一个节点的指针，一个指向后一个节点的指针。
双链表相关操作
定义双链表
public class DoubleNode {
//上一个节点
private DoubleNode preNode;
private int data;
//下一个节点
private DoubleNode nextNode;
public DoubleNode(int data){
this.data=data;
}
public DoubleNode getPreNode() {
return preNode;
}
public int getData() {
return data;
}
public DoubleNode getNextNode() {
return nextNode;
}
}
双链表增加新节点
//增加节点
public void add(DoubleNode node){
//当前节点
DoubleNode currentNode=this;
//当前节点的下一个节点
DoubleNode newNode=this.nextNode;
//新节点作为当前节点的下一个节点
this.nextNode=node;
node.preNode=currentNode;
// 原来的下一个节点作为新节点的下一个节点
node.nextNode=newNode;
// 让原来的下一个节点的上一个节点为当前新节点
newNode.preNode=node;
}
双链表插入一节点
//插入一节点
public void insert(DoubleNode node){
DoubleNode currentNode=this;
//取出下一节点，用作下下节点
DoubleNode newNode=this.nextNode;
//把插入节点作为下一节点
currentNode.nextNode=node;
node.preNode=currentNode;
//把下下节点作为插入节点的下一个节点
node.nextNode=newNode;
newNode.preNode=node;
}
双链表删除一节点
//删除一节点
public void delete(){
//获取当前节点
DoubleNode currentNode=this;
// 取出下下一个节点
DoubleNode newNode=this.nextNode.nextNode;
// 把下下一个节点设置为当前节点的下一个节点
currentNode.nextNode=newNode;
newNode.preNode=currentNode;
}
循环单链表
循环链表，链表首尾相连，用于解决约瑟夫环问题。
循环单链表相关操作
定义循环单链表
public class forList {
private int data;
private forList nextNode;
public forList(int data){
this.data=data;
}
public int getData() {
return data;
}
public forList getNextNode() {
return nextNode;
}
}
循环单链表中插入一节点
public void insert(forList node){
forList currentNode=this;
//取出下一节点，用作下下节点
forList nextNode=this.nextNode;
//把插入节点作为下一节点
currentNode.nextNode=node;
//把下下节点作为插入节点的下一个节点
node.nextNode=nextNode;
}
循环单链表中删除一节点
//删除某一节点
public void delete(){
// 取出下下一个节点
forList newNode=this.nextNode.nextNode;
// 把下下一个节点设置为当前节点的下一个节点
this.nextNode=newNode;
}
遍历循环单链表
//遍历所有节点
public void showAllNode(){
forList currentNode=this;
while (true){
System.out.println("当前节点："+currentNode.data);
if (currentNode.nextNode==null){
System.out.println("已经为最后一个节点");
break;
}
}
}
数组与链表性能比较
数组在定义的时候，长度就是固定的，如果想改动数组的长度，就需要重新定义一个新的数组。
链表的长度可以是不固定的，并且可以动态增删， 适合数据量不固定，频繁增删，较少查询的场景。
