链表数据结构全解：单向链表、双向链表与经典操作实现

一.链表概述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]; } }求递归求和nn-1,....1public 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。大规模局部变量函数内声明超大数组或对象占用栈空间。解决方法优化递归算法尾递归优化增加栈空间限制分治或动态规划监控栈深度但实际上要从根本上解决爆栈问题就是要避免使用递归把递归代码改成循环代码五.递归的时间复杂度计算