数据结构之线性表详解

数组

概念：

数组（Array）是有限个相同类型的变量所组成的有序集合，数组中的每一个变量被称为元素。数组是最为简单、最为常用的数据结构。

存储原理：

数组用一组连续的内存空间来存储一组具有相同类型的数据

(模拟内存存储)

灰色格子：被使用的内存

橙色格子：空闲的内存

红色格子：数组占用的内存

操作：

读取元素

根据下标读取元素的方式叫作随机读取。

int n=nums[2]

更新元素

nums[3]= 10;

注意：不要数组越界。

读取和更新都可以随机访问，时间复杂度为O(1)

插入元素

有三种情况：

1.尾部插入

在数据的实际元素数量小于数组长度的情况下：

直接把插入的元素放在数组尾部的空闲位置即可，等同于更新元素的操作

a[6]=10

2.中间插入

在数据的实际元素数量小于数组长度的情况下：

由于数组的每一个元素都有其固定下标，所以首先把插入位置及后面的元素向后移动，腾出地方，再把要插入的元素放到对应的数组位置上。

3.超范围插入

假如现在有一个数组，已经装满了元素，这时还想插入一个新元素，或者插入位置是越界的

这时就要对原数组进行扩容：

可以创建一个新数组，长度是旧数组的2倍，再把旧数组中的元素统统复制过去，这样就实现了数组的扩容。

int[] numsNew = new int[nums.length * 2];
System.arraycopy(nums, 0, numsNew, 0, nums.length);
// 原数组就丢掉了，资源浪费
nums = numsNew;

删除元素

数组的删除操作和插入操作的过程相反，如果删除的元素位于数组中间，其后的元素都需要向前挪动1位。

for (int i = p; i < nums.length; i++) {
    nums[i - 1] = nums[i];
}

完整代码如下：

package com.zou.array;

/**
 * @author: 邹祥发
 * @date: 2021/12/1 15:20
 */
public class ArrayDemo01 {
    int[] nums = new int[8];

    public ArrayDemo01() {
        nums[0] = 3;
        nums[1] = 1;
        nums[2] = 2;
        nums[3] = 5;
        nums[4] = 4;
        nums[5] = 9;
    }

    //获取某一个元素
    public int get(int i) {
        return nums[i];
    }

    //更新某一个元素
    public void update(int i, int n) {
        nums[i] = n;
    }

    //尾部插入
    public void insertTail(int n) {
        nums[6] = n;
    }

    //中间插入
    public void insertMiddle(int p, int n) {
        for (int i = nums.length - 1; i >= p - 1; i--) {
            //能取到值
            if (nums[i] != 0) {
                nums[i + 1] = nums[i];
            }
        }
        nums[p - 1] = n;
    }

    /**
     * 旧数组复制到新数组
     */
    public void resize() {
        int[] numsNew = new int[nums.length * 2];
        System.arraycopy(nums, 0, numsNew, 0, nums.length);
        nums = numsNew;
    }

    public void insertOutOfBounds(int p, int n) {
        //数组扩容
        resize();
        nums[p - 1] = n;
    }

    public void deleteMiddle(int p) {
        for (int i = p; i < nums.length; i++) {
            nums[i - 1] = nums[i];
        }
    }

    public void display() {
        for (int n : nums) {
            System.out.print(n + " ");
        }
    }

    public static void main(String[] args) {
        ArrayDemo01 demo01 = new ArrayDemo01();
        System.out.print("原数组：");
        demo01.display();
        System.out.println();

        System.out.println("获取下标为3的元素：" + demo01.get(3));

        System.out.print("将下标为2的元素的值更新为10：");
        demo01.update(2, 10);
        demo01.display();
        System.out.println();

        System.out.print("尾部插入值为21的元素：");
        demo01.insertTail(21);
        demo01.display();
        System.out.println();

        System.out.print("在下标为3的元素后面插入值为6的元素：");
        demo01.insertMiddle(5, 6);
        demo01.display();
        System.out.println();

        System.out.print("在下标为8的元素后面插入值为18的元素（数组扩容）：");
        demo01.insertOutOfBounds(10, 18);
        demo01.display();
        System.out.println();

        System.out.print("删除下标为4的元素：");
        demo01.deleteMiddle(5);
        demo01.display();
        System.out.println();

    }
}

