Rubin's Blog

  • 首页
  • 关于作者
  • 隐私政策
享受恬静与美好~~~
分享生活的点点滴滴~~~
  1. 首页
  2. 数据结构和算法
  3. 正文

数据结构之线性表

2022年1月4日 296点热度 0人点赞 0条评论

线性表(Linear List)就是数据排成像一条线一样的结构,数据只有前后两个方向:

数组

概念

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

数组下标从零开始,为什么呢?

存储原理

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

模拟内存存储:

  • 灰色格子:被使用的内存
  • 橙色格子:空闲的内存
  • 红色格子:数组占用的内存

数组可以根据下标随机访问数据。比如一个整型数据 int[] 长度为5:

假设首地址是:1000,int是4字节(32位),实际内存存储是位,随机元素寻址:

a[i]_address=a[0]_address+i*4

该公式解释了三个方面:

  • 连续性分配
  • 相同的类型
  • 下标从0开始

操作

  • 读取元素

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

int n=nums[2]
  • 更新元素
nums[3]= 10;

注意不要数组越界

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

  • 插入元素

有三种情况:

尾部插入

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

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

a[6]=10

中间插入

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

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

超范围插入

假如现在有一个数组,已经装满了元素,这时还想插入一个新元素,或者插入位置是越界的,这时就要对原数组进行扩容:可以创建一个新数组,长度是旧数组的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.rubin.datastructure.array;

import java.util.Arrays;

public class RubinIntArray {

    private int[] items;

    private int size;

    public RubinIntArray() {
        this.items = new int[10];
        this.size = 0;
    }

    public int add(int item) {
        if (size == items.length) {
            resize();
        }
        int index = size;
        items[index] = item;
        ++size;
        return index;
    }

    public int insert(int index, int item) {
        if (index > size) {
            throw new RuntimeException("the index is out of bound");
        }
        if (index == size) {
            add(item);
            return 0;
        }
        if (size == items.length) {
            resize();
        }
        for (int i = size; i > index; i--) {
            items[i] = items[i - 1];
        }
        int oldValue = items[index];
        items[index] = item;
        ++size;
        return oldValue;
    }

    public int update(int index, int item) {
        if (index > size) {
            throw new RuntimeException("the index is out of bound");
        }
        int oldValue = items[index];
        items[index] = item;
        return oldValue;
    }

    public int get(int index) {
        if (index > size) {
            throw new RuntimeException("the index is out of bound");
        }
        return items[index];
    }

    public int delete(int index) {
        if (index >= size) {
            throw new RuntimeException("the index is out of bound");
        }
        int oldValue = items[index];
        if (index == (size -1)) {
            items[index] = 0;
            --size;
            return oldValue;
        }
        for (int i = index + 1; i < size; i++) {
            items[i - 1] = items[i];
        }
        --size;
        items[size] = 0;
        return oldValue;
    }

    public int size() {
        return size;
    }

    private void resize() {
        int[] newItems = new int[items.length * 2];
        System.arraycopy(items, 0, newItems, 0, items.length);
        items = newItems;
    }

    @Override
    public String toString() {
        return Arrays.toString(items);
    }

}
package com.rubin.datastructure.array;

public class Main {

    public static void main(String[] args) {
        RubinIntArray rubinIntArray = new RubinIntArray();
        System.out.println(rubinIntArray);
        for (int i = 0; i < 19; i++) {
            rubinIntArray.add(i);
        }
        System.out.println(rubinIntArray);
        rubinIntArray.insert(19, 19);
        System.out.println(rubinIntArray);
        rubinIntArray.insert(0, 20);
        System.out.println(rubinIntArray);
        rubinIntArray.update(0, 100);
        System.out.println(rubinIntArray);
        rubinIntArray.delete(rubinIntArray.size() - 1);
        System.out.println(rubinIntArray);
        rubinIntArray.delete(0);
        System.out.println(rubinIntArray);
    }

}

时间复杂度

读取和更新都是随机访问,所以是O(1)。

插入数组扩容的时间复杂度是O(n),插入并移动元素的时间复杂度也是O(n),综合起来插入操作的时间复杂度是O(n)。

删除操作,只涉及元素的移动,时间复杂度也是O(n)。

优缺点

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

缺点:插入和删除元素方面。由于数组元素连续紧密地存储在内存中,插入、删除元素都会导致大量元素被迫移动,影响效率 (ArrayList LinkedList )。

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

应用

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

数据结构和算法的可视化网站:https://www.cs.usfca.edu/~galles/visualization/Algorithms.html。

链表

概念

