线性表 及Java实现 顺序表、链表、栈、队列

时间:2024-01-02 21:31:08

数据结构与算法是程序设计的两大基础,大型的IT企业面试时也会出数据结构和算法的题目,

它可以说明你是否有良好的逻辑思维,如果你具备良好的逻辑思维,即使技术存在某些缺陷,面试公司也会认为你很有培养价值,至少在一段时间之后,技术可以很快得到提高。同时,它也是软考的重点,我们需要对这部分的内容进行一下总结。

我们先看一下数据结构和算法的整体内容。

线性表 及Java实现 顺序表、链表、栈、队列

1、线性表

概念:

数据元素的排列方式是线性的。

分类:

分类规则是根据上图中元素的存储结构来划分的。

线性表 及Java实现 顺序表、链表、栈、队列

(1)顺序表

基本思想:元素的存储空间是连续的。在内存中是以顺序存储,内存划分的区域是连续的。存储结构如下图:

线性表 及Java实现 顺序表、链表、栈、队列

(2)链表

基本思想:元素的存储空间是离散的,单独的(物理),它们可以通过在逻辑上指针的联系使得它成为了整体的链表。存储结构如下图:

线性表 及Java实现 顺序表、链表、栈、队列

1.单链表

线性表 及Java实现 顺序表、链表、栈、队列

线性表 及Java实现 顺序表、链表、栈、队列

            2.循环链表

线性表 及Java实现 顺序表、链表、栈、队列·

线性表 及Java实现 顺序表、链表、栈、队列

            3.双链表(双向循环表)

                   线性表 及Java实现 顺序表、链表、栈、队列

                 (图有点小问题 :最后一个节点的 指针域 也指向头结点)

线性表 及Java实现 顺序表、链表、栈、队列

 

三者的区别(从上面三个图我们可以总结出来):

1、它们都有数据域(data(p))和指针域(next(p)),但是从图中可以看出双链表有两个指针域,一个指向它的前节点,一个指向它的后节点。

2、单链表最后一个节点的指针域为空,没有后继节点;循环链表和双链表最后一个节点的指针域指向头节点,下一个结点为头节点,构成循环;

3、单链表和循环链表只可向一个方向遍历;双链表和循环链表,首节点和尾节点被连接在一起,可视为“无头无尾”;双链表可以向两个方向移动,灵活度更大。

线性表操作:

理解了顺序表和链表的基本思想之后,线性表的操作是简单,并且网上有很多讲解插入和删除结点的博客,在这里我就不过多的介绍了。

顺序表和链表的对比:

线性表 及Java实现 顺序表、链表、栈、队列

栈和队列是特殊的线性表,既然特殊就有不同点。

2、栈

基本思想:后进先出(先进后出)即栈中元素被处理时,按后进先出的顺序进行,栈又叫后进先出表(LIFO)。

举例:

日常生活中有很多栈的例子。例如,放在书桌上的一摞书,只能从书顶上拿走一本书,书也只能放在顶上。如下图所示:

线性表 及Java实现 顺序表、链表、栈、队列

3、队列

基本思想:先进先出即先被接收的元素将先被处理,又叫先进先出表(FIFO)。如下图所示:

举例:

队列的例子,生活中更多。比如:买车票排队,排头最先买到车票,新来的排的队尾;进车站时,安检行李,先进去的最先出来,后进去的后出来。

线性表 及Java实现 顺序表、链表、栈、队列

分类:

1.顺序队列

如下图所示:

线性表 及Java实现 顺序表、链表、栈、队列

顺序队列的操作,要判断队满和队空的标志,从图中我们可以总结得到:

1.队空:head = tail

2.队满:tail = m

2.循环队列

如下图所示:

线性表 及Java实现 顺序表、链表、栈、队列

循环队列的操作,要判断队空和队满的情况,从图中我们可以总结得到:

1.队空:head = tail

