数据结构的分类

  • 数据结构与算法（漫画算法） - 图1

  • 数据结构与算法（漫画算法） - 图2

    • 逻辑结构是抽象的概念，它依赖于物理结构而存在。

      数组

      数组的基本操作

      读取元素

      image.png

      更新元素

      image.png

      插入元素

      尾部插入

  • 尾部插入，是最简单的情况。直接把插入的元素放在数组尾部的空闲位置即可，等同于更新元素的操作。

    中间插入

  • 中间插入，由于数组的每一个元素都有其固定下标，所以不得不首先把插入位置及后面的元素向后移动，腾出地方，再把要插入的元素放到对应的数组位置上。 ```java package com.mu.array;

/**

  • 中间插入 */ public class MyArray { private int[] array; private int size; //数组实际元素数量

    public MyArray(int capacity) {

    1.  this.array = new int[capacity];
    2.  size = 0;

    }

    /**

    • 数组插入元素 *
    • @param index 插入位置

    • @param element 插入的元素 */ public void insert(int index, int element) throws Exception { //判断访问下标是否超出范围 if (index < 0 || index > size) {

      1.  throw new IndexOutOfBoundsException("超出数组实际元素范围！");

      } //从右向左循环，将元素逐个向右挪1位 for (int i = size - 1; i >= index; i—) {

      1.  array[i + 1] = array[i];

      } //腾出的位置放入新元素 array[index] = element; size++; }

      /**

    • 输出数组 */ public void output() { for (int i = 0; i < size; i++) {

      1.  System.out.print(array[i]+",");

      } }

      public static void main(String[] args) throws Exception { MyArray myArray = new MyArray(10); myArray.insert(0,3); //不用挪，因为数组中还没元素 myArray.insert(1,7); myArray.insert(2,9); myArray.insert(3,5); myArray.insert(1,6); myArray.output(); } }

  1. <a name="y03fg"></a>
  2. #### 超范围插入
  4. - 假如有一个长度为6的数组，已经装满了元素，此时还想插入一个新元素。这就涉及到数组的扩容了，此时可以创建一个新的数组，长度是旧数组的2倍，再把旧数组中的元素统统复制过去，这样就实现了数组的扩容。
  5. - **arraycopy( )方法：**
  6.    - arraycopy()方法用于将一个[数组](https://so.csdn.net/so/search?q=%E6%95%B0%E7%BB%84&spm=1001.2101.3001.7020)的元素快速拷贝到另一个数组。其中的参数如下
  7.    - System.arraycopy(src, srcPos, dest, destPos, length);
  8.    - src表示源数组，srcPos表示源数组中拷贝元素的起始位置。dest表示目标数组，destPos表示拷贝到目标数组的起始位置，length表示拷贝元素的个数。
  9.    - 需要注意的是在进行数组拷贝时，目标数组必须有足够的空间来存放拷贝的元素，否则就会发生下标越界异常。
  10. ```java
  11. package com.mu.array;
  13. /**
  14.  * 超范围插入
  15.  */
  16. public class MyArray2 {
  17.     private int[] array;
  18.     private int size;
  20.     public MyArray2(int capacity) {
  21.         this.array = new int[capacity];
  22.         size = 0;
  23.     }
  25.     /**
  26.      * 插入元素方法
  27.      *
  28.      * @param index   插入位置
  29.      * @param element 插入元素
  30.      */
  31.     public void insert(int index, int element) throws Exception {
  32.         if (index < 0 || index > size) {
  33.             throw new IndexOutOfBoundsException("超出数组实际元素范围！");
  34.         }
  35.         //若元素数量已达到数组容量上限，则对数组进行扩容
  36.         if (size >= array.length) {
  37.             resize();
  38.         }
  39.         //从右向左循环，将元素逐个向右挪1位，将插入位置腾出来
  40.         for (int i = size - 1; i >= index; i--) {
  41.             array[i + 1] = array[i];
  42.         }
  43.         //腾出的位置放入新元素
  44.         array[index] = element;
  45.         size++;
  46.     }
  48.     /**
  49.      * 数组扩容方法
  50.      */
  51.     public void resize() {
  52.         int[] arrayNew = new int[array.length * 2];
  53.         System.arraycopy(array, 0, arrayNew, 0, array.length);
  54.         array = arrayNew;
  55.     }
  57.     /**
  58.      * 输出数组
  59.      */
  60.     public void output() {
  61.         for (int i = 0; i < size; i++) {
  62.             System.out.println(array[i]);
  63.         }
  64.         System.out.println("数组扩容后的大小："+array.length);
  65.     }
  67.     public static void main(String[] args) throws Exception {
  68.         MyArray2 myArray2 = new MyArray2(4);
  69.         myArray2.insert(0,3);
  70.         myArray2.insert(1,7);
  71.         myArray2.insert(2,9);
  72.         myArray2.insert(3,5);
  73.         //超范围插入
  74.         myArray2.insert(1,6);
  75.         myArray2.output();
  77.     }
  80. }

