[数据结构与算法]【JAVA SE】数据结构、手写双向非循环链表 知识点总结与整理(思维导图)

1. 数据结构-链表
   1. 简介与分类
   2. 特殊例子(只有一个节点)
   3. 特点
2. 手写双向给循环链表(源码体现)
   1. 文案最下面附代码
3. 对比MyArraylist和Mylinedlist
4. 数据结构-栈(Stack)(后续笔记中会深入)
   1. 简介
   2. 特点
   3. 简要代码演示
5. 数据结构-数(Tree)(要理解完全二叉数的含义哦(⊙o⊙))
   1. 简介
   2. 二叉树
   3. 查找树
   4. 平衡二叉树
   5. 红黑树
6. 数据结构-堆(Heap)(后续笔记中会深入)
7. 数据结构-队列
8. 数据结构-图(Graph)

(如果大家没有对象,一定要new个对象哦!-------野猪行为)

1. 手写双向给循环链表(源码体现)
   1. 异常包

      
      //自定义异常
      public class LinkedListExecption extends RuntimeException {
          public LinkedListExecption(String message) {
              super(message);
          }
      
          public LinkedListExecption() {
          }
      }
      

      ?
   2. MyList<E> 接口

      //自定义接口   规范(添加的功能, 具体细节由实现类完成 ...)
      public interface MyList<E> {
      
          //1.添加元素 方便添加各种类型的数据, 使用所有类型的父类Object
          //添加的功能
          void add(E e);
      
          //2.查询元素
          E get(int index);
      
          //3.查询存储元素的个数
          int size();
      
          //4.变更元素
          boolean set(E e, int index);
      
          //5.删除元素
          boolean remove(int index);
      
          //6.删除元素
          boolean remove(E e);
      }
      

   3. MyLinkedList<E> 实现类

      package com.bjsxt.service;
      import com.bjsxt.execption.LinkedListExecption;
      //自定义显示类, 实现接口中的规范(添加 删除 修改 变更 获取存储数量)
      //双向列表的实现
      public class MyLinkedList<E> implements MyList<E> {
          //创建头结点 (只要拿到头结点, 就可以获取到后续的所有结点)
          private Node<E> first;
          //创建尾结点(只要拿到尾结点, 就可以获取前边所有的结点)
          private Node<E> last;
          //记录当前链表中存储了多少个数据(链表没有下表, 此属性就是记录存入数据的个数)
          private int count;
      
          @Override//查询结点信息  index -> 第几个被添加的数据(从0开始)
          public E get(int index){
              //检查index是否合格
              checkIndex(index);
              return getNode(index).item;
          }
      
      
          @Override//返回链表中存储了多少个数据
          public int size() {
              return count;
          }
      
      
          //检查用户输入的index是否合格
          private void checkIndex(int index) throws LinkedListExecption {
              if(index<0 || index>count-1){
                  throw new LinkedListExecption("输入的index有误, 最大index为 :"+(count-1)+" ,最小index为: 0");
              }
          }
      
      
      
          //创建结点的内部类  此节点内部类只有当前的双向列表需要, 所以创建为内部类
          private class Node<E>{
              //1.前一个结点的地址
              Node<E> pre;
              //2.当前结点的值
              E item;
              //3.下一个节点的地址
              Node<E> next;
              public Node(Node<E> pre, E item, Node<E> next) {
                  this.pre = pre;
                  this.item = item;
                  this.next = next;
              }
          }
      
      
      
          /*
          * 头插和尾插
          *   先添加的结点作为尾节点-> 尾插
          *   先添加的结点作为尾节点-> 头插
          * */
          //尾插法(新插入的结点作为新的尾结点)
          public void addLast(E e){
              //1.将目前的尾结点存储起来(方便后续的操作属性)
              Node<E> oldLast = this.last;
              //2.创建新的结点
              Node<E> newLast = new Node<>(oldLast, e, null);
              //3.将新创建的结点设置为尾结点
              this.last = newLast;
              //4.判断
              if(oldLast == null){//此时链表中,没有任何的结点 新创建的结点即为尾结点又为头结点
                  this.first = newLast;
              }else {//链表中存在尾结点, 将旧的尾结点中存储下个结点地址改变为新尾结点的地址
                  oldLast.next = newLast;
              }
              count++;
          }
      
      
          //头插法(新插入的结点作为新的头结点)
          public void addFirst(E e){
              //1.存储现在的头节点
              Node<E> oldFirst = this.first;
              //2.创建新节点
              Node<E> newFirst = new Node<>(null, e, oldFirst);
              //3.指定新创建的结点尾头结点
              this.first = newFirst;
              //4.判断
              if(oldFirst == null){//5.链表中没有结点, 新插入的结点即为头结点又为尾结点
                  this.last = newFirst;
              }else{
                  oldFirst.pre = newFirst;
              }
              count++;
          }
      
          @Override//向链表中添加数据
          public void add(E e) {
              //使用add插入时, 默认尾插
              addLast(e);
          }
      
      
      
          @Override//修改节点中值  第几个数据从0开始
          public boolean set(E e, int index) {
              checkIndex(index); //检查index是否合格
              try {
                  //1.获取要修改值得节点
                  Node<E> node = getNode(index);
                  //2.修改节点中的值
                  node.item = e;
                  return true;
              } catch (Exception ex) {
                  ex.printStackTrace();
                  return false;
              }
          }
      
      
          @Override//删除节点  第几个数据从0开始
          public boolean remove(int index) {
              //检查index是否合格
              checkIndex(index);
              //1.获取删除的节点(头节点 尾节点  非头非尾)
              Node<E> node = getNode(index);
              //Node<E> pre = node.pre; //该节点的上个节点
              //Node<E> next = node.next;//该节点的下个节点
              //情况一: 删除的为头节点(node.pre==null)
              if(node.pre==null){
                  Node<E> next = node.next;
                  next.pre = null;
                  this.first = next; //设置新的头节点
              }else if(node.next==null){//情况二: 删除的为尾节点(node.next==null)
                  Node<E> pre = node.pre;
                  pre.next = null;
                  this.last = pre;//设置新的尾节点
              }else{//情况三: 删除的为非尾节点非头节点
                  /*
                  * 1.将该节点的上个节点 存储下个节点的地址 改成该节点的下个节点
                  * 2.将该节点的下个节点 存储上个节点的地址 改成该节点的上个节点
                  * */
                  Node<E> pre = node.pre; //该节点的上个节点
                  Node<E> next = node.next;//该节点的下个节点
                  pre.next = next;
                  next.pre = pre;
              }
              node = null;
              count--;
              return true;
          }
      
      
      
          //获取节点方法
          private Node<E> getNode(int index){
              //查询的优化
              /*
               *   如果index < ((cout-1)>>1) 从前向后查询
               *   如果index >= ((cout-1)>>1) 从向前后查询
               * */
              /*if(index == 0){
                  return this.first.item;
              }
              if(index == count-1){
                  return this.last.item;
              }*/
              if (index < ((count)>>1)) { //如果index < ((cout-1)>>1) 从前向后查询
                  //1.获取头结点
                  Node<E> node = this.first;
                  //2.根据index遍历  index->用户添加的第几个数据(从零开始计算的)
                  for (int i = 0; i < index; i++) {
                      //获取下一个节点 赋值给当前的node变量
                      node = node.next;
                  }
                  return node;
              } else { //如果index > ((cout-1)>>1) 从向前后查询
                  //1.获取尾结点
                  Node<E> node = this.last;
                  //2.根据index遍历  index->用户添加的第几个数据(从零开始计算的)
                  for (int i = 0; i < count-1-index; i++) {
                      node = node.pre;
                  }
                  return node;
              }
          }
      
      
      }
      

2. ?