2.队满:tail + 1 = head(在队列中会留一个空着的空间,所以要加1)

总结

线性表真的很简单。

----------------------------------------------------------------------------------------------------

数据结构中的线性表,对应着Collection接口中的List接口。

在本节中,我们将做以下三件事

第一。我们先来看看线性表的特征

第二,自己用JAVA实现List

第三,对比的线性表、链式表性能,以及自己的List性能与JDKList性能对比

  线性表特征: 

第一,一个特定的线性表,应该是用来存放特定的某一个类型的元素的(元素的“同一性”)

第二, 除第一个元素外,其他每一个元素有且仅有一个直接前驱;除最后一个元素外,其他每一个元素有且仅有一个直接后继(元素的“序偶性”)

第三, 元素在线性表中的“下标”唯一地确定该元素在表中的相对位置(元素的“索引性”)

又,一.线性表只是数据的一种逻辑结构,其具体存储结构可以为顺序存储结构和链式储存结构来完成,对应可以得到顺序表和链表,

二.对线性表的入表和出表顺序做一定的限定,可以得到特殊的线性表,栈(FILO)和队列(FIFO)

    自己实现线性表之顺序表

思路:

1. 顺序表因为采用顺序存储形式,所以内部使用数组来存储数据

2.因为存储的具体对象类型不一定,所以采用泛型操作

3.数组操作优点:1.通过指针快速定位到下表,查询快速

缺点:1.数组声明时即需要确定数组大小。当操作中超过容量时,则需要重新声明数组,并且复制当前所有数据

2.当需要在中间进行插入或者删除时,则需要移动大量元素(size-index个)

具体实现代码如下

  1. /**
  2. * 自己用数组实现的线性表
  3. */
  4. public class ArrayList<E> {
  5. Object[] data = null;// 用来保存此队列中内容的数组
  6. int current;        // 保存当前为第几个元素的指标
  7. int capacity;        // 表示数组大小的指标
  8. /**
  9. * 如果初始化时,未声明大小,则默认为10
  10. */
  11. public ArrayList() {
  12. this(10);
  13. }
  14. /**
  15. * 初始化线性表,并且声明保存内容的数组大小
  16. * @param initalSize
  17. */
  18. public ArrayList(int initalSize) {
  19. if (initalSize < 0) {
  20. throw new RuntimeException("数组大小错误:" + initalSize);
  21. } else {
  22. this.data = new Object[initalSize];
  23. this.current = 0;
  24. capacity = initalSize;
  25. }
  26. }
  27. /**
  28. * 添加元素的方法 添加前,先确认是否已经满了
  29. * @param e
  30. * @return
  31. */
  32. public boolean add(E e) {
  33. ensureCapacity(current);// 确认容量
  34. this.data[current] = e;
  35. current++;
  36. return true;
  37. }
  38. /**
  39. * 确认系统当前容量是否满足需要,如果满足,则不执行操作 如果不满足,增加容量
  40. * @param cur 当前个数
  41. */
  42. private void ensureCapacity(int cur) {
  43. if (cur == capacity) {
  44. // 如果达到容量极限,增加10的容量,复制当前数组
  45. this.capacity = this.capacity + 10;
  46. Object[] newdata = new Object[capacity];
  47. for (int i = 0; i < cur; i++) {
  48. newdata[i] = this.data[i];
  49. }
  50. this.data = newdata;
  51. }
  52. }
  53. /**
  54. * 得到指定下标的数据
  55. * @param index
  56. * @return
  57. */
  58. public E get(int index) {
  59. validateIndex(index);
  60. return (E) this.data[index];
  61. }
  62. /**
  63. * 返回当前队列大小
  64. * @return
  65. */
  66. public int size() {
  67. return this.current;
  68. }
  69. /**
  70. * 更改指定下标元素的数据为e
  71. * @param index
  72. * @param e
  73. * @return
  74. */
  75. public boolean set(int index, E e) {
  76. validateIndex(index);
  77. this.data[index] = e;
  78. return true;
  79. }
  80. /**
  81. *  验证当前下标是否合法,如果不合法,抛出运行时异常
  82. * @param index 下标
  83. */
  84. private void validateIndex(int index) {
  85. if (index < 0 || index > current) {
  86. throw new RuntimeException("数组index错误:" + index);
  87. }
  88. }
  89. /**
  90. * 在指定下标位置处插入数据e
  91. * @param index 下标
  92. * @param e 需要插入的数据
  93. * @return
  94. */
  95. public boolean insert(int index, E e) {
  96. validateIndex(index);
  97. Object[] tem = new Object[capacity];// 用一个临时数组作为备份
  98. //开始备份数组
  99. for (int i = 0; i < current; i++) {
  100. if (i < index) {
  101. tem[i] = this.data[i];
  102. }else if(i==index){
  103. tem[i]=e;
  104. }else if(i>index){
  105. tem[i]=this.data[i-1];
  106. }
  107. }
  108. this.data=tem;
  109. return true;
  110. }
  111. /**  * 删除指定下标出的数据<br>
  112. * @param index<br>
  113. * @return<br>
  114. */
  115. public boolean delete(int index){
  116. validateIndex(index);
  117. Object[] tem = new Object[capacity];// 用一个临时数组作为备份
  118. //开始备份数组
  119. for (int i = 0; i < current; i++) {
  120. if (i < index) {
  121. tem[i] = this.data[i];
  122. }else if(i==index){
  123. tem[i]=this.data[i+1];
  124. }else if(i>index){
  125. tem[i]=this.data[i+1];
  126. }
  127. }
  128. this.data=tem;
  129. return true;
  130. }
  131. }

 自己实现线性表之链表

