企业官网建设流程全解析

一.链表概述

1.定义

在计算机科学中，链表是数据元素的线性集合，其每个元素都指向下一个元素，元素上存储不连续。

2.单向链表代码实现

package com.SinglyLinkedList; public class SingLinkedList { private Node head = null;//头指针 //节点类(内部类，对外暴露少) private static class Node { int value;//节点值 Node next;//下一个节点指针 //构造方法 public Node(int value,Node next) { this.next = next; this.value = value; } } //添加节点 public void addFirst(int value) { //1.链表为空 //head = new Node(value,null); //2.链表不为空 head = new Node(value, head);//这个代码能处理链表非空和链表为空的情况 } //遍历链表 public void loop1(int[] arr){ Node p = head;//创建一个指针p，指向头指针head while (p != null){ System.out.print(p.value+" "); p = p.next;//移动指针让p指向下一个节点,直到p为null } } public void loop2(int[] arr){ for (Node p = head; p != null; p = p.next) { System.out.print(p.value+" "); } } //查找最后一个节点 private Node findLast(int value){ if (head == null){//链表为空的情况 return null; } Node p = head; for(; p != null; p = p.next){ if (p.value == value){ return p; } } return p; } //添加最后一个节点 public void addLast(int value){ Node last = findLast(value); if (last == null){ addFirst(value); }else { last.next = new Node(value,null); } } //查找索引值 private Node findNode(int index){ int i = 0; for (Node p = head;p != null;p = p.next,i++) { if (i == index){ return p;//索引值存在,返回该节点 } } return null;//索引值不存在 } //获取索引值 public void get(int index){ Node node = findNode(index); if (node != null){ System.out.println(node.value); }else { System.out.println("索引值不存在"); } } //往链表的任意一个索引位置加入一个新的元素 public void insert(int index,int value){ if (index == 0){ addFirst(value);//添加第一个节点 } Node node = findNode(index - 1);//表示上一个节点 if (node == null){//索引值不存在的情况 addFirst(value); return; } node.next = new Node(value,node.next);//创建一个新节点,插入到指定位置 } //删除第一个位置的索引值 public void removeFirst(){ if (head == null){//链表为空的情况 return; } head = head.next;//让head指向第二个节点 } //按索引位置来进行删除 public void remove(int index){ if (index == 0){ //索引值为0的情况 removeFirst();//删除第一个节点 return; } Node node = findNode(index - 1);//上一个节点 // 如果当前节点为空，则移除链表的第一个节点并返回 if (node == null){ //索引值不存在的情况 removeFirst(); return; } // 获取要被删除的下一个节点 Node removed = node.next; // 如果要删除的节点为空，则直接返回 if (removed == null){ //索引值不存在的情况 return; } node.next = removed.next;//删除指定位置的节点 } //单向链表（带哨兵） private static class SinglyLinkedList { private Node head = new Node(0,null); } }

什么时候要加static？

当某一个内部类使用了外部类的一个成员变量时，就不能加static；而当内部类是相对独立的，跟外部类的成员变量没有任何关系时，这时候就可以加static。

3.带哨兵节点

package com.SinglyLinkedList; public class SingLinkedList { private Node head = new Node(666,null);//头指针 //节点类(内部类，对外暴露少) private static class Node { int value;//节点值 Node next;//下一个节点指针 //构造方法 public Node(int value,Node next) { this.next = next; this.value = value; } } //添加节点 public void addFirst(int value) { /* //1.链表为空 //head = new Node(value,null); //2.链表不为空 head = new Node(value, head);//这个代码能处理链表非空和链表为空的情况*/ insert(0,value); } //遍历链表 public void loop1(int[] arr){ Node p = head.next;//创建一个指针p，指向头指针head的下一个节点，跳过了头指针 while (p != null){ System.out.print(p.value+" "); p = p.next;//移动指针让p指向下一个节点,直到p为null } } public void loop2(int[] arr){ for (Node p = head.next; p != null; p = p.next) {//要从哨兵的下一个元素开始遍历 System.out.print(p.value+" "); } } //查找最后一个节点 private Node findLast(int value){ /* if (head == null){//链表为空的情况 return null; }*/ Node p = head; for(; p != null; p = p.next){ if (p.value == value){ return p; } } return p; } //添加最后一个节点 public void addLast(int value){ /* Node last = findLast(value); if (last == null){ addFirst(value); }else { last.next = new Node(value,null); }*/ Node last = findLast(value); last.next = new Node(value,null); } //查找索引值 private Node findNode(int index){ int i = -1; for (Node p = head;p != null;p = p.next,i++) { if (i == index){ return p;//索引值存在,返回该节点 } } return null;//索引值不存在 } //获取索引值 public void get(int index){ Node node = findNode(index); if (node != null){ System.out.println(node.value); }else { System.out.println("索引值不存在"); } } //往链表的任意一个索引位置加入一个新的元素 public void insert(int index,int value){ /* if (index == 0){ addFirst(value);//添加第一个节点 }*/ Node node = findNode(index - 1);//表示上一个节点 if (node == null){//索引值不存在的情况 addFirst(value); return; } node.next = new Node(value,node.next);//创建一个新节点,插入到指定位置 } //删除第一个位置的索引值 public void removeFirst(){ /* if (head == null){//链表为空的情况 return; } head = head.next;//让head指向第二个节点*/ remove(0); } //按索引位置来进行删除 public void remove(int index){ /* if (index == 0){ //索引值为0的情况 removeFirst();//删除第一个节点 return; }*/ Node node = findNode(index - 1);//上一个节点 // 如果当前节点为空，则移除链表的第一个节点并返回 if (node == null){ //索引值不存在的情况 removeFirst(); return; } // 获取要被删除的下一个节点 Node removed = node.next; // 如果要删除的节点为空，则直接返回 if (removed == null){ //索引值不存在的情况 return; } node.next = removed.next;//删除指定位置的节点 } //单向链表（带哨兵） private static class SinglyLinkedList { private Node head = new Node(0,null); } }

二.双向链表

package com.SinglyLinkedList; import org.w3c.dom.Node; public class DoublyLinkedSentinel { private Node head;//头指针 private Node tail;//尾指针 static class Node{ Node prev;//上一个节点指针 int value;//节点值 Node next;//下一个节点指针 public Node(Node prev, int value, Node next) { this.value = value; this.prev = prev; this.next = next; } } //创建一个头尾指针 public DoublyLinkedSentinel(){ head = new Node(null,666,null); tail = new Node(null,888,null); } //查找指定位置的节点 private Node findNode(int index){ int i = -1; for(Node p = head;p !=tail; p = p.next,i++){ if (i == index){ return p; } } return null; } //添加首节点 public void addFirst(int value){ } //删除节点 public void removeFirst(){ remove(0); } //添加尾节点 public void addLast(int value){ Node last = tail.prev; Node addad = new Node(last,value,tail); last.next = addad; tail.prev = addad; } //删除尾节点 public void removeLast(){ Node removed = tail.prev;//通过伪哨兵拿到最后一个节点 if (removed == head){//当删除的节点为头节点时 //抛异常 throw new RuntimeException("链表为空"); } Node prev = removed.prev;//拿到前一个节点 prev.next = tail;//让上一个节点指向伪哨兵 tail.prev = prev;//再让伪哨兵的prev节点指向前一个节点 } //添加指定位置的节点 public void insert(int index,int value){ Node prev = findNode(index - 1); if (prev == null){ //抛异常 throw new RuntimeException("链表为空"); } Node next = prev.next; Node inserted = new Node(prev,value,next);//新节点 prev.next = inserted; next.prev = inserted; } //删除指定位置的节点 public void remove(int index){ Node prev = findNode(index -1); if (prev == null){//索引值为空的情况下 //抛异常 throw new RuntimeException("链表为空"); } Node removed = prev.next; if (removed == tail){//当删除的节点为哨兵节点时 //抛异常 throw new RuntimeException("索引值不存在"); } Node next = removed.next; prev.next = next; next.prev = prev; } }

三.双向环形链表

package com.SinglyLinkedList; public class DoublyLinkedListSentinel2 { private static class Node { Node prev; int value; Node next; public Node(Node prev, int value, Node next) { this.prev = prev; this.value = value; this.next = next; } } private Node sentinel = new Node(null, -1, null); public DoublyLinkedListSentinel2() { // 创建哨兵节点并让它指向自己形成环形结构 sentinel.prev = sentinel; sentinel.next = sentinel; } // 添加到第一个节点 public void addFirst(int value) { Node a = sentinel; Node b = sentinel.next; Node added = new Node(a, value, b); a.next = added; b.next = added; } // 添加到最后一个节点 public void addLast(int value) { Node a = sentinel.prev; Node b = sentinel; Node added = new Node(a, value, b); a.next = added; b.prev = added; } // 删除第一个节点 public void removeFirst() { Node removed = sentinel.next; if (removed == sentinel) { throw new RuntimeException("List is empty"); } Node a = sentinel; Node b = removed.next; a.next = b; b.prev = a; } // 删除最后一个节点 public void removeLast() { Node removed = sentinel.prev; if (removed == sentinel){ throw new RuntimeException("List is empty"); } Node a = removed.prev; Node b = sentinel; a.next = b; b.prev = a; } // 查找值 public Node findByvalue(int value){ Node p = sentinel.next; while (p != sentinel){ if (p.value == value){ return p; } p = p.next; } return null; } //根据值来进行删除 public void remove(int value){ Node removed = findByvalue(value); if (removed == null){ return; } Node a = removed.prev; Node b = removed.next; a.next = b; b.prev = a; } }

四.多路递归-斐波那契数列

package com.Fibonacci; // 斐波那契数列 public class Fibonacca { public static int f(int n){ if (n == 0) { return 0; } if (n == 1) { return 1; } int f1 = f(n - 1); int f2 = f(n - 2); return f1 + f2; } }

使用Memoization记忆法也称备忘录优化后代码：

// 斐波那契数列 public class Fibonacca { public static int feibonacci(int n){ int[] cache = new int[n + 1]; Arrays.fill(cache, -1);// 填充-1 cache[0] = 0; cache[1] = 1; return f(n,cache); } public static int f(int n,int[] cache) { /* if (n == 0) { return 0; } if (n == 1) { return 1; }*/ if (cache[n] != -1) { return cache[n]; } int f1 = f(n - 1, cache); int f2 = f(n - 2,cache); cache[n] = f1 + f2;// 存入数组 return cache[n]; } }

求递归求和n+n-1,....+1

public class Fibonacca2 { //目标：写一个递归求和 public static long sum(int n){ if(n == 1){ return 1; } return sum(n-1) + n; } }

这里会出现爆栈问题：

爆栈（Stack Overflow）通常指程序运行时调用栈（Call Stack）超出系统或语言规定的限制，导致程序崩溃。常见于递归函数未设置终止条件或深度过大时。

常见原因

• 无限递归：递归函数缺少基线条件（Base Case），导致无限调用自身。
• 递归深度过大：即使有终止条件，但递归层级超过栈空间限制（如默认栈大小通常为1-8MB）。
• 大规模局部变量：函数内声明超大数组或对象，占用栈空间。

解决方法

• 优化递归算法
• 尾递归优化
• 增加栈空间限制
• 分治或动态规划
• 监控栈深度

但实际上要从根本上解决爆栈问题，就是要避免使用递归，把递归代码改成循环代码！！！

五.递归的时间复杂度计算