链表(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为空。

操作

  • 查找节点

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

  • 更新节点

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

  • 插入节点

尾部插入

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

头部插入

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

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

中间插入

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

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

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

  • 删除节点

尾部删除

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

头部删除

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

中间删除

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

完整代码:

package com.rubin.datastructure.linkedlist;

import lombok.Data;

@Data
public class RubinNode {

    private int id;

    private String name;

    private RubinNode next;

    public RubinNode() {
    }

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

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

}
package com.rubin.datastructure.linkedlist;

public class RubinLinkedList {

    private RubinNode head;

    public RubinLinkedList() {
        this.head = new RubinNode(0, "");
    }

    /**
     * 添加节点:从头插入
     *
     * @param node  
     */
    public void addNode(RubinNode node) {
        //从头插入
        RubinNode tmp = head;
        while (true) {
            //到尾节点
            if (tmp.getNext() == null) {
                break;
            }
            //后移一个节点
            tmp = tmp.getNext();
        }
        tmp.setNext(node);
    }

    public void addByIdOrder(RubinNode node) {
        //从头插入
        RubinNode tmp = head;
        while (true) {
            //到尾节点
            if (tmp.getNext() == null) {
                break;
            }
            //节点存在
            if (tmp.getNext().getId() == node.getId()) {
                break;
            }
            if (tmp.getNext().getId() > node.getId()) {
                break;
            }
            tmp = tmp.getNext();
        }
        //交换位置
        node.setNext(tmp.getNext());
        tmp.setNext(node);
    }

    public void showList() {
        if (head.getNext() == null) {
            System.out.println("the list is empty");
            return;
        }
        RubinNode tmp = head.getNext();
        while (tmp != null) {
            System.out.println(tmp);
            tmp = tmp.getNext();
        }

    }

}
package com.rubin.datastructure.linkedlist;

public class Main {

    public static void main(String[] args) {
        RubinNode n1 = new RubinNode(1, "张飞");
        RubinNode n2 = new RubinNode(2, "关羽");
        RubinNode n3 = new RubinNode(3, "赵云");
        RubinNode n4 = new RubinNode(4, "黄忠");
        RubinNode n5 = new RubinNode(5, "马超");
        RubinLinkedList rubinLinkedList = new RubinLinkedList();
        rubinLinkedList.addByIdOrder(n4);
        rubinLinkedList.addByIdOrder(n5);
        rubinLinkedList.addByIdOrder(n1);
        rubinLinkedList.addByIdOrder(n2);
        rubinLinkedList.addByIdOrder(n3);
        rubinLinkedList.showList();
    }

}

时间复杂度

查找节点 : O(n)

插入节点:O(1)

更新节点:O(1)

删除节点:O(1)

优缺点

  • 优势

插入、删除、更新效率高

省空间

  • 劣势

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

应用

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

数组与链表的对比

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

数组的优势在于能够快速定位元素,对于读操作多、写操作少的场景来说,用数组更合适一些。

链表的优势在于能够灵活地进行插入和删除操作,如果需要在尾部频繁插入、删除元素,用链表更合适一些。

数组和链表是线性数据存储的物理存储结构:即顺序存储和链式存储。

栈

栈和队列都属于线性数据的逻辑存储结构。

概念

栈(stack)是一种线性数据结构,栈中的元素只能先入后出(First In Last Out,简称FILO)。

最早进入的元素存放的位置叫作栈底(bottom),最后进入的元素存放的位置叫作栈顶 (top)。

存储原理

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

栈的数组实现如下:

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

栈的链表实现如下:

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

操作

  • 入栈(压栈)

入栈操作(push)就是把新元素放入栈中,只允许从栈顶一侧放入元素,新元素的位置将会成为新的栈顶:

  • 出栈(弹栈)

出栈操作(pop)就是把元素从栈中弹出,只有栈顶元素才允许出栈,出栈元素的前一个元素将会成为新的栈顶:

完整代码:

数组实现:

package com.rubin.datastructure.stack;

public class RubinArrayStack {

    private int[] items;

    private int size;

    public RubinArrayStack(int cap) {
        items = new int[cap];
        size = 0;
    }

    public boolean push(int item) {
        if (size == items.length) {
            return false;
        }
        items[size] = item;
        ++size;
        return true;
    }

    public int pop() {
        if (size == 0) {
            return 0;
        }
        --size;
        return items[size];
    }

    public static void main(String[] args) {
        RubinArrayStack rubinArrayStack = new RubinArrayStack(10);
        rubinArrayStack.push(3);
        rubinArrayStack.push(1);
        rubinArrayStack.push(5);
        rubinArrayStack.push(2);
        rubinArrayStack.push(7);
        System.out.println(rubinArrayStack.pop());
        System.out.println(rubinArrayStack.pop());
        System.out.println(rubinArrayStack.pop());
        System.out.println(rubinArrayStack.pop());
        System.out.println(rubinArrayStack.pop());
    }

}

链表实现:

package com.rubin.datastructure.stack;

public class RubinLinkedStack {

    private RubinStackNode head;
    private int size;

    public RubinLinkedStack() {
        size = 0;
    }

    public void push(int item) {
        if (size == 0) {
            head = new RubinStackNode(item);
        } else {
            RubinStackNode newHead = new RubinStackNode(item);
            newHead.next = head;
            head = newHead;
        }
        ++size;
    }

    public int pop() {
        if (size == 0) {
            return 0;
        }
        RubinStackNode oldHead = head;
        head = head.next;
        --size;
        return oldHead.value;
    }

    static class RubinStackNode {
        int value;
        RubinStackNode next;
        public RubinStackNode(int value) {
            this.value = value;
        }
    }

    public static void main(String[] args) {
        RubinLinkedStack rubinLinkedStack = new RubinLinkedStack();
        rubinLinkedStack.push(1);
        rubinLinkedStack.push(2);
        rubinLinkedStack.push(3);
        rubinLinkedStack.push(4);
        rubinLinkedStack.push(5);
        System.out.println(rubinLinkedStack.pop());
        System.out.println(rubinLinkedStack.pop());
        System.out.println(rubinLinkedStack.pop());
        System.out.println(rubinLinkedStack.pop());
        System.out.println(rubinLinkedStack.pop());
    }

}

时间复杂度

入栈和出栈的时间复杂度都是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.rubin.datastructure.queue;

public class RubinArrayQueue {

    private int[] items;

    private int head, tail;

    private int size;

    public RubinArrayQueue(int cap) {
        items = new int[cap];
        head = tail = size = 0;
    }

    public boolean enqueue(int item) {
        if (size == items.length) {
            return false;
        }
        items[tail] = item;
        ++size;
        ++tail;
        if (tail == items.length) {
            tail = 0;
        }
        return true;
    }

    public int dequeue() {
        if (size == 0) {
            return 0;
        }
        int result = items[head];
        --size;
        ++head;
        if (head == items.length) {
            head = 0;
        }
        return result;
    }

    public static void main(String[] args) {
        RubinArrayQueue rubinArrayQueue = new RubinArrayQueue(10);
        for (int i = 0; i < 10; i++) {
            rubinArrayQueue.enqueue(i);
        }
        for (int j = 0; j < 10; j++) {
            System.out.println(rubinArrayQueue.dequeue());
        }
    }

}

链表实现:

package com.rubin.datastructure.queue;

public class RubinLinkedQueue {

    private RubinQueueNode head;
    private RubinQueueNode tail;

    private int size;

    public RubinLinkedQueue() {
        head = tail = null;
        size = 0;
    }

    static class RubinQueueNode {
        int value;
        RubinQueueNode next;
        public RubinQueueNode(int value) {
            this.value = value;
        }
    }

    public void enqueue(int item) {
        if (size == 0) {
            head = tail = new RubinQueueNode(item);
        } else {
            RubinQueueNode newTail = new RubinQueueNode(item);
            tail.next = newTail;
            tail = newTail;
        }
        ++size;
    }

    public int dequeue() {
        if (size == 0) {
            return 0;
        }
        RubinQueueNode h = head;
        int result = h.value;
        head = head.next;
        --size;
        h.next = null;
        return result;
    }

    public static void main(String[] args) {
        RubinLinkedQueue rubinLinkedQueue = new RubinLinkedQueue();
        for (int i = 0; i < 10; i++) {
            rubinLinkedQueue.enqueue(i);
        }
        for (int j = 0; j < 10; j++) {
            System.out.println(rubinLinkedQueue.dequeue());
        }
    }

}

时间复杂度

入队和出队都是O(1)。

应用

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

以上就是本文的全部内容。欢迎各位小伙伴积极留言交流~~~

本作品采用 知识共享署名 4.0 国际许可协议 进行许可
标签: 数据结构和算法
最后更新:2022年6月9日

RubinChu

一个快乐的小逗比~~~

打赏 点赞
< 上一篇
下一篇 >

文章评论

取消回复
  • 数组
  • 链表
  • 栈
  • 队列

COPYRIGHT © 2021 rubinchu.com. ALL RIGHTS RESERVED.

Theme Kratos Made By Seaton Jiang

京ICP备19039146号-1