运行结果：

原数组：3 1 2 5 4 9 0 0 
获取下标为3的元素：5
将下标为2的元素的值更新为10：3 1 10 5 4 9 0 0 
尾部插入值为21的元素：3 1 10 5 4 9 21 0 
在下标为3的元素后面插入值为6的元素：3 1 10 5 6 4 9 21 
在下标为8的元素后面插入值为18的元素（数组扩容）：3 1 10 5 6 4 9 21 0 18 0 0 0 0 0 0 
删除下标为4的元素：3 1 10 5 4 9 21 0 18 0 0 0 0 0 0 0

时间复杂度：

读取、更新操作都是随机访问，所以时间复杂度是O(1)

插入、删除操作，均涉及元素的移动，时间复杂度是O(n)

优缺点：

优点：

数组拥有非常高效的随机访问能力，只要给出下标，就可以用常量时间找到对应元素。

缺点：

插入和删除元素方面。

由于数组元素连续紧密地存储在内存中，插入、删除元素都会导致大量元素被迫移动，影响效率。

申请的空间必须是连续的，也就是说即使有空间也可能因为没有足够的连续空间而创建失败。如果超出范围，需要重新申请内存进行存储，原空间就浪费了。

应用：

数组是基础的数据结构，应用太广泛了，ArrayList、Redis、消息队列等等。

链表

概念：

链表（linked list）是一种在物理上非连续、非顺序的数据结构，由若干节点（node）所组成。

链表中数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元
素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据
域，另一个是存储下一个结点地址的指针域。

常见的链表包括：单链表、双向链表、循环链表

单链表

单向链表的每一个节点又包含两部分，一部分是存放数据的变量data，另一部分是指向下一个节
点的指针next。
```
Node{
    int data;
    Node next;
}
```
双向链表

双向链表的每一个节点除了拥有data和next指针，还拥有指向前置节点的prev指针。
```
Node{
    int data;
    Node next;
    Node prev;
}
```
循环链表

链表的尾节点指向头节点形成一个环，称为循环链表。

存储原理：

数组在内存中的存储方式是顺序存储（连续存储），链表在内存中的存储方式则是随机存储（链式存储）。

链表的每一个节点分布在内存的不同位置，依靠next指针关联起来。这样可以灵活有效地利用零散的碎片空间。

链表的第1个节点被称为头节点（3），没有任何节点的next指针指向它，或者说它的前置节点为空，头结点用来记录链表的基地址。

有了它，我们就可以遍历得到整条链表。链表的最后1个节点被称为尾节点（2），它指向的next为空。

操作：

查找节点

在查找元素时，链表只能从头节点开始向后一个一个节点逐一查找。

更新节点

找到要更新的节点，然后把旧数据替换成新数据

插入节点

1.尾部插入

把最后一个节点的next指针指向新插入的节点即可

2.头部插入

第1步，把新节点的next指针指向原先的头节点

第2步，把新节点变为链表的头节点

3.中间插入

第1步，新节点的next指针，指向插入位置的节点

第2步，插入位置前置节点的next指针，指向新节点

只要内存空间允许，能够插入链表的元素是无限的，不需要像数组那样考虑扩容的问题

删除节点

1.尾部删除

把倒数第2个节点的next指针指向空即可

2.头部删除

把链表的头节点设为原先头节点的next指针即可

3.中间删除

把要删除节点的前置节点的next指针，指向要删除元素的下一个节点即可

完整代码如下：

package com.zou.linkedlist;

/**
 * @author: 邹祥发
 * @date: 2021/12/2 13:53
 * 节点
 */
public class Node {
    int id;
    String name;
    //下一个节点
    Node next;

    public Node(int id, String name) {
        this.id = id;
        this.name = name;
    }

