链表理论知识
链表（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; } } }
数组与链表性能比较
数组在定义的时候，长度就是固定的，如果想改动数组的长度，就需要重新定义一个新的数组。
链表的长度可以是不固定的，并且可以动态增删， 适合数据量不固定，频繁增删，较少查询的场景。