删除元素

  • 数组的删除操作和插入的过程相反，如果删除的元素位于数组中间，其后的元素都需要向前挪一位。 ```java package com.mu.array;

/**

  • 删除操作 */ public class MyArray3 { private int[] array; private int size;

    public MyArray3() {

    1.  this.array = new int[]{1,2,3};
    2.  size = array.length;

    }

    /**

    • 删除操作 *

    • @param index 删除位置 */ public int delete(int index) { if (index < 0 || index >= size) {

      1.  throw new IndexOutOfBoundsException("超出数组实际元素范围！");

      } int deletedElement = array[index]; //从左向右循环，将元素逐个向左挪1位 for (int i = index; i < size - 1; i++) {

      1.  array[i] = array[i + 1];

      } size—; return deletedElement; }

      /**

    • 输出数组 */ public void output() { for (int i = 0; i < size; i++) {

      1.  System.out.println(array[i]);

      } }

      public static void main(String[] args) { MyArray3 myArray3 = new MyArray3(); myArray3.output(); int delete = myArray3.delete(2); System.out.println(“删除的元素：”+delete); myArray3.output();

      } }

  1. <a name="BuvNy"></a>
  2. # 链表
  3. <a name="Kyk28"></a>
  4. ## 链表的基本操作
  5. ```java
  6. package com.mu.linked;
  8. public class MyLinkedList {
  9.     //头结点指针
  10.     private Node head;
  11.     //尾结点指针（为了尾部插入的方便，增加了尾结点指针）
  12.     private Node last;
  13.     //链表实际长度
  14.     private int size;
  16.     /**
  17.      * 链表节点
  18.      */
  19.     private static class Node {
  20.         int data;
  21.         Node next;
  23.         Node(int data) {
  24.             this.data = data;
  25.         }
  26.     }
  28.     /**
  29.      * 查找节点
  30.      *
  31.      * @param index 查找的位置
  32.      * @return 查找的结点
  33.      */
  34.     public Node get(int index) throws Exception {
  35.         if (index < 0 || index > size) {
  36.             throw new IndexOutOfBoundsException("超出链表节点范围");
  37.         }
  38.         Node temp = head; // 1.将查找的指针定位到头结点
  39.         for (int i = 0; i < index; i++) {
  40.             temp = temp.next; // 2.根据头结点的next指针，定位后面的结点
  41.         }
  42.         return temp;
  43.     }
  46.     /**
  47.      * 链表插入元素
  48.      *
  49.      * @param data  插入元素
  50.      * @param index 插入位置
  51.      */
  52.     public void insert(int data, int index) throws Exception {
  53.         if (index < 0 || index > size) {
  54.             throw new IndexOutOfBoundsException("超出链表节点范围");
  55.         }
  56.         //将插入的数据包装到Node节点中
  57.         Node insertNode = new Node(data);
  58.         if (size == 0) {
  59.             //空链表
  60.             head = insertNode;
  61.             last = insertNode;
  62.         } else if (index == 0) {
  63.             //头部插入
  64.             insertNode.next = head; //1.把新节点的next指针指向原先的头结点
  65.             head = insertNode;//2.把新节点变为链表的头结点
  66.         } else if (index == size) {
  67.             //尾部插入
  68.             last.next = insertNode;//1.把最后一个节点的next指针指向新插入的节点
  69.             last = insertNode;//把新节点变为链表的尾结点
  70.         } else {
  71.             //中间插入
  72.             Node prevNode = get(index - 1); //1.获取插入位置的前置结点
  73.             insertNode.next = prevNode.next; //2.新节点的next指针指向插入位置的结点
  74.             prevNode.next = insertNode; //3.前置结点的next指针，指向新节点
  75.         }
  76.         size++;
  77.     }
  79.     /**
  80.      * 链表删除元素
  81.      *
  82.      * @param index 删除位置
  83.      * @return 删除的结点
  84.      */
  85.     public Node remove(int index) throws Exception {
  86.         if (index < 0 || index >= size) {
  87.             throw new IndexOutOfBoundsException("超出链表结点范围");
  88.         }
  89.         Node removeNode = null;
  90.         if (index == 0) {
  91.             //删除头结点
  92.             removeNode = head;
  93.             head = head.next; //1.把链表的头结点设为原头结点的next指针
  94.         } else if (index == size - 1) {
  95.             //删除尾部结点
  96.             Node prevNode = get(index - 1);//1.获取倒数第2个结点
  97.             removeNode = prevNode.next;
  98.             prevNode.next = null; //2. 将倒数第2个结点的next指针指向空即可
  99.             last = prevNode; //3.尾结点指针指向preNode
  100.         } else {
  101.             //删除中间结点
  102.             Node prevNode = get(index - 1); //1.目标结点的前置结点
  103.             removeNode = prevNode.next;
  104.             prevNode.next = prevNode.next.next; //2.把要删除的目标节点的前置结点的next指针指向要删除的元素的下一个结点
  105.         }
  106.         size--;
  107.         return removeNode;
  108.     }
  110.     /**
  111.      * 输出链表
  112.      */
  113.     public void output() {
  114.         Node temp = head;
  115.         while (temp != null) {
  116.             System.out.println(temp.data);
  117.             temp = temp.next;
  118.         }
  119.     }
  121.     public static void main(String[] args) throws Exception {
  122.         MyLinkedList myLinkedList = new MyLinkedList();
  123.         myLinkedList.insert(3, 0);
  124.         myLinkedList.insert(4, 1);
  125.         myLinkedList.insert(5, 2);
  126.         myLinkedList.insert(6, 3);
  127.         Node remove = myLinkedList.remove(2);
  128.         myLinkedList.remove(2);
  129.         myLinkedList.output();
  130.     }
  132. }

数组VS链表

查找 更新 插入 删除
数组 O(1) O(1) O(n) O(n)
链表 O(n) O(1) O(1) O(1)
  • 数组的优势在于能够快速定位元素，对于读操作多、写操作少的场景来说，数组更适合。
  • 链表的优势在于能够灵活的进行插入和删除操作，如果需要在尾部频繁插入、删除元素，链表更适合。

    栈和队列