    @Override
    public String toString() {
        return "Node{" +
                "id=" + id + ",name='" + name + '\'' +
                '}' ;
    }
}

package com.zou.linkedlist;

/**
 * @author: 邹祥发
 * @date: 2021/12/2 13:47
 * 单链表
 */
public class SingleLinkedList {

    //初始化头节点
    private final Node head = new Node(0, "");

    //添加节点：从头插入
    public void addNode(Node node) {
        //从头插入
        Node tmp = head;
        while (tmp.next != null) {
            //到尾节点
            //后移一个节点
            tmp = tmp.next;
        }
        tmp.next = node;
    }

    //添加节点：从中间插入
    public void addByIdOrder(Node node) {
        //从头插入
        Node tmp = head;
        while (true) {
            //到尾节点
            if (tmp.next == null) {
                break;
            }
            //节点存在
            if (tmp.next.id > node.id || tmp.next.id == node.id) {
                break;
            }
            tmp = tmp.next;
        }
        //交换位置
        node.next = tmp.next;
        tmp.next = node;
    }

    //遍历链表
    public void showList() {
        //空链表
        if (head.next == null) {
            System.out.println("链表为空！");
            return;
        }
        Node tmp = head.next;
        while (true) {
            if (tmp == null) {
                return;
            }
            System.out.println(tmp);
            //指针下移
            tmp = tmp.next;
        }
    }

    public static void main(String[] args) {
        Node n1 = new Node(1, "张飞");
        Node n2 = new Node(2, "关羽");
        Node n3 = new Node(3, "赵云");
        Node n4 = new Node(4, "黄忠");
        Node n5 = new Node(5, "马超");
        Node n6 = new Node(6, "吕布");

        SingleLinkedList sll = new SingleLinkedList();
        sll.addByIdOrder(n4);
        sll.addByIdOrder(n5);
        sll.addByIdOrder(n6);
        sll.addByIdOrder(n3);
        sll.addByIdOrder(n2);
        sll.addNode(n1);

        sll.showList();
    }
}

运行结果：

Node{id=2,name='关羽'}
Node{id=3,name='赵云'}
Node{id=4,name='黄忠'}
Node{id=5,name='马超'}
Node{id=6,name='吕布'}
Node{id=1,name='张飞'}

时间复杂度：

查找节点：O(n)

插入、更新、删除节点：O(1)

优缺点：

优点：

插入、删除、更新效率高

省空间

缺点：

查询效率较低，不能随机访问

应用：

链表的应用也非常广泛，比如树、图、Redis的列表、LRU算法实现、消息队列等

数组与链表对比

数据结构没有绝对的好与坏，数组和链表各有千秋。

数组的优势在于能够快速定位元素，对于读操作多、写操作少的场景来说，用数组更合适一些
链表的优势在于能够灵活地进行插入和删除操作，如果需要在尾部频繁插入、删除元素，用链表更合适
一些
数组和链表是线性数据存储的物理存储结构：即顺序存储和链式存储。

栈

概念：

栈（stack）是一种线性数据结构，栈中的元素只能先入后出（First In Last Out，简称FILO）。最早进入的元素存放的位置叫作栈底（bottom），最后进入的元素存放的位置叫作栈顶（top）。

存储原理：

栈既可以用数组来实现，也可以用链表来实现

栈的数组实现如下：

数组实现的栈也叫顺序栈或静态栈

栈的链表实现如下：

链表实现的栈也叫做链式栈或动态栈

操作：

入栈（压栈）

入栈操作（push）就是把新元素放入栈中，只允许从栈顶一侧放入元素，新元素的位置将会成为新的栈顶

出栈（弹栈）

出栈操作（pop）就是把元素从栈中弹出，只有栈顶元素才允许出栈，出栈元素的前一个元素将会成为新的栈顶。

完整代码如下：

数组实现：

package com.zou.stack;

/**
 * @author: 邹祥发
 * @date: 2021/12/10 10:58
 * 数组实现
 */
