《数据结构基础：数组、栈、队列与单链表详解》

<｜begin▁of▁sentence｜># 一、什么是数据结构 ## 1. 数据结构的定义 数据结构是计算机中存储、组织数据的方式。通常情况下，精心选择的数据结构可以带来最优效率的算法。 ## 2. 数据结构和算法的关系 - 程序 = 数据结构 + 算法 - 数据结构是算法的基础 # 二、线性结构 ## 1. 数组 ### 1.1 数组介绍 - 数组（Array）是有序的元素序列。 - 数组的每个元素都有自己的下标，下标从0开始。 - 创建数组时，需要指定数组的容量大小，大小一旦确定就不可以修改。 ### 1.2 自定义数组 ```java public class Array { private E[] data; private int size; // 构造函数，传入数组的容量capacity构造Array public Array(int capacity){ data = (E[])new Object[capacity]; size = 0; } // 无参数的构造函数，默认数组的容量capacity=10 public Array(){ this(10); } // 获取数组的容量 public int getCapacity(){ return data.length; } // 获取数组中的元素个数 public int getSize(){ return size; } // 返回数组是否为空 public boolean isEmpty(){ return size == 0; } // 在index索引的位置插入一个新元素e public void add(int index, E e){ if(index < 0 || index > size) throw new IllegalArgumentException("Add failed. Require index >= 0 and index <= size."); if(size == data.length) resize(2 * data.length); for(int i = size - 1; i >= index ; i --) data[i + 1] = data[i]; data[index] = e; size ++; } // 向所有元素后添加一个新元素 public void addLast(E e){ add(size, e); } // 在所有元素前添加一个新元素 public void addFirst(E e){ add(0, e); } // 获取index索引位置的元素 public E get(int index){ if(index < 0 || index >= size) throw new IllegalArgumentException("Get failed. Index is illegal."); return data[index]; } // 修改index索引位置的元素为e public void set(int index, E e){ if(index < 0 || index >= size) throw new IllegalArgumentException("Set failed. Index is illegal."); data[index] = e; } // 查找数组中是否有元素e public boolean contains(E e){ for(int i = 0 ; i < size ; i ++){ if(data[i].equals(e)) 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; } // 从数组中删除index位置的元素, 返回删除的元素 public E remove(int index){ if(index < 0 || index >= size) throw new IllegalArgumentException("Remove failed. Index is illegal."); E ret = data[index]; for(int i = index + 1 ; i < size ; i ++) data[i - 1] = data[i]; size --; data[size] = null; // loitering objects != memory leak if(size == data.length / 4 && data.length / 2 != 0) resize(data.length / 2); return ret; } // 从数组中删除第一个元素, 返回删除的元素 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); } @Override public String toString(){ StringBuilder res = new StringBuilder(); res.append(String.format("Array: size = %d , capacity = %d\n", size, data.length)); res.append('['); for(int i = 0 ; i < size ; i ++){ res.append(data[i]); if(i != size - 1) res.append(", "); } res.append(']'); return res.toString(); } // 将数组空间的容量变成newCapacity大小 private void resize(int newCapacity){ E[] newData = (E[])new Object[newCapacity]; for(int i = 0 ; i < size ; i ++) newData[i] = data[i]; data = newData; } } ``` ## 2. 栈 ### 2.1 栈的介绍 - 栈（Stack）是一个后进先出（Last In First Out）的有序列表。 - 栈是限制线性表中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表。允许插入和删除的一端，为变化的一端，称为栈顶（Top），另一端为固定的一端，称为栈底（Bottom）。 - 根据栈的定义可知，最先放入栈中元素在栈底，最后放入的元素在栈顶，而删除元素刚好相反，最后放入的元素最先删除，最先放入的元素最后删除。 ### 2.2 栈的应用场景 - 子程序的调用：在跳往子程序前，会先将下个指令的地址存到堆栈中，直到子程序执行完后再将地址取出，以回到原来的程序中。 - 处理递归调用：和子程序的调用类似，只是除了储存下一个指令的地址外，也将参数、区域变量等数据存入堆栈中。 - 表达式的转换[中缀表达式转后缀表达式]与求值(实际解决)。 - 二叉树的遍历。 - 图形的深度优先(depth一first)搜索法。 ### 2.3 自定义栈 ```java public interface Stack { int getSize(); boolean isEmpty(); void push(E e); E pop(); E peek(); } ``` ```java public class ArrayStack implements Stack { Array array; public ArrayStack(int capacity){ array = new Array<>(capacity); } public ArrayStack(){ array = new Array<>(); } @Override public int getSize(){ return array.getSize(); } @Override public boolean isEmpty(){ return array.isEmpty(); } public int getCapacity(){ return array.getCapacity(); } @Override public void push(E e){ array.addLast(e); } @Override public E pop(){ return array.removeLast(); } @Override public E peek(){ return array.getLast(); } @Override public String toString(){ StringBuilder res = new StringBuilder(); res.append("Stack: "); res.append('['); for(int i = 0 ; i < array.getSize() ; i ++){ res.append(array.get(i)); if(i != array.getSize() - 1) res.append(", "); } res.append("] top"); return res.toString(); } } ``` ## 3. 队列 ### 3.1 队列的介绍 - 队列（Queue）是一个有序列表，可以用数组或是链表来实现。 - 遵循先入先出（First In First Out）的原则。即：先存入队列的数据，要先取出。后存入的要后取出。 ### 3.2 自定义队列 ```java public interface Queue { int getSize(); boolean isEmpty(); void enqueue(E e); E dequeue(); E getFront(); } ``` ```java public class ArrayQueue implements Queue { private Array array; public ArrayQueue(int capacity){ array = new Array<>(capacity); } public ArrayQueue(){ array = new Array<>(); } @Override public int getSize(){ return array.getSize(); } @Override public boolean isEmpty(){ return array.isEmpty(); } public int getCapacity(){ return array.getCapacity(); } @Override public void enqueue(E e){ array.addLast(e); } @Override public E dequeue(){ return array.removeFirst(); } @Override public E getFront(){ return array.getFirst(); } @Override public String toString(){ StringBuilder res = new StringBuilder(); res.append("Queue: "); res.append("front ["); for(int i = 0 ; i < array.getSize() ; i ++){ res.append(array.get(i)); if(i != array.getSize() - 1) res.append(", "); } res.append("] tail"); return res.toString(); } public static void main(String[] args) { ArrayQueue queue = new ArrayQueue<>(); for(int i = 0 ; i < 10 ; i ++){ queue.enqueue(i); System.out.println(queue); if(i % 3 == 2){ queue.dequeue(); System.out.println(queue); } } } } ``` ## 4. 链表 ### 4.1 链表的介绍 - 链表（Linked List）是有序的列表，但是它在内存中是存储如下：  - 链表是以节点的方式来存储，是链式存储。 - 每个节点包含data域，next域：指向下一个节点。 - 如图：发现链表的各个节点不一定是连续存储。 - 链表分带头节点的链表和没有头节点的链表，根据实际的需求来确定。 ### 4.2 单链表 - 单链表（带头结点）逻辑结构示意图如下：  - 单链表的应用实例：使用带head头的单向链表实现-水浒英雄排行榜管理完成对英雄人物的增删改查操作。 ```java public class SingleLinkedListDemo { public static void main(String[] args) { //进行测试 //先创建节点 HeroNode hero1 = new HeroNode(1, "宋江", "及时雨"); HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟"); HeroNode hero3 = new HeroNode(3, "吴用", "智多星"); HeroNode hero4 = new HeroNode(4, "林冲", "豹子头"); //创建要给链表 SingleLinkedList singleLinkedList = new SingleLinkedList(); //加入 singleLinkedList.add(hero1); singleLinkedList.add(hero4); singleLinkedList.add(hero2); singleLinkedList.add(hero3); // 测试一下单链表的反转功能 System.out.println("原来链表的情况~~"); singleLinkedList.list(); // System.out.println("反转单链表~~"); // reversetList(singleLinkedList.getHead()); // singleLinkedList.list(); System.out.println("测试逆序打印单链表, 没有改变链表的结构~~"); reversePrint(singleLinkedList.getHead()); /* //加入按照编号的顺序 singleLinkedList.addByOrder(hero1); singleLinkedList.addByOrder(hero4); singleLinkedList.addByOrder(hero2); singleLinkedList.addByOrder(hero3); //显示一把 singleLinkedList.list(); //测试修改节点的代码 HeroNode newHeroNode = new HeroNode(2, "小卢", "玉麒麟~~"); singleLinkedList.update(newHeroNode); System.out.println("修改后的链表情况~~"); singleLinkedList.list(); //删除一个节点 singleLinkedList.del(1); singleLinkedList.del(4); System.out.println("删除后的链表情况~~"); singleLinkedList.list(); //测试一下 求单链表中有效节点的个数 System.out.println("有效的节点个数=" + getLength(singleLinkedList.getHead()));//2 //测试一下看看是否得到了倒数第K个节点 HeroNode res = findLastIndexNode(singleLinkedList.getHead(), 3); System.out.println("res=" + res); */ } //方式2： //可以利用栈这个数据结构，将各个节点压入到栈中，然后利用栈的先进后出的特点，就实现了逆序打印的效果 public static void reversePrint(HeroNode head) { if (head.next == null) { return;//空链表，不能打印 } //创建要给一个栈，将各个节点压入栈 Stack stack = new Stack(); HeroNode cur = head.next; //将链表的所有节点压入栈 while (cur != null) { stack.push(cur); cur = cur.next; //cur后移，这样就可以压入下一个节点 } //将栈中的节点进行打印,pop 出栈 while (stack.size() > 0) { System.out.println(stack.pop()); //stack的特点是先进后出 } } //将单链表反转 public static void reversetList(HeroNode head) { //如果当前链表为空，或者只有一个节点，无需反转，直接返回 if (head.next == null || head.next.next == null) { return; } //定义一个辅助的指针(变量)，帮助我们遍历原来的链表 HeroNode cur = head.next; HeroNode next = null;// 指向当前节点[cur]的下一个节点 HeroNode reverseHead = new HeroNode(0, "", ""); //遍历原来的链表，每遍历一个节点，就将其取出，并放在新的链表reverseHead 的最前端 //动脑筋 while (cur != null) { next = cur.next;//先暂时保存当前节点的下一个节点，因为后面需要使用 cur.next = reverseHead.next;//将cur的下一个节点指向新的链表的最前端 reverseHead.next = cur; //将cur 连接到新的链表上 cur = next;//让cur后移 } //将head.next 指向 reverseHead.next , 实现单链表的反转 head.next = reverseHead.next; } //查找单链表中的倒数第k个结点 【新浪面试题】 //思路 //1. 编写一个方法，接收head节点，同时接收一个index //2. index 表示是倒数第index个节点 //3. 先把链表从头到尾遍历，得到链表的总的长度 getLength //4. 得到size 后，我们从链表的第一个开始遍历 (size-index)个，就可以得到 //5. 如果找到了，则返回该节点，否则返回nulll public static HeroNode findLastIndexNode(HeroNode head, int index) { //判断如果链表为空，返回null if (head.next == null) { return null;//没有找到 } //第一个遍历得到链表的长度(节点个数) int size = getLength(head); //第二次遍历 size-index 位置，就是我们倒数的第K个节点 //先做一个index的校验 if (index <= 0 || index > size) { return null; } //定义给辅助变量， for 循环定位到倒数的index个 HeroNode cur = head.next; //3 // 3 - 1 = 2 for (int i = 0; i < size - index; i++) { cur = cur.next; } return cur; } //方法：获取到单链表的节点的个数(如果是带头结点的链表，需求不统计头节点) /** * * @param head 链表的头节点 * @return 返回的就是有效节点的个数 */ public static int getLength(HeroNode head) { if (head.next == null) { //空链表 return 0; } int length = 0; //定义一个辅助的变量, 这里我们没有统计头节点 HeroNode cur = head.next; while (cur != null) { length++; cur = cur.next; } return length; } } //定义SingleLinkedList 管理我们的英雄 class SingleLinkedList { //先初始化一个头节点, 头节点不要动, 不存放具体的数据 private HeroNode head = new HeroNode(0, "", ""); //返回头节点 public HeroNode getHead() { return head; } //添加节点到单向链表 //思路，当不考虑编号顺序时 //1. 找到当前链表的最后节点 //2. 将最后这个节点的next 指向 新的节点 public void add(HeroNode heroNode) { //因为head节点不能动，因此我们需要一个辅助遍历 temp HeroNode temp = head; //遍历链表，找到最后 while (true) { //找到链表的最后 if (temp.next == null) {// break; } //如果没有找到最后, 将将temp后移 temp = temp.next; } //当退出while循环时，temp就指向了链表的最后 //将最后这个节点的next 指向 新的节点 temp.next = heroNode; } //第二种方式在添加英雄时，根据排名将英雄插入到指定位置 //(如果有这个排名，则添加失败，并给出提示) public void addByOrder(HeroNode heroNode) { //因为头节点不能动，因此我们仍然通过一个辅助指针(变量)来帮助找到添加的位置 //因为单链表，因为我们找的temp 是位于添加位置的前一个节点，否则插入不了 HeroNode temp = head; boolean flag = false; // flag标志添加的编号是否存在，默认为false while (true) { if (temp.next == null) {//说明temp已经在链表的最后 break; // } if (temp.next.no > heroNode.no) { //位置找到，就在temp的后面插入 break; } else if (temp.next.no == heroNode.no) {//说明希望添加的heroNode的编号已然存在 flag = true; //说明编号存在