龙空技术网

《一起学习java和数据结构》系列-数组和链表

方木 111

前言:

此时朋友们对“java删除数组的元素和元素”大致比较着重,各位老铁们都想要分析一些“java删除数组的元素和元素”的相关知识。那么小编在网摘上搜集了一些有关“java删除数组的元素和元素””的相关文章,希望兄弟们能喜欢,姐妹们快快来学习一下吧!

数组

数组是一个线性表数据结构。它用一段连续的内存地址空间,来存储一些相同类型的数据。 从上面的定义,我们不难看出几个关键词。

线性表:顾名思义,线性表就是数据排列成一条线的数据结构。每一个线性表只有前后两个方向。队列、链表、数组、栈都是线性表结构。

连续的内存空间和相同类型的数据:正是因为有了这两个限制,才使数组有了,可以根据数组的下标随机访问的特性。但是也因为连续的内存空间的限制,导致数组在进行删除和插入操作的时候,非常的低效。

如何进行数组的随机访问?

首先我们定义一个数组是,例如: int[]a=newint[10],当我们定义的时候,计算机会给数组a[]分配一块连续的内存地址。当我通过数组下标去访问时,计算机会通过寻址公式 a[i]_address=base_address+i*data_type_size计算出数据在内存中的地址,进行访问。其中,baseaddress是内存首地址,datatypesize表示数组每个元素的大小。比如:啊a[]是int类型,所以datatype_size,就是4个字节。

数组的插入和删除

为了保证数组的连续内存空间性,在对中间的元素进行插入和删除的时候,需要将数组中其他元素移动位置。这样的做法会浪费一些性能,与链表的插入和删除相比,十分低效。

在一个有序的数组中,往下标为3的位置插入元素,需要将下标4到末尾的数据整体向后挪移。如果在一个无序的数组中,往下标为3的位置插入元素,最好的办法是将下标为3的元素放到数组的末尾,再将元素插入,减少元素挪到带来的性能损耗。

和插入类似,删除数组中的一个元素,为了保证内存空间的连续性,需要进行数据的挪移。我们也可以记录下每次删除的元素,但不真正的去删除挪移元素,到数组已经满了以后,再进行一次进行数据的删除挪移。这样可以大大减少元素搬移带来的性能消耗。有点像垃圾回收机制。

数组和容器

在JAVA中提供了数组的类型的容器,比如:ArrayList。那么数组和ArrayList有哪些优缺点呢?

ArrayList最大的优点是将数组的插入、删除和查询等一些操作进行了封装,在使用的时候不需要考虑元素的搬移。另一个比较大的优点是,ArrayList支持动态扩容。由于在数组在定义的时候,计算机需要根据数组的大小分配一块连续的内存空间,所以需要提前定义数组的大小。ArrayList在底层进行了自动扩容实现,当元素大于ArrayList大小时,它会将空间扩大到1.5倍大小,然后将数据复制到新的数组。

链表

链表是一种物理存储单元上非连续、非顺序的存储结构,不需要一块连续的内存空间,他通过链表的指针有次序的将零散的内存空间连接。最常见的链表结构有:单链表、双向链表和循环链表。

单链表

单链表顾名思义,它的链表方向是单向的,对于链表的访问只能从头部开始,这也导致了链表的查询效率低下。

上图是一个单向链表,它有两个结点比较特殊,一个是第一个结点,叫头结点,用来记录链表的基结点;另一个是最后一个结点,叫尾结点,它比较特殊,并不是指向下一个结点,而是指向一个NULL地址。

插入和删除

从上面数组我们知道,由于内存空间连续的限制,元素删除和插入需要数据搬移。但是链表的内存空间不需要连续,所以它的插入和删除操作十分的高效。

对于链表的查询,我们只需要相邻结点的指针变化。

上图是一个单向链表的删除过程,从图上我们可以知道,将链表中的元素删除,将这个元素删除,然后,在将前结点的Next指针,指向它的后结点就OK了,十分的高效。插入操作也是类似,将前结点的Next指针指向,插入的元素,将插入的指针,指向它。

循环链表

循环链表是一种特殊的单链表。它与单链表的唯一区别是,尾结点的Next指针不是指向一个Null地址,而是,指向了链表的头结点,形成了一个闭环,达到了循环的目的。其实确切的说这是一种单向循环链表。

双向链表

与上面的单链表不同,双向链表元素之间是双向的,表现形式也比单链表复杂一点。它的每一个结点不止有后继指针Next,还有一个前驱指针Pre。从这一点可知,一个双向链表的结点比单向链表多一个前驱指针,这也意味着它的每一个结点需要更多的空间去存储前驱指针。

插入和删除操作与单向链表类似,只需要处理好前驱指针和后继指针的指向。

单链表和双向链表对比

我们知道,单向链表想要删除一个元素,需要从头部开始查询直到找到该元素,然后进行删除,指针从新指向,在这一点上双向链表和单向链表是一致的。但是我们如果想要删除一个元素的前驱结点,单向链表因为没有前驱指针,需要再从头遍历,消耗时间,双向链表就可以直接找到前驱结点,并删除。

其实这是一种空间换时间的思路。使用了双向链表占用了多的空间,节约了时间。这种在我们内存足够的情况下,优化算法的执行时间有很好的的帮助。

数组与链表的对比

由于内存空间连续性的不同,链表适合插入、删除操作,而数组则更加适合根据下标的查询。

本文是数据结构和算法学习的开篇文章,希望大家可以和我一起学习成长,早日找到自己想要的生活。

我是方褚,一个努力成长的程序员。

标签: #java删除数组的元素和元素