1. 链表是以节点的形式来存储，是链式存储
2. 每个节点蕴含 data 域，next 域：指向下一个节点
3. 链表的各个节点不肯定是间断存储
4. 链表分带头节点的链表和没有头节点的链表，依据理论的需要来确定
单链表
a. 减少节点思路剖析
借助辅助节点，找到最初一个节点的 next 指向新节点
b. 删除节点思路剖析
借助辅助节点，找到删除节点的前一个节点 temp
temp.next = temp.next.next
c. 批改节点思路剖析
借助辅助节点，遍历找到该节点而后批改
d. 遍历链表思路剖析
借助辅助节点，遍历
e. 获取到单链表的节点的个数
遍历，累加
f. 查找单链表中的倒数第 k 个节点
遍历至总长度 - k 的节点即为倒数第 k 个节点
g. 单链表的反转
新建反转头节点 reverseHead，遍历原链表，将节点一个个插入反转俩表的第一个节点，最初再把 head.next = reverseHead.next
h. 从头到尾打印单链表
用栈先进后出个性
import java.util.Stack;
public class SingleLinkedListDemo {public static void main(String[] args) {SingleLinkedList singleLinkedList = new SingleLinkedList();
Node node1 = new Node(1,"1");
Node node2 = new Node(2,"2");
Node node3 = new Node(3,"3");
Node node4 = new Node(4,"4");
singleLinkedList.add(node1);
singleLinkedList.add(node2);
singleLinkedList.add(node3);
singleLinkedList.add(node4);
singleLinkedList.list();
// singleLinkedList.del("3");
// singleLinkedList.list();
// singleLinkedList.update(new Node(2,"10"));
// singleLinkedList.list();
// singleLinkedList.reversetList();
// singleLinkedList.list();
singleLinkedList.reversePrint();}
}
class SingleLinkedList {
// 先初始化一个头节点, 头节点不要动
private Node head = new Node(0,"");
// 增加节点到单向链表
//1. 找到以后链表的最初节点
//2. 将最初这个节点的 next 指向新的节点
public void add(Node Node) {
// 因为 head 节点不能动，因而咱们须要一个辅助遍历 temp
Node temp = head;
// 遍历链表，找到最初
while (temp.next != null) {temp = temp.next;}
// 当退出 while 循环时，temp 就指向了链表的最初
// 将最初这个节点的 next 指向新的节点
temp.next = Node;
}
// 批改节点的信息, 依据 no 编号来批改
public void update(Node newNode) {
// 找到须要批改的节点, 依据 no 编号
// 定义一个辅助变量
Node temp = head.next;
while(temp != null) {if(temp.index == newNode.index) {
temp.data = newNode.data;
break;
}
temp = temp.next;
}
}
// 删除节点
// 咱们在比拟时，是 temp.next.data 和须要删除的节点的 data 比拟
public void del(String data) {
Node temp = head;
while (temp.next != null) {if (temp.next.data.equals(data)) {
temp.next = temp.next.next;
break;
}
temp = temp.next; //temp 后移，遍历
}
}
// 显示链表[遍历]
public void list() {
Node temp = head.next;
while (temp != null) {System.out.println(temp.data);
// 将 temp 后移
temp = temp.next;
}
}
// 获取到单链表的节点的个数, 不统计头节点
public int getLength() {
int length = 0;
Node temp = head.next;
while (temp != null) {
length ++;
// 将 temp 后移
temp = temp.next;
}
return length;
}
// 查找单链表中的倒数第 k 个结点
//1. 编写一个办法，一个 k
//2. k 示意是倒数第 k 个节点
//3. 先把链表从头到尾遍历，失去链表的总的长度 getLength
//4. 失去 size 后，咱们从链表的第一个开始遍历 (size-k)个，就能够失去
//5. 如果找到了，则返回该节点，否则返回 null
public Node findLastKNode(int k) {
// 判断如果链表为空，返回 null
if(head.next == null) {return null;// 没有找到}
// 第一个遍历失去链表的长度(节点个数)
int size = getLength();
// 第二次遍历 size-k 地位，就是咱们倒数的第 K 个节点
// 先做一个 k 的校验
if(k <=0 || k > size) {return null;}
// 定义给辅助变量，for 循环定位到倒数的 index
Node temp = head.next; //3 // 3 - 1 = 2
for(int i =0; i< size-k; i++) {temp = temp.next;}
return temp;
}
// 将单链表反转
public void reversetList() {
// 如果以后链表为空，或者只有一个节点，无需反转，间接返回
if(head.next == null || head.next.next == null) {return;}
// 定义一个辅助的指针(变量)，帮忙咱们遍历原来的链表
Node cur = head.next;
Node next = null;// 指向以后节点 cur 的下一个节点
Node reverseHead = new Node(0, "");
// 遍历原来的链表，每遍历一个节点，就将其取出，并放在新的链表 reverseHead 的最前端
while(cur != null) {
next = cur.next;// 先临时保留以后节点的下一个节点，因为前面须要应用
cur.next = reverseHead.next;// 将 cur 的下一个节点指向新的链表的第一个节点
reverseHead.next = cur; // 将 cur 连贯到新的链表上
cur = next;// 让 cur 后移
}
// 将 head.next 指向 reverseHead.next , 实现单链表的反转
head.next = reverseHead.next;
}
// 能够利用栈这个数据结构，将各个节点压入到栈中，而后利用栈的先进后出的特点，就实现了逆序打印的成果
public void reversePrint() {if(head.next == null) {return;// 空链表，不能打印}
// 创立要给一个栈，将各个节点压入栈
Stack<Node> stack = new Stack<Node>();
Node cur = head.next;
// 将链表的所有节点压入栈
while(cur != null) {stack.push(cur);
cur = cur.next; //cur 后移，这样就能够压入下一个节点
}
// 将栈中的节点进行打印,pop 出栈
while (stack.size() > 0) {System.out.println(stack.pop().data); //stack 的特点是先进后出
}
}
}
// 定义 Node
class Node {
public int index;// 序号
public String data;// 数据
public Node next; // 指向下一个节点
public Node(int index,String data) {
this.index = index;
this.data = data;
}
}
双向链表
双向链表的节点比单链表多一个 pre 节点
a. 减少节点思路剖析
与单链表一样，借助辅助节点，找到最初一个节点的 next 指向新节点，但双向链表的新节点还需指向最初一个节点
temp.next = newNode;
newNode.pre = temp;b. 删除节点思路剖析
与单链表不同，能够实现节点的自我删除，找到这个节点 temp
temp.pre.next = temp.next;
if(temp.next != null){
// 若最初一个节点执行上面代码则会报空指针异样，temp.next = null
temp.next.pre = tem.prel;
}c. 批改节点思路剖析
与单链表一样，借助辅助节点，遍历找到该节点而后批改
d. 遍历链表思路剖析
与单链表一样，借助辅助节点，向后遍历
环形链表和约瑟夫问题
//TODO