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的特点是先进后出 } }}//定义Nodeclass 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 = nulltemp.next.pre = tem.prel; }c.批改节点思路剖析
与单链表一样，借助辅助节点，遍历找到该节点而后批改
d.遍历链表思路剖析
与单链表一样，借助辅助节点，向后遍历
环形链表和约瑟夫问题
//TODO