public class ArrayStack {
    //数组
    private final int[] nums;
    //栈中元素个数
    private int count;

    //初始化数组，申请一个大小为n的数组空间
    public ArrayStack(int n) {
        this.nums = new int[n];
        this.count = 0;
    }

    //入栈操作
    public void push(int n) {
        // 数组空间不够了，直接返回false，入栈失败。 没有扩容
        if (count >= nums.length) return;
        // 将item放到下标为count的位置，并且count加一
        nums[count] = n;
        count++;
    }

    //出栈操作
    public int pop() {
        // 栈为空，则直接返回0
        if (count == 0) return 0;
        // 返回下标为count-1的数组元素，并且栈中元素个数count减一
        int n = nums[count - 1];
        count--;
        return n;
    }

    public static void main(String[] args) {

        ArrayStack as = new ArrayStack(8);
        System.out.println("元素3,5,1,4依次进栈");
        as.push(3);
        as.push(5);
        as.push(1);
        as.push(4);

        System.out.println("1.元素" + as.pop() + "出栈");
        System.out.println("2.元素" + as.pop() + "出栈");
        System.out.println("3.元素" + as.pop() + "出栈");
        System.out.println("4.元素" + as.pop() + "出栈");

    }
}

运行结果：

元素3,5,1,4依次进栈
1.元素4出栈
2.元素1出栈
3.元素5出栈
4.元素3出栈

链表实现：

package com.zou.stack;

/**
 * @author: 邹祥发
 * @date: 2021/12/10 11:10
 * 链表实现
 */
public class LinedStack {

    /**
     * 链表节点
     */
    public static class Node {
        int value;
        Node next;

        public Node(int value) {
            this.value = value;
        }
    }

    int size;
    //头节点
    Node head;

    //初始化
    public LinedStack() {
        head = null;
        size = 0;
    }

    // 入栈操作
    public void push(Node node) {
        // head
        if (size != 0) {
            node.next = head;
        }
        head = node;
        size++;
    }

    // 出栈操作
    public Node pop() {
        if (size > 0) {
            Node oldHead = head;
            head = head.next;
            size--;
            return oldHead;
        } else {
            return null;
        }
    }

    public static void main(String[] args) {

        System.out.println("元素3,5,1,4依次进栈");
        Node n1 = new Node(3);
        Node n2 = new Node(5);
        Node n3 = new Node(1);
        Node n4 = new Node(4);

        LinedStack ls = new LinedStack();
        ls.push(n1);
        ls.push(n2);
        ls.push(n3);
        ls.push(n4);

        System.out.println("1.元素" + ls.pop().value + "出栈");
        System.out.println("2.元素" + ls.pop().value + "出栈");
        System.out.println("3.元素" + ls.pop().value + "出栈");
        System.out.println("4.元素" + ls.pop().value + "出栈");

    }
}

运行结果：

元素3,5,1,4依次进栈
1.元素4出栈
2.元素1出栈
3.元素5出栈
4.元素3出栈

时间复杂度：

入栈和出栈的时间复杂度都是O(1)

支持动态扩容的顺序栈

当数组空间不够时，我们就重新申请一块更大的内存，将原来数组中数据统统拷贝过去。这样就实现了一个支持动态扩容的数组，通过前面学过的知识，可以得知入栈的时间复杂度是O(n)

应用：

函数调用

每进入一个函数，就会将临时变量作为一个栈入栈，当被调用函数执行完成，返回之后，将这个函数对应的栈帧出栈

浏览器的后退功能

我们使用两个栈，X 和 Y，我们把首次浏览的页面依次压入栈 X，当点击后退按钮时，再依次从栈X 中出栈，并将出栈的数据依次放入栈 Y。当我们点击前进按钮时，我们依次从栈 Y 中取出数据，放入栈 X 中。当栈 X 中没有数据时，那就说明没有页面可以继续后退浏览了。当栈 Y 中没有数据，那就说明没有页面可以点击前进按钮浏览了

队列

概念：

队列（queue）是一种线性数据结构，队列中的元素只能先入先出（First In First Out，简称 FIFO）。

