【从蛋壳到满天飞】JAVA 数据结构解析和算法实现-链表
前言
【从蛋壳到满天飞】JAVA 数据结构解析和算法实现，全部文章大概的内容如下：
Arrays(数组)、Stacks(栈)、Queues(队列)、LinkedList(链表)、Recursion(递归思想)、BinarySearchTree(二分搜索树)、Set(集合)、Map(映射)、Heap(堆)、PriorityQueue(优先队列)、SegmentTree(线段树)、Trie(字典树)、UnionFind(并查集)、AVLTree(AVL 平衡树)、RedBlackTree(红黑平衡树)、HashTable(哈希表)
源代码有三个：ES6（单个单个的 class 类型的 js 文件） | JS + HTML（一个 js 配合一个 html）| JAVA (一个一个的工程)
全部源代码已上传 github， 点击我吧 ，光看文章能够掌握两成，动手敲代码、动脑思考、画图才可以掌握八成。
本文章适合 对数据结构想了解并且感兴趣的人群，文章风格一如既往如此，就觉得手机上看起来比较方便，这样显得比较有条理，整理这些笔记加源码，时间跨度也算将近半年时间了，希望对想学习数据结构的人或者正在学习数据结构的人群有帮助。
链表 Linked List
- 链表是最基础的动态数据结构
-
链表是非常重要的线性数据结构
- 以下三种，底层都是依托静态数组，靠 resize 解决固定容量问题。
- 动态数组：所谓动态，是从用户的角度上来看的。
- 栈
- 队列
-
链表是真正的动态数据结构
- 它是数据结构中的一个重点，
- 也有可能是一个难点，
- 它是最简单的一种动态数据结构，
- 其它更高级的动态数据结构有 二分搜索树、Trie、
- 平衡二叉树、AVL、红黑树等等，
- 熟悉了最简单的动态数据结构，
- 那么对于更高级的也会比较容易掌握了。
-
对于链表来说它涉及到了计算机领域一个非常重要的概念
- 更深入的理解引用（或者指针），
- 这个概念和内存相关，
- 在 java 里面不需要手动的管理内存，
- 但是对链表这种数据结构更加深入的理解，
- 可以让你对 引用、指针甚至计算机系统中
- 和内存管理相关很多话题有更加深入的认识。
-
链表本身也是有它非常清晰的递归结构的，
- 只不过由于链表这种数据结构它本身是一种线性的数据结构，
- 所以依然可以非常容易的使用循环的方式来对链表进行操作，
- 但是链表本身由于它天生也是具有这种递归结构的性质，
- 所以它也能让你更加深入的理解递归机制相应的这种数据结构，
- 在学习更加复杂的数据结构的时候，
- 对递归这种逻辑机制深入的理解是必不可缺的。
-
链表这种数据结构本身就具有功能性
- 它可以用来组成更加复杂的数据结构，
- 比如 图结构、hash 表、栈(链表版)、队列(链表版)，
- 所以他可以辅助组成其它数据结构。
什么是链表
-
数据存储在“节点”（Node）中
- 把数据存在一种单独的结构中，
- 这个结构通常管它叫做节点，
- 对于链表节点来说他通常只有两部分，
- 一部分就是存储真正的数据，
- 另一部分存储的是当前节点的下一个节点，
- 链表其实就像一个火车，每一个节点都是一节车厢，
- 在车厢中存储数据，而车厢和车厢之间还会进行连接，
- 以使得这些数据是整合在一起的，
- 这样用户可以方便的在所有的这些数据上进行查询等等其它的操作，
- 数据与数据之间连接就是用下面的这个 next 来完成的
class Node { E e; Node next; } -
链表的优点
- 真正的动态，不需要处理固定容量的问题，
- 它不像静态数组那样一下子 new 出来一片空间，
- 也根本不需要考虑这个空间是不是不够用，
- 也根本不用去考虑这个空间是不是开多了。
-
对于链表来说，你需要多少个数据。
- 你就可以生成多少个节点，
- 把它们挂接起来了，这就是所谓的动态。
-
链表的缺点
O(1)
数组和链表的对比
-
数组
scores[2]
-
链表
- 链表不适合用于索引有语意的情况。
- 最大的优点：动态存储。
-
对比
- 数组也可以没有语意，并不是所有的时候索引是有语意的，
- 也并不是所有有语意的这样的一个标志就适合做索引，如身份证号，
- 将一个静态数组改变为一个动态数组，
- 就是在应付不方便使用索引的时候有关数据存储的问题，
- 对于这样的存储数据的需求使用链表是更合适的，
- 因为链表最大的优点是动态存储。
-
要清楚什么时候使用数组这样的静态数据结构，
- 什么时候使用链表这类的动态数据结构。
-
简单的代码示例
MyLinkedListpublic class MyLinkedList<E> { // 隐藏内部实现，不需要让用户知道 private class Node { public E e; public Node next; public Node (E e, Node next) { this.e = e; this.next = next; } public Node (E e) { this(e, null); } public Node () { this(null, null); } @Override public String toString () { return e.toString(); } } }
在链表中进行添加、插入操作
-
链表是通过节点来装载元素
MyLinkedList
-
给自定义数组添加元素是从数组尾部开始添加，
- 给链表添加元素是从数组头部开始添加，
- 因为自定义数组有维护一个 size，
- 这个 size 指向的是下一个待添加元素的位置，
- 所以你直接将 size 做索引直接赋值即可，
- 有 size 这个变量在跟踪数组的尾巴，
- 而对于链表来说 有设置一个链表的头这样的一个变量，
- 也就是说有一个变量在跟踪链表的头，
- 并没有一个变量去跟踪链表的尾巴，
- 所以在链表头部添加元素是非常方便。
-
添加操作原理
node.next = head head = node
-
在链表头部添加元素非常简单，
- 只需要创建节点，让节点的 next 指向 head，
- 然后让 head 重新指向这个节点，也就是让 head 变成新的元素，
- 因为链表是从头部添加元素的。
-
在链表中间添加元素，
node.next = prev.next prev.next = node
-
在链表的操作中很多时候顺序非常重要，
- 如在链表中插入一个元素，在指定的元素后面插入一个元素，
- 并且不影响整个链表结构，和在链表中间添加元素一样，
- 把原本的
node.next = prev.next和prev.next = node - 的顺序变一下，
prev.next = node在前， -
node.next = prev.next在后，这样一来逻辑就不成立了， - 链表不仅断开了，而且新节点的 next 指向的是自己，死循环了，
- 所以一样的代码，顺序颠倒了，得到的结果就是错误的。
-
在链表的 index(0-based)位置添加元素 e
- 通过索引来操作链表，在链表中不是一个常用的操作，
- 因为在选择使用链表的时候通常就选择不使用索引了，
- 但是这个需求在面试等一些考题中出现的概率很大，
- 所以他的主要作用更多的是一个练习。
学习方式
-
如果刚接触链表，对链表不熟悉，
- 然后很多这种操作在脑子里不能非常快的反应出来，
- 不清楚他的意义是什么，那你可以使用纸笔来稍微画一下，
- 每一步程序逻辑的执行意味着当前这个链表变成了什么样子，
- 这个过程能够帮助你更加深入的理解程序，
- 包括在调试的时候来看你的程序到底为什么出了错误时，
- 非常非常有帮助的，不要犯懒，为了更加深入的理解你的程序，
- 不能只盯着你的代码去想，一定要写写画画，
- 必要的时候甚至根据你的程序进行具体的调试，
- 这些都是非常重要非常有帮助的。
代码示例 (class: MyLinkedList)
-
MyLinkedList
public class MyLinkedList<E> { // 隐藏内部实现，不需要让用户知道 private class Node { public E e; public Node next; public Node (E e, Node next) { this.e = e; this.next = next; } public Node (E e) { this(e, null); } public Node () { this(null, null); } @Override public String toString () { return e.toString(); } } private Node head; private int size; public MyLinkedList () { head = null; size = 0; } // ... // 其它的构造函数，例如传进来一个数组，将数组转换为链表 // 获取链表中元素的个数 public int getSize () { return size; } // 返回当前链表是否为空 public boolean isEmpty () { return size == 0; } // 在链表头部添加一个元素 e public void addFirst (E e) { // 写法一 // Node node = new Node(e, head); // head = node; // 写法二 // Node node = new Node(e); // node.next = head; // head = node; // 写法三 head = new Node(e, head); size ++; } // 在链表指定索引出插入一个元素 public void insert (int index, E e) { if (index < 0 || index > size) { throw new IllegalArgumentException("add error. index < 0 or index > size"); } if (index == 0) { addFirst(e); }else { // 第一个prev就是head Node prev = head; // 不断的搜索 一直通过next来进行检索 for (int i = 0; i < index - 1 ; i++) { prev = prev.next; } // 第一种方式 // Node node = new Node(e); // node.next = prev.next; // prev.next = node; // 第二种方式 prev.next = new Node(e, prev.next); size ++; } } // 在链表尾部添加一个元素 public void addLast (E e) { insert(size, e); } }
给链表设立虚拟头节点
-
在链表中进行指定索引处插入元素时
- 对链表头插入元素与对链表其它位置插入元素的逻辑有区别，
- 所以就导致每次操作都需要对索引进行判断，
- 如果你是在索引 0 的位置插入元素，那么就没有 prev(前一个元素),
- 自然就不可以使用
node.next = prev.next和prev.next = node了， - 那时候你可以直接使用
node.next = head和head = node， - 不过已经有了向链表头添加元素的方法了，
- 所以向头部插入元素时根本就不需要这么做，
- 这时候可以通过给链表设立虚拟头节点来解决这个问题。
-
为什么对链表头插入元素那么特殊？
- 因为插入元素时，必需要找到该索引位置的节点之前的一个节点(prev)，
- 而链表头(head)之前并没有任何节点，所以逻辑上就会特殊一些。
- 不过在链表的具体实现中有一个非常常用的技巧，
- 可以把链表头的这种特殊的操作与其它的操作一起统一起来，
- 其实这个方法的想法很简单，既然它没有链表头之前的节点，
- 那就自己造一个链表头之前的节点，
- 这个链表头之前的节点不会用来存储任何元素，存储的数据为空，
- 这个空节点就称之为整个链表头的 head，也可以叫它 dummyHead，
- 因为它就是一个假的 head，它也是为链表设立的虚拟头节点，
- 这样一来 链表的第一个元素就是 dummyHead 的 next 所对应的那个节点，
- 因为 dummyHead 这个位置的元素是根本不存在的，
- 对用户来讲也是根本没有意义的，
- 这只是为了编写逻辑方便而出现的一个虚拟的头节点，
- 所以一个这样的内部机制对用户来说也是不可见的，
- 用户不知道链表中有没有虚拟的头节点，
- 这和自定义的循环队列有点像，自定义循环队列中有一个不可用的空间，
- 有意识地去浪费一个空间，为了编写逻辑更加的方便，
- 从而也让性能在整体上得到了提升。
-
有了 dummyHead 之后就不需要处理头节点这个特殊的操作
- 因为当你在头部插入元素时，可以这样
-
node.next = dummyHead.next、dummyHead.next = node， - 这样你就解决了每次插入时都要进行一次逻辑判断了，
- 这样一来就说明了链表中所有的节点都有前一个节点了，
- 在初始的时候 dummyHead 指向的是索引为 0 的元素前一个位置的节点。
-
链表操作的实际原理
node.next = head.next;head = node; node.next = dummyHead.next; dummyHead.next = node; dummyHead.next
代码示例 (class: MyLinkedList)
-
MyLinkedList
public class MyLinkedList<E> { // 隐藏内部实现，不需要让用户知道 private class Node { public E e; public Node next; public Node (E e, Node next) { this.e = e; this.next = next; } public Node (E e) { this(e, null); } public Node () { this(null, null); } @Override public String toString () { return e.toString(); } } private Node dummyHead; private int size; public MyLinkedList () { dummyHead = new Node(null, null); size = 0; } // ... // 其它的构造函数，例如传进来一个数组，将数组转换为链表 // 获取链表中元素的个数 public int getSize () { return size; } // 返回当前链表是否为空 public boolean isEmpty () { return size == 0; } // 在链表头部添加一个元素 e public void addFirst (E e) { // 写法一 // Node node = new Node(e, head); // head = node; // 写法二 // Node node = new Node(e); // node.next = dummyHead.next; // dummyHead.next = node; // 写法三 // dummyHead.next = new Node(e, dummyHead.next); // size ++; // 写法四 insert(0, e); } // 在链表指定索引出插入一个元素 public void insert (int index, E e) { if (index < 0 || index > size) { throw new IllegalArgumentException("add error. index < 0 or index > size"); } // 第一个prev就是dummyHead Node prev = dummyHead; // 不断的搜索 一直通过next来进行检索 for (int i = 0; i < index ; i++) { prev = prev.next; } // 第一种方式 // Node node = new Node(e); // node.next = prev.next; // prev.next = node; // 第二种方式 prev.next = new Node(e, prev.next); size ++; } // 在链表尾部添加一个元素 public void addLast (E e) { insert(size, e); } }
在链表中进行遍历、查询、修改操作
-
如果要找指定索引元素的前一个节点
dummyHead dummyHead.next
代码示例 (class: MyLinkedList, class: Main)
-
MyLinkedList
public class MyLinkedList<E> { // 隐藏内部实现，不需要让用户知道 private class Node { public E e; public Node next; public Node (E e, Node next) { this.e = e; this.next = next; } public Node (E e) { this(e, null); } public Node () { this(null, null); } @Override public String toString () { return e.toString(); } } private Node dummyHead; private int size; public MyLinkedList () { dummyHead = new Node(null, null); size = 0; } // ... // 其它的构造函数，例如传进来一个数组，将数组转换为链表 // 获取链表中元素的个数 public int getSize () { return size; } // 返回当前链表是否为空 public boolean isEmpty () { return size == 0; } // 在链表头部添加一个元素 e public void addFirst (E e) { // 写法一 // Node node = new Node(e, head); // head = node; // 写法二 // Node node = new Node(e); // node.next = dummyHead.next; // dummyHead.next = node; // 写法三 // dummyHead.next = new Node(e, dummyHead.next); // size ++; // 写法四 insert(0, e); } // 在链表指定索引出插入一个元素 public void insert (int index, E e) { if (index < 0 || index > size) { throw new IllegalArgumentException("add or insert error. index < 0 or index > size"); } // 第一个prev就是dummyHead Node prev = dummyHead; // 不断的搜索 一直通过next来进行检索，找指定索引的节点的前一个元素 for (int i = 0; i < index ; i++) { prev = prev.next; } // 第一种方式 // Node node = new Node(e); // node.next = prev.next; // prev.next = node; // 第二种方式 prev.next = new Node(e, prev.next); size ++; } // 在链表尾部添加一个元素 public void addLast (E e) { insert(size, e); } // get public E get (int index) { if (index < 0 || index >= size) { throw new IllegalArgumentException("get error. index < 0 or index >= size"); } Node cur = dummyHead.next; for (int i = 0; i < index ; i++) { cur = cur.next; } return cur.e; } // getFirst public E getFirst () { return get(0); } // getLast public E getLast () { return get(size - 1); } // set public void set (int index, E e) { if (index < 0 || index >= size) { throw new IllegalArgumentException("set error. index < 0 or index >= size"); } Node node = dummyHead.next; for (int i = 0; i < index; i++) { node = node.next; } node.e = e; } // contains public boolean contains (E e) { // 第一种方式 // Node node = dummyHead; // for (int i = 0; i < size - 1 ; i++) { // node = node.next; // // if (node.e.equals(e)) { // return true; // } // } // 第二种方式 Node node = dummyHead.next; while (node != null) { if (node.e.equals(e)) { return true; } else { node = node.next; } } return false; } @Override public String toString () { StringBuilder sb = new StringBuilder(); sb.append("链表长度：" + size + "，链表信息："); // // 写法一 // Node node = dummyHead.next; // while (node != null) { // sb.append(node + "->"); // node = node.next; // } // 写法二 for (Node node = dummyHead.next; node != null ; node = node.next) { sb.append(node + "->"); } sb.append("NULL"); return sb.toString(); } } -
Main
public class Main { public static void main(String[] args) { MyLinkedList<Integer> mkl = new MyLinkedList<Integer>(); for (int i = 1; i <= 5 ; i++) { mkl.addFirst(i); System.out.println(mkl); } mkl.insert(2, 88888); System.out.println(mkl); } }
在链表中进行删除操作
-
链表元素的删除
prev.next = delNode.next delNode.next = null delNode = delNode.next
代码示例 (class: MyLinkedList, class: Main)
-
MyLinkedList
public class MyLinkedList<E> { // 隐藏内部实现，不需要让用户知道 private class Node { public E e; public Node next; public Node (E e, Node next) { this.e = e; this.next = next; } public Node (E e) { this(e, null); } public Node () { this(null, null); } @Override public String toString () { return e.toString(); } } private Node dummyHead; private int size; public MyLinkedList () { dummyHead = new Node(null, null); size = 0; } // ... // 其它的构造函数，例如传进来一个数组，将数组转换为链表 // 获取链表中元素的个数 public int getSize () { return size; } // 返回当前链表是否为空 public boolean isEmpty () { return size == 0; } // 在链表头部添加一个元素 e public void addFirst (E e) { // 写法一 // Node node = new Node(e, head); // head = node; // 写法二 // Node node = new Node(e); // node.next = dummyHead.next; // dummyHead.next = node; // 写法三 // dummyHead.next = new Node(e, dummyHead.next); // size ++; // 写法四 insert(0, e); } // 在链表指定索引出插入一个元素 public void insert (int index, E e) { if (index < 0 || index > size) { throw new IllegalArgumentException("add or insert error. index < 0 or index > size"); } // 第一个prev就是dummyHead Node prev = dummyHead; // 不断的搜索 一直通过next来进行检索，找指定索引的节点的前一个元素 for (int i = 0; i < index ; i++) { prev = prev.next; } // 第一种方式 // Node node = new Node(e); // node.next = prev.next; // prev.next = node; // 第二种方式 prev.next = new Node(e, prev.next); size ++; } // 在链表尾部添加一个元素 public void addLast (E e) { insert(size, e); } // get public E get (int index) { if (index < 0 || index >= size) { throw new IllegalArgumentException("get error. index < 0 or index >= size"); } Node cur = dummyHead.next; for (int i = 0; i < index ; i++) { cur = cur.next; } return cur.e; } // getFirst public E getFirst () { return get(0); } // getLast public E getLast () { return get(size - 1); } // set public void set (int index, E e) { if (index < 0 || index >= size) { throw new IllegalArgumentException("set error. index < 0 or index >= size"); } Node node = dummyHead.next; for (int i = 0; i < index; i++) { node = node.next; } node.e = e; } // contains public boolean contains (E e) { // 第一种方式 // Node node = dummyHead; // for (int i = 0; i < size - 1 ; i++) { // node = node.next; // // if (node.e.equals(e)) { // return true; // } // } // 第二种方式 Node node = dummyHead.next; while (node != null) { if (node.e.equals(e)) { return true; } else { node = node.next; } } return false; } // remove public E remove (int index) { if (index < 0 || index >= size) { throw new IllegalArgumentException("remove error. index < 0 or index >= size"); } Node prev = dummyHead; for (int i = 0; i < index ; i++) { prev = prev.next; } Node delNode = prev.next; prev.next = delNode.next; size --; E e = delNode.e; delNode.next = null; return e; } // removeFirst public E removeFirst () { return remove(0); } // removeLast public E removeLast () { return remove(size - 1); } @Override public String toString () { StringBuilder sb = new StringBuilder(); sb.append("链表长度：" + size + "，链表信息："); // // 写法一 // Node node = dummyHead.next; // while (node != null) { // sb.append(node + "->"); // node = node.next; // } // 写法二 for (Node node = dummyHead.next; node != null ; node = node.next) { sb.append(node + "->"); } sb.append("NULL"); return sb.toString(); } } -
Main
public class Main { public static void main(String[] args) { MyLinkedList<Integer> mkl = new MyLinkedList<Integer>(); for (int i = 1; i <= 5 ; i++) { mkl.addFirst(i); System.out.println(mkl); } mkl.insert(2, 88888); System.out.println(mkl); mkl.remove(2); System.out.println(mkl); mkl.removeFirst(); System.out.println(mkl); mkl.removeLast(); System.out.println(mkl); } }
链表的时间复杂度分析
- 增：
O(n)：在只对链表头进行操作时为O(1) - 删：
O(n)：在只对链表头进行操作时为O(1) - 改：
O(n) - 查：
O(n)：只查链表头的元素时为O(1) -
链表增删改查的时间复杂度
- 整体上要比数组增删改查的时间复杂度要差，
- 因为数组有一个优势，
- 你有索引的话你就可以快速访问，
- 而链表没有这样的优势
- 但是链表的优势是，
- 如果你只对链表头进行增删的操作，
- 那么它的时间复杂度是 O(1)级别的，
- 而且它整体是动态的，所以不会大量的浪费内存空间。 6.链表适合做的事情
- 不去修改、也不去查任意的元素，
- 就算查，也只能查链表头的元素，
- 查的时候，只有那样才是 O(1)级别的时间复杂度，
- 并且增加删除的时候只对链表头进行操作，
- 只有在这种时候才会和数组整体的时间复杂度是一样的，
- 不过链表整体是动态的，不会去大量的浪费内存空间，
- 所以它具有一定的优势。
-
链表还有诸多的改进的方式
- 所以应用链表在一些情况下仍然是有它的优势的，
- 最最重要的是 链表本身是一种最最基础的动态数据结构，
- 对这种动态数据结构要深刻的理解和掌握，
- 对于学习更重要的动态数据结构是有巨大的帮助，
- 比如说二叉树、平衡二叉树、AVL、红黑树等等。
添加操作 O(n)
-
addLast(e)：O(n)- 会从头遍历到尾，
- 找到最后一个节点之后才能添加元素
-
addFirst(e)：O(1)- 直接从头部添加元素
-
insert(index, e)：O(n/2) = O(n)- 会去遍历链表中每一个节点，
- 检索到合适的位置才会添加这个元素。
删除操作 O(n)
-
removeLast()：O(n)- 会去遍历链表中每一个节点，
- 找到最后一个节点后才会删除
-
removeFirst()：O(1)- 直接从头部删除这个节点
-
remove(index)：O(n/2) = O(n)- 会去遍历链表中每一个节点，
- 检索到合适的位置才会移除这个元素
修改操作 O(n)
-
set(index, e)：O(n)- 会去遍历链表中每一个节点，
- 找到了合适位置的节点后，
- 才会修改元素
查找操作 O(n)
-
get(index)：O(n)- 会去遍历链表中每一个节点，
- 找到了合适位置的节点后，
- 返回这个元素。
-
contains(e)：O(n)- 会去遍历链表中每一个节点，
- 返回 是否有相同元素的 bool 值。
-
find(e)：O(n)- 这个方法对链表来说是没有用的，
- 就算你拿到了那个索引你也不能快速访问。
使用链表来实现栈
-
对链表进行添加操作时
O(n) O(1)
-
对链表进行删除操作时
O(n) O(1)
-
对链表进行查询操作时
O(n) O(1)
-
这些特性很符合栈的需求
- 栈是后进先出的，并且栈只查栈顶的元素，
- 所以可以使用链表来实现栈这样的数据结构。
链表实现的栈
-
首先定义接口
IMyLinkedListStack，- 然后让
MyLinkedListStack来实现这些接口。
- 然后让
-
IMyLinkedListStackvoid push(E e) E pop() E peek() int getSize() boolean isEmpty()
代码示例
-
(Interface: IMyLinkedListStack, class: MyLinkedList,-
class: MyLinkedListStack, class: Main)
-
-
IMyLinkedListStackpublic interface IMyLinkedListStack<E> { /** * @param e
*/
void push (E e);
/**
* @return e
* 出栈
*/
E pop ();
/**
* @return e
* 查看栈顶的一个元素
*/
E peek ();
/**
* @return size
* 查看栈中实际元素的个数
*/
int getSize ();
/**
* @return not empty
* 判断栈中是否为空
*/
boolean isEmpty ();
}
3. `MyLinkedList`
public class MyLinkedList<E> {
// 隐藏内部实现，不需要让用户知道
private class Node {
public E e;
public Node next;
public Node (E e, Node next) {
this.e = e;
this.next = next;
}
public Node (E e) {
this(e, null);
}
public Node () {
this(null, null);
}
@Override
public String toString () {
return e.toString();
}
}
private Node dummyHead;
private int size;
public MyLinkedList () {
dummyHead = new Node(null, null);
size = 0;
}
// ...
// 其它的构造函数，例如传进来一个数组，将数组转换为链表
// 获取链表中元素的个数
public int getSize () {
return size;
}
// 返回当前链表是否为空
public boolean isEmpty () {
return size == 0;
}
// 在链表头部添加一个元素 e
public void addFirst (E e) {
// 写法一
// Node node = new Node(e, head);
// head = node;
// 写法二
// Node node = new Node(e);
// node.next = dummyHead.next;
// dummyHead.next = node;
// 写法三
// dummyHead.next = new Node(e, dummyHead.next);
// size ++;
// 写法四
insert(0, e);
}
// 在链表指定索引出插入一个元素
public void insert (int index, E e) {
if (index < 0 || index > size) {
throw new IllegalArgumentException("add or insert error. index < 0 or index > size");
}
// 第一个prev就是dummyHead
Node prev = dummyHead;
// 不断的搜索 一直通过next来进行检索，找指定索引的节点的前一个元素
for (int i = 0; i < index ; i++) {
prev = prev.next;
}
// 第一种方式
// Node node = new Node(e);
// node.next = prev.next;
// prev.next = node;
// 第二种方式
prev.next = new Node(e, prev.next);
size ++;
}
// 在链表尾部添加一个元素
public void addLast (E e) {
insert(size, e);
}
// get
public E get (int index) {
if (index < 0 || index > size) {
throw new IllegalArgumentException("get error. index < 0 or index > size");
}
Node cur = dummyHead.next;
for (int i = 0; i < index ; i++) {
cur = cur.next;
}
return cur.e;
}
// getFirst
public E getFirst () {
return get(0);
}
// getLast
public E getLast () {
return get(size - 1);
}
// set
public void set (int index, E e) {
if (index < 0 || index > size) {
throw new IllegalArgumentException("set error. index < 0 or index > size");
}
Node node = dummyHead.next;
for (int i = 0; i < index; i++) {
node = node.next;
}
node.e = e;
}
// contains
public boolean contains (E e) {
// 第一种方式
// Node node = dummyHead;
// for (int i = 0; i < size - 1 ; i++) {
// node = node.next;
//
// if (node.e.equals(e)) {
// return true;
// }
// }
// 第二种方式
Node node = dummyHead.next;
while (node != null) {
if (node.e.equals(e)) {
return true;
} else {
node = node.next;
}
}
return false;
}
// remove
public E remove (int index) {
if (index < 0 || index > size) {
throw new IllegalArgumentException("remove error. index < 0 or index > size");
}
Node prev = dummyHead;
for (int i = 0; i < index ; i++) {
prev = prev.next;
}
Node delNode = prev.next;
prev.next = delNode.next;
size --;
E e = delNode.e;
delNode.next = null;
return e;
}
// removeFirst
public E removefirst () {
return remove(0);
}
// removeLast
public E removeLast () {
return remove(size - 1);
}
@Override
public String toString () {
StringBuilder sb = new StringBuilder();
sb.append("链表长度：" + size + "，链表信息：");
// // 写法一
// Node node = dummyHead.next;
// while (node != null) {
// sb.append(node + "->");
// node = node.next;
// }
// 写法二
for (Node node = dummyHead.next; node != null ; node = node.next) {
sb.append(node + "->");
}
sb.append("NULL");
return sb.toString();
}
}
4. `MyLinkedListStack`
public class MyLinkedListStack<E> implements IMyLinkedListStack<E> {
private MyLinkedList<E> mkl;
public MyLinkedListStack () {
mkl = new MyLinkedList<E>();
}
/**
* @param e 入栈
*/
@Override
public void push (E e) {
mkl.addFirst(e);
}
/**
* @return e
* 出栈
*/
@Override
public E pop () {
return mkl.removefirst();
}
/**
* @return e
* 查看栈顶的一个元素
*/
@Override
public E peek () {
return mkl.getFirst();
}
/**
* @return size
* 查看栈中实际元素的个数
*/
@Override
public int getSize () {
return mkl.getSize();
}
/**
* @return not empty
* 判断栈中是否为空
*/
@Override
public boolean isEmpty () {
return mkl.isEmpty();
}
@Override
public String toString () {
int size = getSize();
StringBuilder sb = new StringBuilder();
sb.append("MyLinkedlistStack: 元素个数=" + size);
sb.append(", stack top=[ ");
for (int i = 0; i < size ; i++) {
sb.append(mkl.get(i));
sb.append("->");
}
sb.append("NULL ]");
return sb.toString();
}
}
5. `Main`
public class Main {
public static void main(String[] args) {
MyLinkedListStack<Integer> mkls = new MyLinkedListStack<Integer>();
for (int i = 1; i <= 5 ; i++) {
mkls.push(i);
System.out.println(mkls);
}
System.out.println(mkls.peek());
for (int i = 0; i < 5 ; i++) {
System.out.println(mkls);
mkls.pop();
}
}
}
## 自定义数组栈对比自定义链表栈 1. 自定义数组栈与自定义链表栈的性能相差很少 1. 但是随着操作的次数增长，数组栈会慢慢强过链表栈， 2. 自定义链表栈中有太多的 new 操作， 3. new 操作在有一些系统上比较耗费性能的， 4. 因为它在不停的在内存中寻找可以开辟空间的地方来进行开辟空间， 5. 自定义数组栈中有比较多的扩容操作， 6. 所以这个比较是相对比较复杂的， 7. 和你的语法、操作系统、编译器、解释器都有关系， 8. 不过他们的时间复杂度都是`O(1)`级别的， 9. 所以他们之间的性能差异无非就 1-2 倍这样， 10. 在最极端的情况下 3-5 倍就已经很难了， 11. 不会有几百倍的巨大的差异，因为毕竟他们的时间复杂度一样。 ### 代码示例 1. `(Interface: IStack, class: MyLinkedList,` 1. `class: MyLinkedListStack, class: MyArray,` 2. `class: MyStack, class: Main)` 2. `IStack`
public interface IStack<E> {
/**
* @param e
* 入栈
*/
void push (E e);
/**
* @return e
* 出栈
*/
E pop ();
/**
* @return e
* 查看栈顶的一个元素
*/
E peek ();
/**
* @return size
* 查看栈中实际元素的个数
*/
int getSize ();
/**
* @return not empty
* 判断栈中是否为空
*/
boolean isEmpty ();
}
3. `MyLinkedList`
public class MyLinkedList<E> {
// 隐藏内部实现，不需要让用户知道
private class Node {
public E e;
public Node next;
public Node (E e, Node next) {
this.e = e;
this.next = next;
}
public Node (E e) {
this(e, null);
}
public Node () {
this(null, null);
}
@Override
public String toString () {
return e.toString();
}
}
private Node dummyHead;
private int size;
public MyLinkedList () {
dummyHead = new Node(null, null);
size = 0;
}
// ...
// 其它的构造函数，例如传进来一个数组，将数组转换为链表
// 获取链表中元素的个数
public int getSize () {
return size;
}
// 返回当前链表是否为空
public boolean isEmpty () {
return size == 0;
}
// 在链表头部添加一个元素 e
public void addFirst (E e) {
// 写法一
// Node node = new Node(e, head);
// head = node;
// 写法二
// Node node = new Node(e);
// node.next = dummyHead.next;
// dummyHead.next = node;
// 写法三
// dummyHead.next = new Node(e, dummyHead.next);
// size ++;
// 写法四
insert(0, e);
}
// 在链表指定索引出插入一个元素
public void insert (int index, E e) {
if (index < 0 || index > size) {
throw new IllegalArgumentException("add or insert error. index < 0 or index > size");
}
// 第一个prev就是dummyHead
Node prev = dummyHead;
// 不断的搜索 一直通过next来进行检索，找指定索引的节点的前一个元素
for (int i = 0; i < index ; i++) {
prev = prev.next;
}
// 第一种方式
// Node node = new Node(e);
// node.next = prev.next;
// prev.next = node;
// 第二种方式
prev.next = new Node(e, prev.next);
size ++;
}
// 在链表尾部添加一个元素
public void addLast (E e) {
insert(size, e);
}
// get
public E get (int index) {
if (index < 0 || index > size) {
throw new IllegalArgumentException("get error. index < 0 or index > size");
}
Node cur = dummyHead.next;
for (int i = 0; i < index ; i++) {
cur = cur.next;
}
return cur.e;
}
// getFirst
public E getFirst () {
return get(0);
}
// getLast
public E getLast () {
return get(size - 1);
}
// set
public void set (int index, E e) {
if (index < 0 || index > size) {
throw new IllegalArgumentException("set error. index < 0 or index > size");
}
Node node = dummyHead.next;
for (int i = 0; i < index; i++) {
node = node.next;
}
node.e = e;
}
// contains
public boolean contains (E e) {
// 第一种方式
// Node node = dummyHead;
// for (int i = 0; i < size - 1 ; i++) {
// node = node.next;
//
// if (node.e.equals(e)) {
// return true;
// }
// }
// 第二种方式
Node node = dummyHead.next;
while (node != null) {
if (node.e.equals(e)) {
return true;
} else {
node = node.next;
}
}
return false;
}
// remove
public E remove (int index) {
if (index < 0 || index > size) {
throw new IllegalArgumentException("remove error. index < 0 or index > size");
}
Node prev = dummyHead;
for (int i = 0; i < index ; i++) {
prev = prev.next;
}
Node delNode = prev.next;
prev.next = delNode.next;
size --;
E e = delNode.e;
delNode.next = null;
return e;
}
// removeFirst
public E removefirst () {
return remove(0);
}
// removeLast
public E removeLast () {
return remove(size - 1);
}
@Override
public String toString () {
StringBuilder sb = new StringBuilder();
sb.append("链表长度：" + size + "，链表信息：");
// // 写法一
// Node node = dummyHead.next;
// while (node != null) {
// sb.append(node + "->");
// node = node.next;
// }
// 写法二
for (Node node = dummyHead.next; node != null ; node = node.next) {
sb.append(node + "->");
}
sb.append("NULL");
return sb.toString();
}
}
4. `MyLinkedListStack`
public class MyLinkedListStack<E> implements IStack<E> {
private MyLinkedList<E> mkl;
public MyLinkedListStack () {
mkl = new MyLinkedList<E>();
}
/**
* @param e 入栈
*/
@Override
public void push (E e) {
mkl.addFirst(e);
}
/**
* @return e
* 出栈
*/
@Override
public E pop () {
return mkl.removefirst();
}
/**
* @return e
* 查看栈顶的一个元素
*/
@Override
public E peek () {
return mkl.getFirst();
}
/**
* @return size
* 查看栈中实际元素的个数
*/
@Override
public int getSize () {
return mkl.getSize();
}
/**
* @return not empty
* 判断栈中是否为空
*/
@Override
public boolean isEmpty () {
return mkl.isEmpty();
}
@Override
public String toString () {
int size = getSize();
StringBuilder sb = new StringBuilder();
sb.append("MyLinkedlistStack: 元素个数=" + size);
sb.append(", stack top=[ ");
for (int i = 0; i < size ; i++) {
sb.append(mkl.get(i));
sb.append("->");
}
sb.append("NULL ]");
return sb.toString();
}
}
5. `MyArray`
public class MyArray<E> {
private E [] data;
private int size;
// 构造函数，传入数组的容量capacity构造Array
public MyArray (int capacity) {
data = (E[])new Object[capacity];
size = 0;
}
// 无参数的构造函数，默认数组的容量capacity=10
public MyArray () {
// this( capacity: 10);
this(10);
}
// 获取数组中的元素实际个数
public int getSize () {
return size;
}
// 获取数组的总容量
public int getCapacity () {
return data.length;
}
// 返回数组是否为空
public boolean isEmpty () {
return size == 0;
}
// 重新给数组扩容
private void resize (int newCapacity) {
E[] newData = (E[])new Object[newCapacity];
int index = size - 1;
while (index > -1) {
newData[index] = get(index);
index --;
}
data = newData;
}
// 给数组添加一个新元素
public void add (E e) {
if (size == data.length) {
// throw new IllegalArgumentException("add error. Array is full.");
resize(2 * data.length);
}
data[size] = e;
size++;
}
// 向所有元素后添加一个新元素 （与 add方法功能一样） push
public void addLast (E e) {
// 复用插入元素的方法
insert(size, e);
}
// 在所有元素前添加一个新元素 unshift
public void addFirst (E e) {
insert(0, e);
}
// 在index索引的位置插入一个新元素e
public void insert (int index, E e) {
if (index < 0 || index > size) {
throw new IllegalArgumentException("insert error. require index < 0 or index > size");
}
if (size == data.length) {
// throw new IllegalArgumentException("add error. Array is full.");
resize(2 * data.length);
}
for (int i = size - 1; i >= index; i--) {
data[i + 1] = data[i];
}
data[index] = e;
size++;
}
// 获取index索引位置的元素
public E get (int index) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("get error. index < 0 or index >= size ");
}
return data[index];
}
// 获取数组中第一个元素（纯查看）
public E getFirst () {
return get(0);
}
// 获取数组中最后一个元素（纯查看）
public E getLast () {
return get(size - 1);
}
// 修改index索引位置的元素为e
public void set (int index, E e) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("get error. index < 0 or index >= size ");
}
data[index] = e;
}
// 查找数组中是否有元素e
public boolean contain (E e) {
for (int i = 0; i < size; i++) {
// if (data[i] == e) { // 值比较 用 ==
if (data[i].equals(e)) { // 引用比较 用 equals()
return true;
}
}
return false;
}
// 查找数组中元素e所在的索引，如果不存在元素e，则返回-1
public int find (E e) {
for (int i = 0; i < size; i++) {
if (data[i].equals(e)) {
return i;
}
}
return -1;
}
// 查找数组中所有元素e所在的索引，最后返回存放 所有索引值的 自定义数组
public MyArray findAll (E e) {
MyArray ma = new MyArray(20);
for (int i = 0; i < size; i++) {
if (data[i].equals(e)) {
ma.add(i);
}
}
return ma;
// int[] result = new int[ma.getSize()];
// for (int i = 0; i < ma.getSize(); i++) {
// result[i] = ma.get(i);
// }
//
// return result;
}
// 从数组中删除第一个元素, 返回删除的元素
public E removeFirst () {
return remove(0);
}
// 从数组中删除最后一个元素, 返回删除的元素
public E removeLast () {
return remove(size - 1);
}
// 从数组中删除第一个元素e
public void removeElement (E e) {
int index = find(e);
if (index != -1) {
remove(index);
}
// if (contain(e)) {
// int index = find(e);
// remove(index);
// }
}
// 从数组中删除所有元素e
public void removeAllElement (E e) {
int index = find(e);
while (index != -1) {
remove(index);
index = find(e);
}
// while (contain(e)) {
// removeElement(e);
// }
}
// 从数组中删除index位置的元素, 返回删除的元素
public E remove (int index) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("get error. index < 0 or index >= size ");
}
E temp = data[index];
for (int i = index; i < size - 1; i++) {
data[i] = data[i + 1];
}
// for (int i = index + 1; i < size; i++) {
// data[i - 1] = data[i];
// }
size --;
// data[size] = 0;
data[size] = null;
// 防止复杂度震荡 防止容量为4，size为1时，data.length / 2 为 0
if(size == data.length / 4 && data.length / 2 != 0) {
resize(data.length / 2);
}
return temp;
}
@Override
// @Override: 方法名 日期-开发人员
public String toString () {
StringBuilder sb = new StringBuilder();
String arrInfo = "Array: size = %d，capacity = %d/n";
sb.append(String.format(arrInfo, size, data.length));
sb.append('[');
for (int i = 0; i < size - 1; i ++) {
sb.append(data[i]);
sb.append(',');
}
sb.append(data[size - 1]);
sb.append(']');
return sb.toString();
}
}
6. `MyStack`
public class MyStack<E> implements IStack<E> {
// 借用自定义个动态数组
private MyArray<E> ma;
public MyStack () {
ma = new MyArray<E>();
}
public MyStack (int capacity) {
ma = new MyArray<E>(capacity);
}
/**
* @param e
* @return 入栈
*/
@Override
public void push(E e) {
ma.addLast(e);
}
/**
* @return 出栈
*/
@Override
public E pop() {
return ma.removeLast();
}
/**
* @return 查看栈顶的元素
*/
@Override
public E peek() {
return ma.getLast();
}
/**
* @return 获取栈中实际元素的个数
*/
@Override
public int getSize() {
return ma.getSize();
}
/**
* @return 判断栈是否为空
*/
@Override
public boolean isEmpty() {
return ma.isEmpty();
}
// 返回栈的容量
public int getCapacity () {
return ma.getCapacity();
}
@Override
// @Override: 方法名 日期-开发人员
public String toString () {
int size = ma.getSize();
// int capacity = ma.getCapacity();
StringBuilder sb = new StringBuilder();
// String arrInfo = "Stack: size = %d，capacity = %d/n";
// sb.append(String.format(arrInfo, size, capacity));
sb.append("Stack: [");
for (int i = 0; i < size - 1; i ++) {
sb.append(ma.get(i));
sb.append(',');
}
if (!ma.isEmpty()) {
sb.append(ma.getLast());
}
sb.append("] right is stack top !");
return sb.toString();
}
}
7. `Main`
import java.util.Random;
public class Main {
private static double testStack (IStack<Integer> s, int openCount) {
long startTime = System.nanoTime();
Random random = new Random();
for (int i = 1; i <= openCount ; i++) {
s.push(random.nextInt(Integer.MAX_VALUE));
}
//
while (!s.isEmpty()) {
s.pop();
}
// ..
long endTime = System.nanoTime();
return (endTime - startTime) / 1000_000_000.0;
}
public static void main(String[] args) {
MyLinkedListStack<Integer> mkls = new MyLinkedListStack<Integer>();
MyStack<Integer> ms = new MyStack<Integer>();
double msTime = testStack(ms, 100000);
double mklsTime = testStack(mkls, 100000);
System.out.println("MyStack，time：" + msTime + "s.");
System.out.println("MyLinkedListStack，time：" + mklsTime + "s.");
}
}
## 使用链表来实现队列 1. 对链表进行添加操作时 1. 时间复杂度为`O(n)`， 2. 只对链表头进行操作时为`O(1)`， 3. 对链表尾部进行操作时为`O(n)` 2. 对链表进行删除操作时 1. 时间复杂度为`O(n)`， 2. 只对链表头进行操作时为`O(1)`， 3. 对链表尾部进行操作时为`O(n)` 3. 对链表进行查询操作时 1. 时间复杂度为`O(n)`， 2. 只查链表头的元素时为`O(1)`， 3. 查链表尾部的元素时为`O(n)` 4. 队列中的操作 1. 在线性结构的一端插入元素， 2. 在另外一端删除元素， 3. 所以必然会在线性结构的两端同时操作， 4. 此时就会有一端的操作的复杂度是`O(n)`级别， 5. 这个问题在用自定义数组实现时也遇到了， 6. 也正因为如此产生了循环队列， 7. 通过改进使用数组来实现队列的方式， 8. 所以链表也可以进行改进。 5. 改进链表 1. 不能使用之前的链表来进行队列的实现， 2. 设置一个 head 变量指向链表的头部第一个节点， 3. 设置一个 tail 变量指向链表的尾部第一个节点， 4. 有了 tail 这个变量，那么在链表的尾部添加一个元素非常容易， 5. 有了 head 和 tail 之后在两端添加节点是非常容易的， 6. 但是无法使用`O(1)`去删除尾部的节点， 7. 从 tail 这一端删除元素并不容易， 8. 但是如果将 head 作为队首，将 tail 作为队尾， 9. 队列操作是从队尾进队首出的， 10. 只需要从队尾 tail 插入元素，从队首 head 删除元素， 11. 这样一来就可以实现队列的功能。 6. 链表中不再有插入的功能所以不需要 dummyHead 1. 但是由于没有 dummyHead，所以需要注意链表为空的情况。 7. 让自定义动态数组队列与自定义链表队列进行对比 1. 自定义动态数组队列的性能最差 2. 自定义动态数组循环队列与自定义链表队列的性能相近。 8. 与链表相关的有一个非常重要的内容 1. 就是递归，因为链表本身具有天然的递归性质， 2. 同时它又是一种非常简单的数据结构， 3. 所以链表是一种非常好的 4. 研究学习递归的逻辑机制的的数据结构。 ### 代码示例 1. `(Interface: IMyQueue, class: MyArray, class: MyQueue,` 1. `class: MyLoopQueue, class: MyLinkedListQueue, class: Main)` 2. `IMyQueue`
public interface IMyQueue<E> {
/**
- @param e
- 入队
*/
void enqueue (E e);
/**
- @return e
- 出队
*/
E dequeue ();
/**
- @return e
- 查看队首的元素
*/
E getFront ();
/**
- @return number
- 获取队列中的实际元素个数
*/
int getSize ();
/**
- @return bool
- 获取队列是否为空的bool值
*/
boolean isEmpty ();
}
3. `MyArray`
public class MyArray<E> {
private E [] data;
private int size;
// 构造函数，传入数组的容量capacity构造Array
public MyArray (int capacity) {
data = (E[])new Object[capacity];
size = 0;
}
// 无参数的构造函数，默认数组的容量capacity=10
public MyArray () {
// this( capacity: 10);
this(10);
}
// 获取数组中的元素实际个数
public int getSize () {
return size;
}
// 获取数组的总容量
public int getCapacity () {
return data.length;
}
// 返回数组是否为空
public boolean isEmpty () {
return size == 0;
}
// 重新给数组扩容
private void resize (int newCapacity) {
E[] newData = (E[])new Object[newCapacity];
int index = size - 1;
while (index > -1) {
newData[index] = get(index);
index --;
}
data = newData;
}
// 给数组添加一个新元素
public void add (E e) {
if (size == data.length) {
// throw new IllegalArgumentException("add error. Array is full.");
resize(2 * data.length);
}
data[size] = e;
size++;
}
// 向所有元素后添加一个新元素 （与 add方法功能一样） push
public void addLast (E e) {
// 复用插入元素的方法
insert(size, e);
}
// 在所有元素前添加一个新元素 unshift
public void addFirst (E e) {
insert(0, e);
}
// 在index索引的位置插入一个新元素e
public void insert (int index, E e) {
if (index < 0 || index > size) {
throw new IllegalArgumentException("insert error. require index < 0 or index > size");
}
if (size == data.length) {
// throw new IllegalArgumentException("add error. Array is full.");
resize(2 * data.length);
}
for (int i = size - 1; i >= index; i--) {
data[i + 1] = data[i];
}
data[index] = e;
size++;
}
// 获取index索引位置的元素
public E get (int index) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("get error. index < 0 or index >= size ");
}
return data[index];
}
// 获取数组中第一个元素（纯查看）
public E getFirst () {
return get(0);
}
// 获取数组中最后一个元素（纯查看）
public E getLast () {
return get(size - 1);
}
// 修改index索引位置的元素为e
public void set (int index, E e) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("get error. index < 0 or index >= size ");
}
data[index] = e;
}
// 查找数组中是否有元素e
public boolean contain (E e) {
for (int i = 0; i < size; i++) {
// if (data[i] == e) { // 值比较 用 ==
if (data[i].equals(e)) { // 引用比较 用 equals()
return true;
}
}
return false;
}
// 查找数组中元素e所在的索引，如果不存在元素e，则返回-1
public int find (E e) {
for (int i = 0; i < size; i++) {
if (data[i].equals(e)) {
return i;
}
}
return -1;
}
// 查找数组中所有元素e所在的索引，最后返回存放 所有索引值的 自定义数组
public MyArray findAll (E e) {
MyArray ma = new MyArray(20);
for (int i = 0; i < size; i++) {
if (data[i].equals(e)) {
ma.add(i);
}
}
return ma;
// int[] result = new int[ma.getSize()];
// for (int i = 0; i < ma.getSize(); i++) {
// result[i] = ma.get(i);
// }
//
// return result;
}
// 从数组中删除第一个元素, 返回删除的元素
public E removeFirst () {
return remove(0);
}
// 从数组中删除最后一个元素, 返回删除的元素
public E removeLast () {
return remove(size - 1);
}
// 从数组中删除第一个元素e
public void removeElement (E e) {
int index = find(e);
if (index != -1) {
remove(index);
}
// if (contain(e)) {
// int index = find(e);
// remove(index);
// }
}
// 从数组中删除所有元素e
public void removeAllElement (E e) {
int index = find(e);
while (index != -1) {
remove(index);
index = find(e);
}
// while (contain(e)) {
// removeElement(e);
// }
}
// 从数组中删除index位置的元素, 返回删除的元素
public E remove (int index) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("get error. index < 0 or index >= size ");
}
E temp = data[index];
for (int i = index; i < size - 1; i++) {
data[i] = data[i + 1];
}
// for (int i = index + 1; i < size; i++) {
// data[i - 1] = data[i];
// }
size --;
// data[size] = 0;
data[size] = null;
// 防止复杂度震荡 防止容量为4，size为1时，data.length / 2 为 0
if(size == data.length / 4 && data.length / 2 != 0) {
resize(data.length / 2);
}
return temp;
}
@Override
// @Override: 方法名 日期-开发人员
public String toString () {
StringBuilder sb = new StringBuilder();
String arrInfo = "Array: size = %d，capacity = %d/n";
sb.append(String.format(arrInfo, size, data.length));
sb.append('[');
for (int i = 0; i < size - 1; i ++) {
sb.append(data[i]);
sb.append(',');
}
sb.append(data[size - 1]);
sb.append(']');
return sb.toString();
}
}
4. `MyQueue`
public class MyQueue<E> implements IMyQueue<E> {
private MyArray<E> ma;
public MyQueue () {
ma = new MyArray<E>();
}
public MyQueue (int capacity) {
ma = new MyArray<E>(capacity);
}
/**
- @param e
- 入队
*/
@Override
public void enqueue (E e) {
ma.addLast(e);
}
/**
- @return e
- 出队
*/
@Override
public E dequeue () {
return ma.removeFirst();
}
/**
- @return e
- 查看队首的元素
*/
@Override
public E getFront () {
return ma.getFirst();
}
/**
- @return number
- 获取队列中的实际元素个数
*/
@Override
public int getSize () {
return ma.getSize();
}
/**
- @return bool
- 获取队列是否为空的bool值
*/
@Override
public boolean isEmpty () {
return ma.isEmpty();
}
// 获取队列容量
public int getCapacity () {
return ma.getCapacity();
}
@Override
public String toString () {
int size = ma.getSize ();
StringBuilder sb = new StringBuilder();
sb.append("Queue: head [");
for (int i = 0; i < size - 1; i ++) {
sb.append(ma.get(i));
sb.append(',');
}
if(!isEmpty()) {
sb.append(ma.getLast());
}
sb.append("] foot. left is queue top!");
return sb.toString();
}
}
5. `MyLoopQueue`
public class MyLoopQueue<E> implements IMyQueue<E> {
private E[] data;
private int front, tail;
private int size;
public MyLoopQueue (int capacity) {
// 这个数组的容量为 传进来的指定容量+1，
// 因为会有意识的浪费一个空间，只有+1后，
// 才能装下用户期望传进来的所有数据
data = (E[])new Object[capacity + 1];
front = tail = size = 0;
}
public MyLoopQueue () {
this(10);
}
public int getCapacity () {
return data.length - 1;
}
private void resize (int newCapacity) {
E[] newData = (E[]) new Object[newCapacity + 1];
for (int i = 0; i < size; i++) {
// 索引可能会越界，于是就要取余一下，
// 如果越界了，就从队首开始
newData[i] = data[(front + i) % data.length];
}
data = newData;
front = 0;
tail = size;
}
/**
* @param e 入队
*/
@Override
public void enqueue(E e) {
if ((tail + 1) % data.length == front) {
resize(getCapacity() * 2);
}
data[tail] = e;
// tail在队列中循环
tail = (tail + 1) % data.length;
size ++;
}
/**
* @return e
* 出队
*/
@Override
public E dequeue() {
if(isEmpty()) {
throw new IllegalArgumentException("can't dequeue from an empty queue.");
}
E e = data[front];
data[front] = null;
front = (front + 1) % data.length;
size -- ;
if (getCapacity() / 4 == size && getCapacity() / 2 != 0) {
resize(getCapacity() / 2);
}
return e;
}
/**
* @return e
* 查看队首的元素
*/
@Override
public E getFront() {
if (isEmpty()) {
throw new IllegalArgumentException("queue is empty.");
}
return data[front];
}
/**
* @return number
* 获取队列中的实际元素个数
*/
@Override
public int getSize() {
return size;
}
/**
* @return bool
* 获取队列是否为空的bool值
*/
@Override
public boolean isEmpty() {
return front == tail;
}
@Override
public String toString () {
StringBuilder sb = new StringBuilder();
sb.append(String.format("Queue: size = %d，capacity = %d /n", size, getCapacity()));
sb.append("Queue: head [");
// 第一种遍历方式
// for (int i = 0; i < size - 1; i ++) {
// sb.append(data[(front + i) % data.length]);
// sb.append(',');
// }
// if(!isEmpty()) {
// sb.append(data[(front + size - 1) % data.length]);
// }
// 第二种遍历方式
for (int i = front; i != tail ; i = (i + 1) % data.length) {
sb.append(data[i]);
if ((i + 1) % data.length != tail) {
sb.append(',');
}
}
sb.append("] foot. left is queue top!");
sb.append("/n");
return sb.toString();
}
}
6. `MyLinkedListQueue`
public class MyLinkedListQueue<E> implements IMyQueue<E> {
private class Node {
public E e;
public Node next;
public Node (E e, Node next) {
this.e = e;
this.next = next;
}
public Node (E e) {
this(e, null);
}
public Node () {
this(null, null);
}
@Override
public String toString () {
return e.toString();
}
}
private Node head, tail;
private int size;
public MyLinkedListQueue () {
head = tail = null;
size = 0;
}
/**
* @param e 入队
*/
@Override
public void enqueue(E e) {
// // 第一种方式
// Node node = new Node(e);
// node.next = tail;
// tail = node;
// 第二种方式
// head = new Node(e, head);
// 链表尾部为空
if (tail == null) {
tail = new Node(e);
head = tail;
} else {
tail.next = new Node(e);
tail = tail.next;
}
size ++;
// 不需要管头节点，因为头节点是不需要动的。
}
/**
* @return e
* 出队
*/
@Override
public E dequeue() {
if (isEmpty()) {
throw new IllegalArgumentException("can not dequeue from an empty queue.");
}
Node node = head;
head = head.next;
node.next = null;
if (head == null) {
tail = null;
}
size --;
return node.e;
}
/**
* @return e
* 查看队首的元素
*/
@Override
public E getFront() {
if (isEmpty()) {
throw new IllegalArgumentException("can not dequeue from an empty queue.");
}
return head.e;
}
/**
* @return number
* 获取队列中的实际元素个数
*/
@Override
public int getSize() {
return size;
}
/**
* @return bool
* 获取队列是否为空的bool值
*/
@Override
public boolean isEmpty() {
return size == 0;
}
@Override
public String toString () {
StringBuilder sb = new StringBuilder();
sb.append("MyLinkedListQueue: 元素个数=" + size);
sb.append(", queue front [ ");
for (Node node = head; node != null; node = node.next) {
sb.append(node);
sb.append("->");
}
sb.append("NULL ] tail");
return sb.toString();
}
public static void main(String[] args) {
MyLinkedListQueue<Integer> mkls = new MyLinkedListQueue<Integer>();
for (int i = 1; i <= 5 ; i++) {
mkls.enqueue(i);
System.out.println(mkls);
}
System.out.println(mkls.getFront());
for (int i = 0; i < 5 ; i++) {
System.out.println(mkls);
mkls.dequeue();
}
}
}
7. `Main`
import java.util.Random;
public class Main {
private static double testQueue (IMyQueue<Integer> q, int openCount) {
long startTime = System.nanoTime();
Random random = new Random();
for (int i = 1; i <= openCount ; i++) {
q.enqueue(random.nextInt(Integer.MAX_VALUE));
}
//
while (!q.isEmpty()) {
q.dequeue();
}
// ..
long endTime = System.nanoTime();
return (endTime - startTime) / 1000_000_000.0;
}
public static void main(String[] args) {
IMyQueue<Integer> mq = new MyQueue<Integer>();
IMyQueue<Integer> mlq = new MyLoopQueue<Integer>();
IMyQueue<Integer> mklq = new MyLinkedListQueue<Integer>();
double mqTime = testQueue(mq, 100000);
double mlqTime = testQueue(mlq, 100000);
double mklqTime = testQueue(mklq, 100000);
System.out.println("MyQueue，time：" + mqTime + "s.");
System.out.println("MyLoopQueue，time：" + mlqTime + "s.");
System.out.println("MyLinkedListQueue，time：" + mklqTime + "s.");
}
}
正文到此结束
- 本文标签： map 需求 value core NIO equals node find 代码 DOM src ORM LinkedList tab tar GitHub 遍历 build queue 索引 源码 管理 解析 开发 文章 HashTable 编译 js IDE HTML 操作系统 ACE id java https 数据 App 参数 删除 希望 git 调试 空间 快的 http MQ rand db UI 时间 list DDL IO 递归
- 版权声明： 本文为互联网转载文章，出处已在文章中说明(部分除外)。如果侵权，请联系本站长删除，谢谢。
- 本文海报： 生成海报一 生成海报二
热门推荐
相关文章
近期评论
-
文章和留言都翻到11页了 没有OOM
-
-
朋友，翻页到11页，及以后，会出现OOM，无法访问
-
-
搞个gitee的项目
-
-
版本号是多少，你可以下载哪个代码仓库，jdk选1.8 直接跑就行
-
-
-
Loading...
![[HBLOG]公众号](https://www.liuhaihua.cn/img/qrcode_gzh.jpg)
