1. Toy模板网首页
  2. > Toy博客

【Java数据结构】顺序表、队列、栈、链表、哈希表

10月前 作者：RenX000 分类：Toy博客 阅读(43) 违法举报

这篇具有很好参考价值的文章主要介绍了【Java数据结构】顺序表、队列、栈、链表、哈希表。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

顺序表ArrayList

定义

是一个有类型参数（type parameter）的范型表（generic class）
能够自动调整容量，并且不需要写额外的代码

存放数据使用数组但是可以编写一些额外的操作来强化为线性表，底层依然采用顺序存储实现的线性表，称为顺序表

操作

创建

//在Java10中，最好用此方法，避免重复写类名
var staff = new ArrayList<Employee>();
//可以省略右边的类型参数
ArrayList<Employee> staff = new ArrayList<>();

常见操作

staff.add(new Employee(“”,…);
//如果已经能够估计出可能存储的数量大小，这样前100次add调用，就不会带来开销很大的重新分配内存
staff.ensureCapacity(100);
//可以传初试容量
ArrayList<Employee> staff = new ArrayList<>(100);
//求大小
staff.size();
//设置第i 个元素
staff.set(i, Harry);
//转换为数组
x = new X[list.size()];
list.toArray(x);
//删除第n个元素
staff.remove(n);

一旦确认数组列表大小恒定，不再发生变化，可以调用此方法，将内存块的大小调整至保存当前元素数量所需要的存储空间

staff.trimToSize();

注意：数组列表的容量和数组大小有重要区别，容量为100的数组列表只是可能保存100个元素，但是在一开始，并不包含任何元素

代码实现

创建类型

先定义一个新的类型

public class ArrayList<E> {
    int capacity = 10; //顺序表的最大容量
    int size = 0; //当前已经存放的元素数量
    private Object[] array = new Object[capacity]; //底层存放的数组
}

【Java数据结构】顺序表、队列、栈、链表、哈希表

由此可见，顺序表是紧凑的，不能出现空位

插入

但是这样少了条件限制，也就是容量的问题，范围只是[0,size]，所以需要判断

public void add(E element, int index) {
    if(index<0 || index>size)
        throw new IndexOutOfBoundsException("invalid, size:0~"+size);
    for(int i=size; i>index; i--) {
        array[i] = array[i-1];
    }
    array[index] = element;
    size++;
}

public static void main(String[] args) {
    ArrayList<Integer> list = new ArrayList<>();
    list.add(10,1); //是一个可以得到异常的函数
}

此时此刻，就很成功的报错了
【Java数据结构】顺序表、队列、栈、链表、哈希表

完善 - 扩容

我们可以让我们的操作更加完美，比如，扩容

public void add(E element, int index) {
    if(index<0 || index>size)
        throw new IndexOutOfBoundsException("invalid, size:0~"+size);
    if(capacity == size) {
        int newCapacity = capacity +(capacity >> 1);
        Object[] newArray = new Object[newCapacity];
        System.arraycopy(array, 0, newArray, 0, size);
        array = newArray;
        capacity = newCapacity;
    }
    for(int i=size; i>index; i--) {
        array[i] = array[i-1];
    }
    array[index] = element;
    size++;
}

打印

public String toString() {
    StringBulider bulider = new StringBuilder();
    for(int i=0; i<size; i++) {
        builder.append(array[i].append(" "));
        return builder.toString();
    }
}

删除

@SuppressWarnings("unchecked")
public E remove(int index){
    if(index < 0 || index > size - 1)
        throw new IndexOutOfBoundsException("删除位置非法，合法的插入位置为：0 ~ "+(size - 1));
    E e = (E) array[index];
    for (int i = index; i < size; i++)
        array[i] = array[i + 1];
    size--;
    return e;
}

获取

public E get(int index) {
if(index<0 || index>(size-1)) 
	throw new IndexOutOfBoundsException("invalid: position 0~" +(size-1));
return (E) array[index];
}

public int size() {
	return size;
}

链表

链表通过指针来连接各个分散的结点，形成链状的结构，不需要申请连续的空间，逻辑依然是每个元素相连

链表分带头结点的和不带头结点的

带头结点的就是不存放数据，一般设计都会采用带头结点的

设置

public class LinkedList<E> {
    private final Node<E> head = new Node<>(null);
	private int size = 0;

	private static class Node<E> {
   		E element;
    	Node<E> next;
    	public Node(E element) {
        	this.element = element;
    	}
	}
}

插入

考虑的点：插入位置是否合法

public void add(E element, int index){
    if(index < 0 || index > size)
        throw new IndexOutOfBoundsException("插入位置非法，合法的插入位置为：0 ~ "+size);
    Node<E> prev = head;
    for (int i = 0; i < index; i++)
        prev = prev.next;
    Node<E> node = new Node<>(element);
    node.next = prev.next;
    prev.next = node;
    size++;
}

重写 toString() 

@Override
public String toString() {
	StringBuilder builder = new StringBuilder();
    Node<E> node = head.next;
    while(node != null) {
        bulider.append(node.element).append(" ");
        node = node.next;
    }
    return builder.toString();
}

删除

public E remove(int index) {
    if(index<0 || index>size-1) {
        throw new IndexOutOfBoundsException("invalid,position: 0~" + (size - 1));
    }
    Node<E> prev = head;
    for(int i=0; i<index; i++) {
        prev = prev.next;
    }
    E e = prev.next.element;
    size--;
    return e;
}

获取对应位置上的元素

public E get(int index) {
    if(index<0 || index>size-1) {
        throw new IndexOutOfBoundsException("invalid position:0~" + (size-1));
    }
    Node<E> node = head;
    while(index-- >= 0) {
        node = node.next;
    }
    return node.element;
}

public int size() {
    return size;
}

总结

链表在随机访问数据的时候，需要通过遍历来完成，而顺序表则利用数组的特性可以直接访问得到，当我们读取数据多于插入删除操作的时候，使用顺序表会更好；顺序表在进行插入删除操作的时候，因为需要移动后续元素，会很浪费时间，链表则不需要，只需要修改结点的指向就行了。所以在进行频繁的插入删除操作的时候，使用链表必然是更好的

栈-先进后出

**FILO: First in, Last out **

是一种特殊的线性表，只能在表尾进行插入删除操作；有点像堆积木，最后堆上去的往往是最先拿下来的

底部称为栈底，顶部称为栈顶；所有的操作只能在栈顶进行

栈可以使用顺序表实现，也可以使用链表实现，使用链表会更加方便。直接将头结点指向栈顶结点，而栈顶结点连接后续的栈内结点

链表实现

类

public class LinkedStack<E> {
    private final Node<E> head = new Node<>(null);
    private static class Node<E> {
        E element;
        Node<E> next;
        public Node(E element) {
            this.element = element;
        }
    }
}

入栈操作

public pop() {
    if(head.next == null) {
        throw new NoSuchElementException("Stack is empty");
    }
    E e = head.next.element;
    return e;
}

测试

public static void main(String[] args) {
    LinkedStack<String> stack = new LinkedStack<>();
    stack.push("AAA");
    stack.push("BBB");
    stack.push("CCC");
    System.out.println(stack.pop());
    System.out.println(stack.pop());
    System.out.println(stack.pop());
}

队列

FIFO First in First out

类似于在超市买东西，先进先出
队列有队头和队首
实现方式：链表、顺序表
利用链表则不需要考虑容量的问题，我们需要同时保存队首和队尾两个指针

创建队列

public class LinkedQueue<E> {
	private final Node <E> head = new Node<>(null);
//入队操作
	public void offer(E element) {
		Node<E> last = head;
		while(last.next != null) {
			last = last.next;
		}
		last.next = new Node<>(element);
	}
//出队操作
	public E pull() {
		if(head.next == null) 
			throw new NoSuchElementException(“Queue is empty”);
		E e = head.next.element;
		head.next = head.next.next;
		return e;
	}

	private static class Node<E> {
		E element;
		Node<E> next;
		public Node(E element) {
			this.element = element;
		}
}

使用

public static void main(String[] Args) {
	LinkedQueue<String> stack = new LinkedQueue<>();
	stack.offer(“AAA”);
	stack.offer(“BBB”);
	stack.offer(“CCC”);
	System.out.println(stack.pull());
	System.out.println(stack.pull());
	System.out.println(stack.pull());

哈希表

散列（Hashing)通过散列函数（哈希函数）将要参与检索的数据与散列值（哈希值）关联，生成一种便于搜索的数据结构，称其为散列表（哈希表）

我们需要将一堆数据保存起来，这些数据会通过哈希函数进行计算，得到与其对应的哈希值，下次需要查找的时候，只需要再次计算哈希值就行了

哈希函数在现实生活中应用十分广泛，目前应用最广泛的是SHA-1、MD5；比如我们下载的IDEA，她的校验文件，就是安装包文件通过哈希算法计算得到的

我们可以将这些元素保存到哈希表，保存的位置与其对应的哈希值有关，哈希值是通过哈希函数计算得到的，我们只需要将对应元素的key提供给哈希函数就可以进行计算了。一般比较简单的哈希函数就是取模操作。哈希表长度（最好是素数）多少，模就是多少

保存到数据是无序的，我们并不清楚计算完哈希值之后会被放到那个位置，哈希表在查找时只需要进行一次哈希函数计算就能直接找到对应元素的存储位置，效率极高

实现简单的哈希表和哈希函数，通过哈希表，可以将数据的查找时间复杂度提升到常数阶

public class HashTable<E> {
    private final int TABLE_SIZE = 10;
    private final Object[] TABLE = new Object[TABLE_SIZE];
    
    public void insert(E element) {
        int index = hash(element);
        TABLE[index] = element;
    }
    
    public boolean contains(E element) {
        int index = hash(element);
        return TABLE[index] == element;
    }
    
    private int hash(Object object) {
        int hashCode = object.hashCode(); //每一个对象都有一个独一无二的哈希值，可以通过hashCode方法得到，只有极小概率会重复
        return hashCode % TABLE_SIZE;
    }
}

会出现哈希碰撞的情况，也就是不同的元素计算出来的哈希值是一样的，这种情况是不可避免的，我们只能通过使用更加高级的哈希函数来尽可能避免这种情况

常见的哈希冲突解决方案是链地址法 ，当出现哈希冲突的时候，我们依然将其保存在对应的位置上，可以将其连接为一个链表的形式

【Java数据结构】顺序表、队列、栈、链表、哈希表

当元素太多的时候，我们一般将其横过来看
【Java数据结构】顺序表、队列、栈、链表、哈希表

但是当链表变得很长的时候，查找效率也就会变得很低下，所以我们可以考虑在链表长度达到一定值的时候，使用其他数据结构，例如平衡二叉树、红黑树，这样就可以一定程度上缓解查找的压力文章来源地址https://www.toymoban.com/news/detail-433725.html

public class HashTable<E> {
    private final int TABLE_SIZE = 10;
    private final Node<E>[] TABLE = new Node[TABLE_SIZE];
    
    public HashTable() {
        for(int i=0; i<TABLE_SIZE; i++) {
            TABLE[i] = new Node<>(null);
        }
    }
    
    public void insert(E element) {
        int index = hash(element);
        Node<E> prev = TABLE[index];
        while(prev.next != null) {
            prev = prev.next;
        }
        prev.next = new Node<>(element);
    }
    
    public boolean contains(E element) {
        int index = hash(element);
        Node<E> node = TABLE[index].next;
        while(node != null) {
            if(node.element == element) 
                return true;
            node = node.next;
        }
        return false;
    }
    
    private int hash(Object object) {
        int hashCode = object.hashCode();
        return hashCode % TABLE_SIZE;
    }
    
    private static class Node<E> {
        private final E element;
        private Node<E> next;
        
        private Node(E element) {
            this.element = element;
        }
    }
}

到了这里，关于【Java数据结构】顺序表、队列、栈、链表、哈希表的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • Java常见的数据结构：栈、队列、数组、链表、二叉树、二叉查找树、平衡二叉树、红黑树

    Java常见的数据结构：栈、队列、数组、链表、二叉树、二叉查找树、平衡二叉树、红黑树

    数据结构是计算机底层存储、组织数据的方式。是指数据相互之间是以什么方式排列在一起的。 通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率 栈 队列 数组 链表 二叉树 二叉查找树 平衡二叉树 红黑树... 后进先出，先进后出 数据进入栈模型的过程称为

    2024年02月07日
    浏览(45)
  • 数据结构---顺序表，链表

    数据结构---顺序表，链表

    目录 前言 线性表 线性表的概念 顺序表 顺序表的概念 顺序表的结构 接口实现 相关面试题分析 顺序表的问题及思考 链表 链表的概念及结构 链表的分类 单链表的实现  接口实现  链表面试题 双向链表 顺序表和链表的区别         这篇文章主要讲顺序表和链表，有几点需要

    2024年02月16日
    浏览(35)
  • 【数据结构】顺序队列模拟实现

    【数据结构】顺序队列模拟实现

    💐 🌸 🌷 🍀 🌹 🌻 🌺 🍁 🍃 🍂 🌿 🍄🍝 🍛 🍤 📃 个人主页 ：阿然成长日记 👈点击可跳转 📆 个人专栏： 🔹数据结构与算法🔹C语言进阶 🚩 不能则学，不知则问，耻于问人，决无长进 🍭 🍯 🍎 🍏 🍊 🍋 🍒 🍇 🍉 🍓 🍑 🍈 🍌 🍐 🍍 一、队列的基本概念

    2024年02月10日
    浏览(40)
  • 【数据结构】顺序表和链表

    【数据结构】顺序表和链表

    线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使 用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串... 线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的， 线性表在物理上

    2024年01月20日
    浏览(68)
  • 九、数据结构——顺序队列中的循环队列

    九、数据结构——顺序队列中的循环队列

    一、循环队列的定义 二、循环队列的实现 三、循环队列的基本操作 ①初始化 ②判空 ③判满 ④入队 ⑤出队 ⑥获取长度 ⑦打印 四、循环队列的应用 五、全部代码 在数据结构中，队列（Queue）是一种常见的线性数据结构，遵循先进先出（First In First Out，FIFO）的原则。循环队

    2024年02月15日
    浏览(49)

  • 数据结构队列例题一顺序实现

    仅供个人复习使用

    2024年02月06日
    浏览(44)
  • 数据结构01-线性结构-链表栈队列-队列篇

    数据结构01-线性结构-链表栈队列-队列篇

    本系列为C++数据结构系列，会介绍 线性结构，简单树，特殊树，简单图等。本文为线性结构部分。 线性结构 【 3 】链表：单链表、双向链表、循环链表 【 3 】栈 【 3 】队列 队列（Queue）与栈一样，是一种线性存储结构，它具有如下特点： （1）队列中的数据元素遵循“先进

    2024年02月16日
    浏览(40)
  • 数据结构2：顺序表和链表

    数据结构2：顺序表和链表

    目录 1.线性表 2.顺序表 2.1概念及结构 2.2接口实现 2.3数据相关面试题 2.4顺序表的问题及思考 3.链表 3.1链表的概念及结构 3.2链表的分类 3.3链表的实现 3.4链表面试题 3.5双向链表的实现 4.顺序表和链表的区别 线性表（linear list）是具有相同特征的数据元素的有限序列。线性表是

    2023年04月17日
    浏览(50)
  • 数据结构（二）----线性表（顺序表，链表）

    数据结构（二）----线性表（顺序表，链表）

    目录 1.线性表的概念 2.线性表的基本操作 3.存储线性表的方式 （1）顺序表 •顺序表的概念 •顺序表的实现 静态分配： 动态分配： 顺序表的插入： 顺序表的删除： 顺序表的按位查找： 顺序表的按值查找： 顺序表的特点： （2）单链表 •单链表的实现 不带头结点的单链表

    2024年04月16日
    浏览(57)
  • 《数据结构》实验报告二：顺序表 链表

    《数据结构》实验报告二：顺序表 链表

    1、掌握线性表中元素的 前驱、后续 的概念。 2、掌握顺序表与链表的 建立 、 插入 元素、 删除 表中某元素的算法。 3、对线性表相应算法的 时间复杂度 进行分析。 4、理解顺序表、链表数据结构的特点（ 优缺点 ）。 说明以下概念 1、线性表：         具有 相同特性 的数

    2024年02月08日
    浏览(43)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包