队列的出口端叫作队头（front），队列的入口端叫作队尾（rear）。

存储原理：

队列这种数据结构既可以用数组来实现，也可以用链表来实现

数组实现

用数组实现时，为了入队操作的方便，把队尾位置规定为最后入队元素的下一个位置

用数组实现的队列叫作顺序队列

链表实现

用链表实现的队列叫作链式队列

操作：

入队

入队（enqueue）就是把新元素放入队列中，只允许在队尾的位置放入元素，新元素的下一个位置将会成为新的队尾。

出队

出队操作（dequeue）就是把元素移出队列，只允许在队头一侧移出元素，出队元素的后一个元素将会成为新的队头。

完整代码如下：

数组实现：

package com.zou.queue;

/**
 * @author: 邹祥发
 * @date: 2021/12/10 16:31
 * 用数组实现的队列
 */
public class ArrayQueue {

    int[] nums;
    // head表示队头下标，tail表示队尾下标
    int head = 0;
    int tail = 0;

    // 申请一个大小为capacity的数组
    public ArrayQueue(int size) {
        nums = new int[size];
    }

    // 入队
    public void enqueue(int n) {
        // 如果 tail=nums.length 表示队列已经满了
        if (tail == nums.length) return;
        nums[tail] = n;
        ++tail;
    }

    // 出队
    public int dequeue() {
        // 如果head == tail 表示队列为空
        if (head == tail) return 0;
        int ret = nums[head];
        ++head;
        return ret;
    }

    public static void main(String[] args) {

        ArrayQueue aq = new ArrayQueue(8);
        System.out.println("元素3,5,1,4依次进队列");
        aq.enqueue(3);
        aq.enqueue(5);
        aq.enqueue(1);
        aq.enqueue(4);

        System.out.println("元素" + aq.dequeue() + "出队列");
        System.out.println("元素" + aq.dequeue() + "出队列");
        System.out.println("元素" + aq.dequeue() + "出队列");
        System.out.println("元素" + aq.dequeue() + "出队列");

    }
}

运行结果：

元素3,5,1,4依次进队列
元素3出队列
元素5出队列
元素1出队列
元素4出队列

链表实现：

package com.zou.queue;

/**
 * @author: 邹祥发
 * @date: 2021/12/10 16:36
 * 用链表实现的队列
 */
public class LinkedQueue {

    Node head;
    Node tail;
    int size;

    public void enqueue(Node node) {
        if (tail == null) {
            head = node;
            tail = node;
        } else {
            tail.next = node;
            tail = node;
        }
        size++;
    }

    public Node dequeue() {
        if (head == null) return null;
        Node h = head;
        //将拉取的节点的下一个节点变成新的表头
        head = head.next;
        //把旧的表头的下一个节点指向设置为null，让gc回收
        h.next = null;
        //队列为空
        if (head == null)
            tail = null;
        size--;
        return h;
    }

    public static void main(String[] args) {

        Node n1 = new Node(3);
        Node n2 = new Node(5);
        Node n3 = new Node(1);
        Node n4 = new Node(4);

        LinkedQueue lq = new LinkedQueue();
        System.out.println("元素3,5,1,4依次进队列");
        lq.enqueue(n1);
        lq.enqueue(n2);
        lq.enqueue(n3);
        lq.enqueue(n4);

        System.out.println("元素" + lq.dequeue().value + "出队列");
        System.out.println("元素" + lq.dequeue().value + "出队列");
        System.out.println("元素" + lq.dequeue().value + "出队列");
        System.out.println("元素" + lq.dequeue().value + "出队列");

    }
}

运行结果：

元素3,5,1,4依次进队列
元素3出队列
元素5出队列
元素1出队列
元素4出队列

时间复杂度：

入队和出队都是O(1)

应用：

资源池、消息队列、命令队列等等

本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名，转载请标明出处。
最后编辑时间为: 2021/12/10 16:53:19

数据结构之线性表详解

数组

链表

栈

队列

评论区 0

操作成功