【从蛋壳到满天飞】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, 点击我吧 ,光看文章能够掌握两成,动手敲代码、动脑思考、画图才可以掌握八成。
本文章适合 对数据结构想了解并且感兴趣的人群,文章风格一如既往如此,就觉得手机上看起来比较方便,这样显得比较有条理,整理这些笔记加源码,时间跨度也算将近半年时间了,希望对想学习数据结构的人或者正在学习数据结构的人群有帮助。
链表是非常重要的线性数据结构
链表是真正的动态数据结构
对于链表来说它涉及到了计算机领域一个非常重要的概念
链表本身也是有它非常清晰的递归结构的,
链表这种数据结构本身就具有功能性
数据存储在“节点”(Node)中
class Node { E e; Node next; }
链表的优点
对于链表来说,你需要多少个数据。
链表的缺点
O(1)
数组
scores[2]
链表
对比
要清楚什么时候使用数组这样的静态数据结构,
简单的代码示例 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(); } } }
链表是通过节点来装载元素
MyLinkedList
给自定义数组添加元素是从数组尾部开始添加,
添加操作原理
node.next = head head = node
在链表头部添加元素非常简单,
在链表中间添加元素,
node.next = prev.next prev.next = node
在链表的操作中很多时候顺序非常重要,
node.next = prev.next
和 prev.next = node
prev.next = node
在前, node.next = prev.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); } }
在链表中进行指定索引处插入元素时
node.next = prev.next
和 prev.next = node
了, node.next = head
和 head = node
, 为什么对链表头插入元素那么特殊?
有了 dummyHead 之后就不需要处理头节点这个特殊的操作
node.next = dummyHead.next
、 dummyHead.next = node
, 链表操作的实际原理
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)
链表增删改查的时间复杂度
链表还有诸多的改进的方式
addLast(e)
: O(n)
addFirst(e)
: O(1)
insert(index, e)
: O(n/2) = O(n)
removeLast()
: O(n)
removeFirst()
: O(1)
remove(index)
: O(n/2) = O(n)
set(index, e)
: O(n)
get(index)
: O(n)
contains(e)
: O(n)
find(e)
: O(n)
对链表进行添加操作时
O(n) O(1)
对链表进行删除操作时
O(n) O(1)
对链表进行查询操作时
O(n) O(1)
这些特性很符合栈的需求
首先定义接口 IMyLinkedListStack
,
MyLinkedListStack
来实现这些接口。 IMyLinkedListStack
void push(E e) E pop() E peek() int getSize() boolean isEmpty()
(Interface: IMyLinkedListStack, class: MyLinkedList,
class: MyLinkedListStack, class: Main)
IMyLinkedListStack
public 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."); } }