Java实现之顺序表、链表、栈、队列 蔚落 2022-05-28 08:20 154阅读 0赞 数据结构与算法是程序设计的两大基础,大型的IT企业面试时也会出数据结构和算法的题目, 它可以说明你是否有良好的逻辑思维,如果你具备良好的逻辑思维,即使技术存在某些缺陷,面试公司也会认为你很有培养价值,至少在一段时间之后,技术可以很快得到提高。同时,它也是软考的重点,我们需要对这部分的内容进行一下总结。 我们先看一下数据结构和算法的整体内容。 ![20140417143957015][] ## 1、线性表 ## ### 概念: ### 数据元素的排列方式是线性的。 ### 分类: ### 分类规则是根据上图中元素的存储结构来划分的。 ![20140417152023312][] #### (1)顺序表 #### 基本思想:元素的存储空间是连续的。在内存中是以顺序存储,内存划分的区域是连续的。存储结构如下图: ![20140417152510500][] #### (2)链表 #### 基本思想:元素的存储空间是离散的,单独的(物理),它们可以通过在逻辑上指针的联系使得它成为了整体的链表。存储结构如下图: ![20140417154704718][] 1.单链表 ![20140417160422750][] ![0_1305618800y6GC.gif][] 2.循环链表 ![20140417160438046][]· ![0_1305618815gCFS.gif][] 3.双链表(双向循环表) ![20140417160445843][] (图有点小问题 :最后一个节点的 指针域 也指向头结点) ![Center][] 三者的区别(从上面三个图我们可以总结出来): 1、它们都有数据域(data(p))和指针域(next(p)),但是从图中可以看出双链表有两个指针域,一个指向它的前节点,一个指向它的后节点。 2、单链表最后一个节点的指针域为空,没有后继节点;循环链表和双链表最后一个节点的指针域指向头节点,下一个结点为头节点,构成循环; 3、单链表和循环链表只可向一个方向遍历;双链表和循环链表,首节点和尾节点被连接在一起,可视为“无头无尾”;双链表可以向两个方向移动,灵活度更大。 ### 线性表操作: ### 理解了顺序表和链表的基本思想之后,线性表的操作是简单,并且网上有很多讲解插入和删除结点的博客,在这里我就不过多的介绍了。 ### 顺序表和链表的对比: ### ![Center 1][] 栈和队列是特殊的线性表,既然特殊就有不同点。 ## 2、栈 ## 基本思想:后进先出(先进后出)即栈中元素被处理时,按后进先出的顺序进行,栈又叫后进先出表(LIFO)。 举例: 日常生活中有很多栈的例子。例如,放在书桌上的一摞书,只能从书顶上拿走一本书,书也只能放在顶上。如下图所示: ![Center 2][] ## 3、队列 ## 基本思想:先进先出即先被接收的元素将先被处理,又叫先进先出表(FIFO)。如下图所示: 举例: 队列的例子,生活中更多。比如:买车票排队,排头最先买到车票,新来的排的队尾;进车站时,安检行李,先进去的最先出来,后进去的后出来。 ![Center 3][] ### 分类: ### #### 1.顺序队列 #### 如下图所示: ![SouthEast][] 顺序队列的操作,要判断队满和队空的标志,从图中我们可以总结得到: 1.队空:head = tail 2.队满:tail = m #### 2.循环队列 #### 如下图所示: ![SouthEast 1][] 循环队列的操作,要判断队空和队满的情况,从图中我们可以总结得到: 1.队空:head = tail 2.队满:tail + 1 = head(在队列中会留一个空着的空间,所以要加1) ## 总结 ## 线性表真的很简单。 \---------------------------------------------------------------------------------------------------- 数据结构中的线性表,对应着Collection接口中的List接口。 在本节中,我们将做以下三件事 第一。我们先来看看线性表的特征 第二,自己用JAVA实现List 第三,对比的线性表、链式表性能,以及自己的List性能与JDKList性能对比 线性表特征: 第一,一个特定的线性表,应该是用来存放特定的某一个类型的元素的(元素的“同一性”) 第二, 除第一个元素外,其他每一个元素有且仅有一个直接前驱;除最后一个元素外,其他每一个元素有且仅有一个直接后继(元素的“序偶性”) 第三, 元素在线性表中的“下标”唯一地确定该元素在表中的相对位置(元素的“索引性”) 又,一.线性表只是数据的一种逻辑结构,其具体存储结构可以为顺序存储结构和链式储存结构来完成,对应可以得到顺序表和链表, 二.对线性表的入表和出表顺序做一定的限定,可以得到特殊的线性表,栈(FILO)和队列(FIFO) 自己实现线性表之顺序表 思路: 1. 顺序表因为采用顺序存储形式,所以内部使用数组来存储数据 2.因为存储的具体对象类型不一定,所以采用泛型操作 3.数组操作优点:1.通过指针快速定位到下表,查询快速 缺点:1.数组声明时即需要确定数组大小。当操作中超过容量时,则需要重新声明数组,并且复制当前所有数据 2.当需要在中间进行插入或者删除时,则需要移动大量元素(size-index个) 具体实现代码如下 Java代码 1. /\*\* 2. \* 自己用数组实现的线性表 3. \*/ 4. **public** **class** ArrayList<E> \{ 5. Object\[\] data = **null**;// 用来保存此队列中内容的数组 6. **int** current; // 保存当前为第几个元素的指标 7. **int** capacity; // 表示数组大小的指标 8. 9. /\*\* 10. \* 如果初始化时,未声明大小,则默认为10 11. \*/ 12. **public** ArrayList() \{ 13. **this**(10); 14. \} 15. 16. /\*\* 17. \* 初始化线性表,并且声明保存内容的数组大小 18. \* @param initalSize 19. \*/ 20. **public** ArrayList(**int** initalSize) \{ 21. **if** (initalSize < 0) \{ 22. **throw** **new** RuntimeException("数组大小错误:" \+ initalSize); 23. \} **else** \{ 24. **this**.data = **new** Object\[initalSize\]; 25. **this**.current = 0; 26. capacity = initalSize; 27. \} 28. \} 29. 30. /\*\* 31. \* 添加元素的方法 添加前,先确认是否已经满了 32. \* @param e 33. \* @return 34. \*/ 35. **public** **boolean** add(E e) \{ 36. ensureCapacity(current);// 确认容量 37. **this**.data\[current\] = e; 38. current++; 39. **return** **true**; 40. \} 41. 42. /\*\* 43. \* 确认系统当前容量是否满足需要,如果满足,则不执行操作 如果不满足,增加容量 44. \* @param cur 当前个数 45. \*/ 46. **private** **void** ensureCapacity(**int** cur) \{ 47. **if** (cur == capacity) \{ 48. // 如果达到容量极限,增加10的容量,复制当前数组 49. **this**.capacity = **this**.capacity + 10; 50. Object\[\] newdata = **new** Object\[capacity\]; 51. **for** (**int** i = 0; i < cur; i++) \{ 52. newdata\[i\] = **this**.data\[i\]; 53. \} 54. **this**.data = newdata; 55. \} 56. \} 57. 58. /\*\* 59. \* 得到指定下标的数据 60. \* @param index 61. \* @return 62. \*/ 63. **public** E get(**int** index) \{ 64. validateIndex(index); 65. **return** (E) **this**.data\[index\]; 66. \} 67. 68. /\*\* 69. \* 返回当前队列大小 70. \* @return 71. \*/ 72. **public** **int** size() \{ 73. **return** **this**.current; 74. \} 75. 76. /\*\* 77. \* 更改指定下标元素的数据为e 78. \* @param index 79. \* @param e 80. \* @return 81. \*/ 82. **public** **boolean** set(**int** index, E e) \{ 83. validateIndex(index); 84. **this**.data\[index\] = e; 85. **return** **true**; 86. \} 87. 88. /\*\* 89. \* 验证当前下标是否合法,如果不合法,抛出运行时异常 90. \* @param index 下标 91. \*/ 92. **private** **void** validateIndex(**int** index) \{ 93. **if** (index < 0 || index > current) \{ 94. **throw** **new** RuntimeException("数组index错误:" \+ index); 95. \} 96. \} 97. 98. /\*\* 99. \* 在指定下标位置处插入数据e 100. \* @param index 下标 101. \* @param e 需要插入的数据 102. \* @return 103. \*/ 104. **public** **boolean** insert(**int** index, E e) \{ 105. validateIndex(index); 106. Object\[\] tem = **new** Object\[capacity\];// 用一个临时数组作为备份 107. //开始备份数组 108. **for** (**int** i = 0; i < current; i++) \{ 109. **if** (i < index) \{ 110. tem\[i\] = **this**.data\[i\]; 111. \}**else** **if**(i==index)\{ 112. tem\[i\]=e; 113. \}**else** **if**(i>index)\{ 114. tem\[i\]=**this**.data\[i-1\]; 115. \} 116. \} 117. **this**.data=tem; 118. **return** **true**; 119. \} 120. /\*\* \* 删除指定下标出的数据<br> 121. \* @param index<br> 122. \* @return<br> 123. \*/ 124. **public** **boolean** delete(**int** index)\{ 125. validateIndex(index); 126. Object\[\] tem = **new** Object\[capacity\];// 用一个临时数组作为备份 127. //开始备份数组 128. for (int i = 0; i < current; i++) \{ 129. if (i < index) \{ 130. tem\[i\] = this.data\[i\]; 131. \}else if(i==index)\{ 132. tem\[i\]=this.data\[i+1\]; 133. \}else if(i>index)\{ 134. tem\[i\]=this.data\[i+1\]; 135. \} 136. \} 137. this.data=tem; 138. return true; 139. \} 140. \} 自己实现线性表之链表 思路:1.链表采用链式存储结构,在内部只需要将一个一个结点链接起来。(每个结点中有关于此结点下一个结点的引用) 链表操作优点:1.因为每个结点记录下个结点的引用,则在进行插入和删除操作时,只需要改变对应下标下结点的引用即可 缺点:1.要得到某个下标的数据,不能通过下标直接得到,需要遍历整个链表。 实现代码如下 Java代码 ![收藏代码][icon_star.png] 1. /\*\* 2. \* 自己用链式存储实现的线性表 3. \*/ 4. **public** **class** LinkedList<E> \{ 5. 6. **private** Node<E> header = **null**;// 头结点 7. **int** size = 0;// 表示数组大小的指标 8. 9. **public** LinkedList() \{ 10. **this**.header = **new** Node<E>(); 11. \} 12. 13. **public** **boolean** add(E e) \{ 14. **if** (size == 0) \{ 15. header.e = e; 16. \} **else** \{ 17. // 根据需要添加的内容,封装为结点 18. Node<E> newNode = **new** Node<E>(e); 19. // 得到当前最后一个结点 20. Node<E> last = getNode(size-1); 21. // 在最后一个结点后加上新结点 22. last.addNext(newNode); 23. \} 24. size++;// 当前大小自增加1 25. **return** **true**; 26. \} 27. 28. **public** **boolean** insert(**int** index, E e) \{ 29. Node<E> newNode = **new** Node<E>(e); 30. // 得到第N个结点 31. Node<E> cNode = getNode(index); 32. newNode.next = cNode.next; 33. cNode.next = newNode; 34. size++; 35. **return** **true**; 36. \} 37. 38. /\*\* 39. \* 遍历当前链表,取得当前索引对应的元素 40. \* 41. \* @return 42. \*/ 43. **private** Node<E> getNode(**int** index) \{ 44. // 先判断索引正确性 45. **if** (index > size || index < 0) \{ 46. **throw** **new** RuntimeException("索引值有错:" \+ index); 47. \} 48. Node<E> tem = **new** Node<E>(); 49. tem = header; 50. **int** count = 0; 51. **while** (count != index) \{ 52. tem = tem.next; 53. count++; 54. \} 55. **return** tem; 56. \} 57. 58. /\*\* 59. \* 根据索引,取得该索引下的数据 60. \* 61. \* @param index 62. \* @return 63. \*/ 64. **public** E get(**int** index) \{ 65. // 先判断索引正确性 66. **if** (index >= size || index < 0) \{ 67. **throw** **new** RuntimeException("索引值有错:" \+ index); 68. \} 69. Node<E> tem = **new** Node<E>(); 70. tem = header; 71. **int** count = 0; 72. **while** (count != index) \{ 73. tem = tem.next; 74. count++; 75. \} 76. E e = tem.e; 77. **return** e; 78. \} 79. 80. **public** **int** size() \{ 81. **return** size; 82. \} 83. 84. /\*\* 85. \* 设置第N个结点的值 86. \* 87. \* @param x 88. \* @param e 89. \* @return 90. \*/ 91. **public** **boolean** set(**int** index, E e) \{ 92. // 先判断索引正确性 93. **if** (index > size || index < 0) \{ 94. **throw** **new** RuntimeException("索引值有错:" \+ index); 95. \} 96. Node<E> newNode = **new** Node<E>(e); 97. // 得到第x个结点 98. Node<E> cNode = getNode(index); 99. cNode.e = e; 100. **return** **true**; 101. \} 102. 103. /\*\* 104. \* 用来存放数据的结点型内部类 105. \*/ 106. **class** Node<e> \{ 107. **private** E e;// 结点中存放的数据 108. Node<E> next;// 用来指向该结点的下一个结点 109. 110. Node() \{ \} 111. Node(E e) \{ 112. **this**.e = e; 113. \} 114. // 在此结点后加一个结点 115. **void** addNext(Node<E> node) \{ 116. next = node; 117. \} 118. \} 119. \} 自己实现线性表之栈 栈是限定仅允许在表的同一端(通常为“表尾”)进行插入或删除操作的线性表。 允许插入和删除的一端称为栈顶(top),另一端称为栈底(base) 特点:后进先出 (LIFO)或,先进后出(FILO) 因为栈是限定线的线性表,所以,我们可以调用前面两种线性表,只需要对出栈和入栈操作进行设定即可 具体实现代码 Java代码 ![收藏代码][icon_star.png] 1. /\*\* 2. \* 自己用数组实现的栈 3. \*/ 4. **public** **class** ArrayStack<E> \{ 5. **private** ArrayList<E> list=**new** ArrayList<E>();//用来保存数据线性表<br> private int size;//表示当前栈元素个数 6. /\*\* 7. \* 入栈操作 8. \* @param e 9. \*/ 10. **public** **void** push(E e)\{ 11. list.add(e); 12. size++; 13. \} 14. 15. /\*\* 16. \* 出栈操作 17. \* @return 18. \*/ 19. **public** E pop()\{ 20. E e= list.get(size-1); 21. size--; 22. **return** e; 23. \} 24. 25. \} 至于用链表实现栈,则只需要把保存数据的顺序表改成链表即可,此处就不给出代码了 自己实现线性表之队列 与栈类似 队列是只允许在表的一端进行插入,而在另一端删除元素的线性表。 在队列中,允许插入的一端叫队尾(rear),允许删除的一端称为队头(front)。 特点:先进先出 (FIFO)、后进后出 (LILO) 同理,我们也可以调用前面两种线性表,只需要对队列的入队和出队方式进行处理即可 Java代码 ![收藏代码][icon_star.png] 1. **package** cn.javamzd.collection.List; 2. 3. /\*\* 4. \* 用数组实现的队列 5. \*/ 6. **public** **class** ArrayQueue<E> \{ 7. **private** ArrayList<E> list = **new** ArrayList<E>();// 用来保存数据的队列 8. **private** **int** size;// 表示当前栈元素个数 9. 10. /\*\* 11. \* 入队 12. \* @param e 13. \*/ 14. **public** **void** EnQueue(E e) \{ 15. list.add(e); 16. size++; 17. \} 18. 19. /\*\* 20. \* 出队 21. \* @return 22. \*/ 23. **public** E DeQueue() \{ 24. **if** (size > 0) \{ 25. E e = list.get(0); 26. list.delete(0); 27. **return** e; 28. \}**else**\{ 29. **throw** **new** RuntimeException("已经到达队列顶部"); 30. \} 31. \} 32. \} 对比线性表和链式表 前面已经说过顺序表和链式表各自的特点,这里在重申一遍 数组操作优点:1.通过指针快速定位到下标,查询快速 缺点: 1.数组声明时即需要确定数组大小。当操作中超过容量时,则需要重新声明数组,并且复制当前所有数据 2.当需要在中间进行插入或者删除时,则需要移动大量元素(size-index个) 链表操作优点:1.因为每个结点记录下个结点的引用,则在进行插入和删除操作时,只需要改变对应下标下结点的引用即可 缺点:1.要得到某个下标的数据,不能通过下标直接得到,需要遍历整个链表。 现在,我们通过进行增删改查操作来感受一次其效率的差异 思路:通过两个表,各进行大数据量操作(3W)条数据的操作,记录操作前系统时间,操作后系统时间,得出操作时间 实现代码如下 Java代码 ![收藏代码][icon_star.png] 1. **package** cn.javamzd.collection.List; 2. 3. **public** **class** Test \{ 4. 5. /\*\* 6. \* @param args 7. \*/ 8. **public** **static** **void** main(String\[\] args) \{ 9. //测试自己实现的ArrayList类和Linkedlist类添加30000个数据所需要的时间 10. ArrayList<String> al = **new** ArrayList<String>(); 11. LinkedList<String> ll = **new** LinkedList<String>(); 12. Long aBeginTime=System.currentTimeMillis();//记录BeginTime 13. **for**(**int** i=0;i<30000;i++)\{ 14. al.add("now"\+i); 15. \} 16. Long aEndTime=System.currentTimeMillis();//记录EndTime 17. System.out.println("arrylist add time--->"\+(aEndTime-aBeginTime)); 18. Long lBeginTime=System.currentTimeMillis();//记录BeginTime 19. **for**(**int** i=0;i<30000;i++)\{ 20. ll.add("now"\+i); 21. \} 22. Long lEndTime=System.currentTimeMillis();//记录EndTime 23. System.out.println("linkedList add time---->"\+(lEndTime-lBeginTime)); 24. 25. //测试JDK提供的ArrayList类和LinkedList类添加30000个数据所需要的世界 26. java.util.ArrayList<String> sal=**new** java.util.ArrayList<String>(); 27. java.util.LinkedList<String> sll=**new** java.util.LinkedList<String>(); 28. Long saBeginTime=System.currentTimeMillis();//记录BeginTime 29. **for**(**int** i=0;i<30000;i++)\{ 30. sal.add("now"\+i); 31. \} 32. Long saEndTime=System.currentTimeMillis();//记录EndTime 33. System.out.println("JDK arrylist add time--->"\+(saEndTime-saBeginTime)); 34. Long slBeginTime=System.currentTimeMillis();//记录BeginTime 35. **for**(**int** i=0;i<30000;i++)\{ 36. sll.add("now"\+i); 37. \} 38. Long slEndTime=System.currentTimeMillis();//记录EndTime 39. System.out.println("JDK linkedList add time---->"\+(slEndTime-slBeginTime)); 40. \} 41. 42. \} 得到测试结果如下: <table style="width:780px;background-color:rgb(255,255,255);color:rgb(0,0,0);line-height:25.2px;font-family:Helvetica, Tahoma, Arial, sans-serif;font-size:14px;"> <tbody> <tr> <td style="font-size:1em;">arrylist add time--->446<br>linkedList add time---->9767<br>JDK arrylist add time--->13<br>JDK linkedList add time---->12</td> </tr> </tbody> </table> 由以上数据,我们可知: 1.JDK中的ArrayList何LinkedList在添加数据时的性能,其实几乎是没有差异的 2.我们自己写的List的性能和JDK提供的List的性能还是存在巨大差异的 3.我们使用链表添加操作,花费的时间是巨大的,比ArrayList都大几十倍 第三条显然是跟我们最初的设计不相符的,按照我们最初的设想,链表的添加应该比顺序表更省时 查看我们写的源码,可以发现: 我们每次添加一个数据时,都需要遍历整个表,得到表尾,再在表尾添加,这是很不科学的 现改进如下:设立一个Node<E>类的成员变量end来指示表尾,这样每次添加时,就不需要再重新遍历得到表尾 改进后add()方法如下 Java代码 1. **public** **boolean** add(E e) \{ 2. **if** (size == 0) \{ 3. header.e = e; 4. \} **else** \{ 5. // 根据需要添加的内容,封装为结点 6. Node<E> newNode = **new** Node<E>(e); 7. //在表尾添加元素 8. last.addNext(newNode); 9. //将表尾指向当前最后一个元素 10. last = newNode; 11. \} 12. size++;// 当前大小自增加1 13. **return** **true**; 14. \} ArrayList添加的效率和JDK中对比起来也太低 分析原因为: 每次扩大容量时,扩大量太小,需要进行的复制操作太多 现在改进如下: 每次扩大,则扩大容量为当前的三倍,此改进仅需要更改ensureCapacity()方法中的一行代码,此处就不列出了。 改进后,再次运行添加元素测试代码,结果如下: <table style="width:780px;background-color:rgb(255,255,255);color:rgb(0,0,0);line-height:25.2px;font-family:Helvetica, Tahoma, Arial, sans-serif;font-size:14px;"> <tbody> <tr> <td style="font-size:1em;">arrylist add time--->16<br>linkedList add time---->8<br>JDK arrylist add time--->7<br>JDK linkedList add time---->7</td> </tr> </tbody> </table> 虽然还有改进的空间,但是显然,我们的效果已经大幅度改进了,而且也比较接近JDK了 接下来测试插入操作的效率 我们只需要将测试代码中的添加方法(add())改成插入方法(insert(int index,E e)),为了使插入次数尽可能多,我们把index都设置为0 测试结果如下: <table style="width:780px;background-color:rgb(255,255,255);color:rgb(0,0,0);line-height:25.2px;font-family:Helvetica, Tahoma, Arial, sans-serif;font-size:14px;"> <tbody> <tr> <td style="font-size:1em;">arrylist inset time--->17<br>linkedList inset time---->13<br>JDK arrylist inset time--->503<br>JDK linkedList inset time---->11</td> </tr> </tbody> </table> 多次测试,发现我们写的ArrayList在插入方法的效率都已经超过JDK了,而且也接近LinkedLst了。撒花!!! [20140417143957015]: /images/20220528/01cdb16a2dfc44f0aa64987ef0311432.png [20140417152023312]: /images/20220528/53d6e1d88a5d4c228fff5ea7234604fe.png [20140417152510500]: /images/20220528/a78074420fab4ebeb2556586c7b2da5f.png [20140417154704718]: /images/20220528/fbcbc83f419f4c0d8967ee8b05c92afb.png [20140417160422750]: /images/20220528/4f35940aa55d45e38eb6e11451126875.png [0_1305618800y6GC.gif]: /images/20220528/bc34ecb1154d43ff927da5697503981e.png [20140417160438046]: /images/20220528/488f130922bd4db3a9e0765361d59710.png [0_1305618815gCFS.gif]: /images/20220528/b5c7de75609847698c20940e8c4ef4df.png [20140417160445843]: /images/20220528/e00349b469ad45d99ec618a0f777b130.png [Center]: /images/20220528/e10c7b38baf54008a13366d2a122c638.png [Center 1]: /images/20220528/7b251c6e2f3a49fa89daa3cbffeb3a4e.png [Center 2]: /images/20220528/bb033f6ee8f64dbb9bd9cfbbb9b8bc71.png [Center 3]: /images/20220528/2efe6a1ff49040e58428a3e787da54ab.png [SouthEast]: /images/20220528/c8941ef1bbc8441d8bbdf014b8297964.png [SouthEast 1]: /images/20220528/732576234e714a469c89cbeb1fdc6b40.png [icon_star.png]: /images/20220528/1cac157bdcc948fb82d26fa6da83c653.png
还没有评论,来说两句吧...