思路:1.链表采用链式存储结构,在内部只需要将一个一个结点链接起来。(每个结点中有关于此结点下一个结点的引用)

链表操作优点:1.因为每个结点记录下个结点的引用,则在进行插入和删除操作时,只需要改变对应下标下结点的引用即可

缺点:1.要得到某个下标的数据,不能通过下标直接得到,需要遍历整个链表。

实现代码如下

  1. /**
  2. * 自己用链式存储实现的线性表
  3. */
  4. public class LinkedList<E> {
  5. private Node<E> header = null;// 头结点
  6. int size = 0;// 表示数组大小的指标
  7. public LinkedList() {
  8. this.header = new Node<E>();
  9. }
  10. public boolean add(E e) {
  11. if (size == 0) {
  12. header.e = e;
  13. } else {
  14. // 根据需要添加的内容,封装为结点
  15. Node<E> newNode = new Node<E>(e);
  16. // 得到当前最后一个结点
  17. Node<E> last = getNode(size-1);
  18. // 在最后一个结点后加上新结点
  19. last.addNext(newNode);
  20. }
  21. size++;// 当前大小自增加1
  22. return true;
  23. }
  24. public boolean insert(int index, E e) {
  25. Node<E> newNode = new Node<E>(e);
  26. // 得到第N个结点
  27. Node<E> cNode = getNode(index);
  28. newNode.next = cNode.next;
  29. cNode.next = newNode;
  30. size++;
  31. return true;
  32. }
  33. /**
  34. * 遍历当前链表,取得当前索引对应的元素
  35. *
  36. * @return
  37. */
  38. private Node<E> getNode(int index) {
  39. // 先判断索引正确性
  40. if (index > size || index < 0) {
  41. throw new RuntimeException("索引值有错:" + index);
  42. }
  43. Node<E> tem = new Node<E>();
  44. tem = header;
  45. int count = 0;
  46. while (count != index) {
  47. tem = tem.next;
  48. count++;
  49. }
  50. return tem;
  51. }
  52. /**
  53. * 根据索引,取得该索引下的数据
  54. *
  55. * @param index
  56. * @return
  57. */
  58. public E get(int index) {
  59. // 先判断索引正确性
  60. if (index >= size || index < 0) {
  61. throw new RuntimeException("索引值有错:" + index);
  62. }
  63. Node<E> tem = new Node<E>();
  64. tem = header;
  65. int count = 0;
  66. while (count != index) {
  67. tem = tem.next;
  68. count++;
  69. }
  70. E e = tem.e;
  71. return e;
  72. }
  73. public int size() {
  74. return size;
  75. }
  76. /**
  77. * 设置第N个结点的值
  78. *
  79. * @param x
  80. * @param e
  81. * @return
  82. */
  83. public boolean set(int index, E e) {
  84. // 先判断索引正确性
  85. if (index > size || index < 0) {
  86. throw new RuntimeException("索引值有错:" + index);
  87. }
  88. Node<E> newNode = new Node<E>(e);
  89. // 得到第x个结点
  90. Node<E> cNode = getNode(index);
  91. cNode.e = e;
  92. return true;
  93. }
  94. /**
  95. * 用来存放数据的结点型内部类
  96. */
  97. class Node<e> {
  98. private E e;// 结点中存放的数据
  99. Node<E> next;// 用来指向该结点的下一个结点
  100. Node() { }
  101. Node(E e) {
  102. this.e = e;
  103. }
  104. // 在此结点后加一个结点
  105. void addNext(Node<E> node) {
  106. next = node;
  107. }
  108. }
  109. }

自己实现线性表之栈

栈是限定仅允许在表的同一端(通常为“表尾”)进行插入或删除操作的线性表。

允许插入和删除的一端称为栈顶(top),另一端称为栈底(base)
         特点:后进先出 (LIFO)或,先进后出(FILO)

因为栈是限定线的线性表,所以,我们可以调用前面两种线性表,只需要对出栈和入栈操作进行设定即可

具体实现代码

  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. * @return
  17. */
  18. public E pop(){
  19. E e= list.get(size-1);
  20. size--;
  21. return e;
  22. }
  23. }

至于用链表实现栈,则只需要把保存数据的顺序表改成链表即可,此处就不给出代码了

自己实现线性表之队列

与栈类似

队列是只允许在表的一端进行插入,而在另一端删除元素的线性表。

在队列中,允许插入的一端叫队尾(rear),允许删除的一端称为队头(front)。
        特点:先进先出 (FIFO)、后进后出 (LILO)

同理,我们也可以调用前面两种线性表,只需要对队列的入队和出队方式进行处理即可

  1. package cn.javamzd.collection.List;
  2. /**
  3. * 用数组实现的队列
  4. */
  5. public class ArrayQueue<E> {
  6. private ArrayList<E> list = new ArrayList<E>();// 用来保存数据的队列
  7. private int size;// 表示当前栈元素个数
  8. /**
  9. * 入队
  10. * @param e
  11. */
  12. public void EnQueue(E e) {
  13. list.add(e);
  14. size++;
  15. }
  16. /**
  17. * 出队
  18. * @return
  19. */
  20. public E DeQueue() {
  21. if (size > 0) {
  22. E e = list.get(0);
  23. list.delete(0);
  24. return e;
  25. }else{
  26. throw new RuntimeException("已经到达队列顶部");
  27. }
  28. }
  29. }

对比线性表和链式表
         前面已经说过顺序表和链式表各自的特点,这里在重申一遍

数组操作优点:1.通过指针快速定位到下标,查询快速

缺点:  1.数组声明时即需要确定数组大小。当操作中超过容量时,则需要重新声明数组,并且复制当前所有数据

2.当需要在中间进行插入或者删除时,则需要移动大量元素(size-index个)

链表操作优点:1.因为每个结点记录下个结点的引用,则在进行插入和删除操作时,只需要改变对应下标下结点的引用即可

缺点:1.要得到某个下标的数据,不能通过下标直接得到,需要遍历整个链表。

现在,我们通过进行增删改查操作来感受一次其效率的差异

思路:通过两个表,各进行大数据量操作(3W)条数据的操作,记录操作前系统时间,操作后系统时间,得出操作时间

实现代码如下

  1. package cn.javamzd.collection.List;
  2. public class Test {
  3. /**
  4. * @param args
  5. */
  6. public static void main(String[] args) {
  7. //测试自己实现的ArrayList类和Linkedlist类添加30000个数据所需要的时间
  8. ArrayList<String> al = new ArrayList<String>();
  9. LinkedList<String> ll = new LinkedList<String>();
  10. Long aBeginTime=System.currentTimeMillis();//记录BeginTime
  11. for(int i=0;i<30000;i++){
  12. al.add("now"+i);
  13. }
  14. Long aEndTime=System.currentTimeMillis();//记录EndTime
  15. System.out.println("arrylist  add time--->"+(aEndTime-aBeginTime));
  16. Long lBeginTime=System.currentTimeMillis();//记录BeginTime
  17. for(int i=0;i<30000;i++){
  18. ll.add("now"+i);
  19. }
  20. Long lEndTime=System.currentTimeMillis();//记录EndTime
  21. System.out.println("linkedList add time---->"+(lEndTime-lBeginTime));
  22. //测试JDK提供的ArrayList类和LinkedList类添加30000个数据所需要的世界
  23. java.util.ArrayList<String> sal=new java.util.ArrayList<String>();
  24. java.util.LinkedList<String> sll=new java.util.LinkedList<String>();
  25. Long saBeginTime=System.currentTimeMillis();//记录BeginTime
  26. for(int i=0;i<30000;i++){
  27. sal.add("now"+i);
  28. }
  29. Long saEndTime=System.currentTimeMillis();//记录EndTime
  30. System.out.println("JDK arrylist  add time--->"+(saEndTime-saBeginTime));
  31. Long slBeginTime=System.currentTimeMillis();//记录BeginTime
  32. for(int i=0;i<30000;i++){
  33. sll.add("now"+i);
  34. }
  35. Long slEndTime=System.currentTimeMillis();//记录EndTime
  36. System.out.println("JDK linkedList add time---->"+(slEndTime-slBeginTime));
  37. }
  38. }

得到测试结果如下:

arrylist add time--->446
linkedList add time---->9767
JDK arrylist add time--->13
JDK linkedList add time---->12

由以上数据,我们可知:

           1.JDK中的ArrayList何LinkedList在添加数据时的性能,其实几乎是没有差异的

2.我们自己写的List的性能和JDK提供的List的性能还是存在巨大差异的

3.我们使用链表添加操作,花费的时间是巨大的,比ArrayList都大几十倍

第三条显然是跟我们最初的设计不相符的,按照我们最初的设想,链表的添加应该比顺序表更省时

查看我们写的源码,可以发现:

我们每次添加一个数据时,都需要遍历整个表,得到表尾,再在表尾添加,这是很不科学的

 现改进如下:设立一个Node<E>类的成员变量end来指示表尾,这样每次添加时,就不需要再重新遍历得到表尾

改进后add()方法如下

  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()方法中的一行代码,此处就不列出了。

改进后,再次运行添加元素测试代码,结果如下:

arrylist add time--->16
linkedList add time---->8
JDK arrylist add time--->7
JDK linkedList add time---->7

虽然还有改进的空间,但是显然,我们的效果已经大幅度改进了,而且也比较接近JDK了

接下来测试插入操作的效率

我们只需要将测试代码中的添加方法(add())改成插入方法(insert(int index,E e)),为了使插入次数尽可能多,我们把index都设置为0

测试结果如下:

arrylist inset time--->17
linkedList inset time---->13
JDK arrylist inset time--->503
JDK linkedList inset time---->11

多次测试,发现我们写的ArrayList在插入方法的效率都已经超过JDK了,而且也接近LinkedLst了。撒花!!!