数据结构中的线性表,对应着Collection中的List接口。
在本节中,我们将做以下三件事
第一。我们先来看看线性表的特征
第二,自己用JAVA实现List
第三,对比的线性表、链式表性能,以及自己的List性能与JDKList性能对比
线性表特征:
第一,一个特定的线性表,应该是用来存放特定的某一个类型的元素的(元素的“同一性”)
第二, 除第一个元素外,其他每一个元素有且仅有一个直接前驱;除最后一个元素外,其他每一个元素有且仅有一个 直接后继(元素的“序偶性”)
第二, 元素在线性表中的“下标”唯一地确定该元素在表中的相对位置(元素的“索引性”)
又,一.线性表只是数据的一种逻辑结构,其具体存储结构可以为顺序存储结构和链式储存结构来完成,对应可以得到顺序表和链表,
二.对线性表的入表和出表顺序做一定的限定,可以得到特殊的线性表,栈(FILO)和队列(FIFO)
自己实现线性表之顺序表
思路:
1. 顺序表因为采用顺序存储形式,所以内部使用数组来存储数据
2.因为存储的具体对象类型不一定,所以采用泛型操作
3.数组操作优点:1.通过指针快速定位到下表,查询快速
缺点:1.数组声明时即需要确定数组大小。当操作中超过容量时,则需要重新声明数组,并且复制当前所有数据
2.当需要在中间进行插入或者删除时,则需要移动大量元素(size-index个)
具体实现代码如下
/**
* 自己用数组实现的线性表
*/
public class ArrayList<E> {
Object[] data = null;// 用来保存此队列中内容的数组
int current;// 保存当前为第几个元素的指标
int capacity;// 表示数组大小的指标
/**
* 如果初始化时,未声明大小,则默认为10
*/
public ArrayList() {
this(10);
}
/**
* 初始化线性表,并且声明保存内容的数组大小
* @param initalSize
*/
public ArrayList(int initalSize) {
if (initalSize < 0) {
throw new RuntimeException("数组大小错误:" + initalSize);
} else {
this.data = new Object[initalSize];
this.current = 0;
capacity = initalSize;
}
}
/**
* 添加元素的方法 添加前,先确认是否已经满了
* @param e
* @return
*/
public boolean add(E e) {
ensureCapacity(current);// 确认容量
this.data[current] = e;
current++;
return true;
}
/**
* 确认系统当前容量是否满足需要,如果满足,则不执行操作 如果不满足,增加容量
* @param cur 当前个数
*/
private void ensureCapacity(int cur) {
if (cur == capacity) {
// 如果达到容量极限,增加10的容量,复制当前数组
this.capacity = this.capacity + 10;
Object[] newdata = new Object[capacity];
for (int i = 0; i < cur; i++) {
newdata[i] = this.data[i];
}
this.data = newdata;
}
}
/**
* 得到指定下标的数据
* @param index
* @return
*/
public E get(int index) {
validateIndex(index);
return (E) this.data[index];
}
/**
* 返回当前队列大小
* @return
*/
public int size() {
return this.current;
}
/**
* 更改指定下标元素的数据为e
* @param index
* @param e
* @return
*/
public boolean set(int index, E e) {
validateIndex(index);
this.data[index] = e;
return true;
}
/**
* 验证当前下标是否合法,如果不合法,抛出运行时异常
* @param index 下标
*/
private void validateIndex(int index) {
if (index < 0 || index > current) {
throw new RuntimeException("数组index错误:" + index);
}
}
/**
* 在指定下标位置处插入数据e
* @param index 下标
* @param e 需要插入的数据
* @return
*/
public boolean insert(int index, E e) {
validateIndex(index);
Object[] tem = new Object[capacity];// 用一个临时数组作为备份
//开始备份数组
for (int i = 0; i < current; i++) {
if (i < index) {
tem[i] = this.data[i];
}else if(i==index){
tem[i]=e;
}else if(i>index){
tem[i]=this.data[i-1];
}
}
this.data=tem;
return true;
}
/**
* 删除指定下标出的数据
* @param index
* @return
*/
public boolean delete(int index){
validateIndex(index);
Object[] tem = new Object[capacity];// 用一个临时数组作为备份
//开始备份数组
for (int i = 0; i < current; i++) {
if (i < index) {
tem[i] = this.data[i];
}else if(i==index){
tem[i]=this.data[i+1];
}else if(i>index){
tem[i]=this.data[i+1];
}
}
this.data=tem;
return true;
}
}
自己实现线性表之链表
思路:1.链表采用链式存储结构,在内部只需要将一个一个结点链接起来。(每个结点中有关于此结点下一个结点的引用)
链表操作优点:1.,因为每个结点记录下个结点的引用,则在进行插入和删除操作时,只需要改变对应下标下结点的引用即可
缺点:1.要得到某个下标的数据,不能通过下标直接得到,需要遍历整个链表。
实现代码如下
/**
* 自己用链式存储实现的线性表
*/
public class LinkedList<E> {
private Node<E> header = null;// 头结点
int size = 0;// 表示数组大小的指标
public LinkedList() {
this.header = new Node<E>();
}
public boolean add(E e) {
if (size == 0) {
header.e = e;
} else {
// 根据需要添加的内容,封装为结点
Node<E> newNode = new Node<E>(e);
// 得到当前最后一个结点
Node<E> last = getNode(size-1);
// 在最后一个结点后加上新结点
last.addNext(newNode);
}
size++;// 当前大小自增加1
return true;
}
public boolean insert(int index, E e) {
Node<E> newNode = new Node<E>(e);
// 得到第N个结点
Node<E> cNode = getNode(index);
newNode.next = cNode.next;
cNode.next = newNode;
size++;
return true;
}
/**
* 遍历当前链表,取得当前索引对应的元素
*
* @return
*/
private Node<E> getNode(int index) {
// 先判断索引正确性
if (index > size || index < 0) {
throw new RuntimeException("索引值有错:" + index);
}
Node<E> tem = new Node<E>();
tem = header;
int count = 0;
while (count != index) {
tem = tem.next;
count++;
}
return tem;
}
/**
* 根据索引,取得该索引下的数据
*
* @param index
* @return
*/
public E get(int index) {
// 先判断索引正确性
if (index >= size || index < 0) {
throw new RuntimeException("索引值有错:" + index);
}
Node<E> tem = new Node<E>();
tem = header;
int count = 0;
while (count != index) {
tem = tem.next;
count++;
}
E e = tem.e;
return e;
}
public int size() {
return size;
}
/**
* 设置第N个结点的值
*
* @param x
* @param e
* @return
*/
public boolean set(int index, E e) {
// 先判断索引正确性
if (index > size || index < 0) {
throw new RuntimeException("索引值有错:" + index);
}
Node<E> newNode = new Node<E>(e);
// 得到第x个结点
Node<E> cNode = getNode(index);
cNode.e = e;
return true;
}
/**
* 用来存放数据的结点型内部类
*/
class Node<e> {
private E e;// 结点中存放的数据
Node() {
}
Node(E e) {
this.e = e;
}
Node<E> next;// 用来指向该结点的下一个结点
// 在此结点后加一个结点
void addNext(Node<E> node) {
next = node;
}
}
}
自己实现线性表之栈
栈是限定仅允许在表的同一端(通常为“表尾”)进行插入或删除操作的线性表。
允许插入和删除的一端称为栈顶(top),另一端称为栈底(base)
特点:后进先出 (LIFO)或,先进后出(FILO)
因为栈是限定线的线性表,所以,我们可以调用前面两种线性表,只需要对出栈和入栈操作进行设定即可
具体实现代码
/**
* 自己用数组实现的栈
*/
public class ArrayStack<E> {
private ArrayList<E> list=new ArrayList<E>();//用来保存数据线性表
private int size;//表示当前栈元素个数
/**
* 入栈操作
* @param e
*/
public void push(E e){
list.add(e);
size++;
}
/**
* 出栈操作
* @return
*/
public E pop(){
E e= list.get(size-1);
size--;
return e;
}
}
至于用链表实现栈,则只需要把保存数据的顺序表改成链表即可,此处就不给出代码了
自己实现线性表之队列
与栈类似
队列是只允许在表的一端进行插入,而在另一端删除元素的线性表。
在队列中,允许插入的一端叫队尾(rear),允许删除的一端称为队头(front)。
特点:先进先出 (FIFO)、后进后出 (LILO)
同理,我们也可以调用前面两种线性表,只需要对队列的入队和出队方式进行处理即可
package cn.javamzd.collection.List;
/**
* 用数组实现的队列
*/
public class ArrayQueue<E> {
private ArrayList<E> list = new ArrayList<E>();// 用来保存数据的队列
private int size;// 表示当前栈元素个数
/**
* 入队
* @param e
*/
public void EnQueue(E e) {
list.add(e);
size++;
}
/**
* 出队
* @return
*/
public E DeQueue() {
if (size > 0) {
E e = list.get(0);
list.delete(0);
return e;
}else{
throw new RuntimeException("已经到达队列顶部");
}
}
}
对比线性表和链式表
前面已经说过顺序表和链式表各自的特点,这里在重申一遍
数组操作优点:1.通过指针快速定位到下标,查询快速
缺点:1.数组声明时即需要确定数组大小。当操作中超过容量时,则需要重新声明数组,并且复制当前所有数据
2.当需要在中间进行插入或者删除时,则需要移动大量元素(size-index个)
链表操作优点:1.,因为每个结点记录下个结点的引用,则在进行插入和删除操作时,只需要改变对应下标下结点的引用即可
缺点:1.要得到某个下标的数据,不能通过下标直接得到,需要遍历整个链表。
现在,我们通过进行增删改查操作来感受一次其效率的差异
思路:通过两个表,各进行大数据量操作(2W)条数据的操作,记录操作前系统时间,操作后系统时间,得出操作时间
实现代码如下
package cn.javamzd.collection.List;
public class Test {
/**
* @param args
*/
public static void main(String[] args) {
//测试自己实现的ArrayList类和Linkedlist类添加20000个数据所需要的时间
ArrayList<String> al = new ArrayList<String>();
LinkedList<String> ll = new LinkedList<String>();
Long aBeginTime=System.currentTimeMillis();//记录BeginTime
for(int i=0;i<30000;i++){
al.add("now"+i);
}
Long aEndTime=System.currentTimeMillis();//记录EndTime
System.out.println("arrylist add time--->"+(aEndTime-aBeginTime));
Long lBeginTime=System.currentTimeMillis();//记录BeginTime
for(int i=0;i<30000;i++){
ll.add("now"+i);
}
Long lEndTime=System.currentTimeMillis();//记录EndTime
System.out.println("linkedList add time---->"+(lEndTime-lBeginTime));
//测试JDK提供的ArrayList类和LinkedList类添加20000个数据所需要的世界
java.util.ArrayList<String> sal=new java.util.ArrayList<String>();
java.util.LinkedList<String> sll=new java.util.LinkedList<String>();
Long saBeginTime=System.currentTimeMillis();//记录BeginTime
for(int i=0;i<30000;i++){
sal.add("now"+i);
}
Long saEndTime=System.currentTimeMillis();//记录EndTime
System.out.println("JDK arrylist add time--->"+(saEndTime-saBeginTime));
Long slBeginTime=System.currentTimeMillis();//记录BeginTime
for(int i=0;i<30000;i++){
sll.add("now"+i);
}
Long slEndTime=System.currentTimeMillis();//记录EndTime
System.out.println("JDK linkedList add time---->"+(slEndTime-slBeginTime));
}
}
得到测试结果如下:
arrylist add time--->446 linkedList add time---->9767 JDK arrylist add time--->13 JDK linkedList add time---->12 |
由以上数据,我们可知:
1.JDK中的ArrayList何LinkedList在添加数据时的性能,其实几乎是没有差异的
2.我们自己写的List的性能和JDK提供的List的性能还是存在巨大差异的
3.我们使用链表添加操作,花费的时间是巨大的,比ArrayList都大几十倍
第三条显然是跟我们最初的设计不相符的,按照我们最初的设想,链表的添加应该比顺序表更省时
查看我们写的源码,可以发现:
我们每次添加一个数据时,都需要遍历整个表,得到表尾,再在表尾添加,这是很不科学的
现改进如下:设立一个Node<E>类的成员变量end来指示表尾,这样每次添加时,就不需要再重新遍历得到表尾
改进后add()方法如下
public boolean add(E e) {
if (size == 0) {
header.e = e;
} else {
// 根据需要添加的内容,封装为结点
Node<E> newNode = new Node<E>(e);
//在表尾添加元素
last.addNext(newNode);
//将表尾指向当前最后一个元素
last = newNode;
}
size++;// 当前大小自增加1
return true;
}
ArrayList添加的效率和JDK中对比起来也太低
分析原因为:
每次扩大容量时,扩大量太小,需要进行的复制操作太多
现在改进如下:
每次扩大,则扩大容量为当前的三倍,此改进仅需要更改ensureCapacity()方法中的一行代码,此处就不列出了。
改进后,再次运行添加元素测试代码,结果如下:
arrylist add time--->16 linkedList add time---->8 JDK arrylist add time--->7 JDK linkedList add time---->7
|
虽然还有改进的空间,但是显然,我们的效果已经大幅度改进了,而且也比较接近JDK了
接下来测试插入操作的效率
我们只需要将测试代码中的添加方法(add())改成插入方法(insert(int index,E e)),为了使插入次数尽可能多,我们把index都设置为0
测试结果如下:
arrylist inset time--->17 linkedList inset time---->13 JDK arrylist inset time--->503 JDK linkedList inset time---->11
|
多次测试,发现我们写的ArrayList在插入方法的效率都已经超过JDK了,而且也接近LinkedLst了。撒花!!!
接下来测试删除、得到下标等等操作就不一一列出来了(只需要改变每次调用的方法即可)
恩,本来想今晚把所有的集合框架实现都写一下的
但是不知不觉这都又2点了
明早还得去蓝杰上课
果断先睡吧
敬请大家期待我明日大作------------静态/动态查找表的实现,动态查找表查找/加入算法的JAVA实现,Hash表的实现
good night
分享到:
相关推荐
线性表分析及Java实现
线性表的实现:插入,删除等操作
(5)对于普通标识符和常量,分别建立标识符表和常量表(使用线性表存储),当遇到一个标识符或常量时,查找标识符表或常量表,若存在,则返回位置,否则返回0并且填写符号表或常量表。 标识符表结构:变量名,...
算法分析:通过数学方法分析算法的时间复杂度(运行时间随数据规模增长的速度)和空间复杂度(所需内存大小)来评估其效率。 学习算法与数据结构不仅有助于理解程序的内部工作原理,更能帮助开发人员编写出高效、...
线性表,链表,哈希表是常用的数据结构,在进行Java开发时,JDK已经为我们提供了一系列相应的类来实现基本的数据结构。这些类均在java.util包中。本文试图通过简单的描述,向读者阐述各个类的作用以及如何正确使用...
基础的数据结构和算法C、C++、Java实现,有线性表、链表、队列、二叉树、图、查找、排序等等,全是最标准的实现,可以用来学习也可以直接使用。用来学习的话,里边有每种算法一步一步实现的图片,更加清晰。
《数据结构与算法分析:Java语言描述 第2版 》是国外数据结构与算法分析方面的经典教材 使用卓越的Java编程语言作为实现工具讨论了数据结构(组织大量数据的方法)和算法分析(对算法运行时间的估计) 随着计算机速度...
它不是从基于另一种程序设计语言的数据结构教材简单地“改编”而来的,因此在数据结构的实现上更加“地道”地运用了Java语言,并且自始至终强调以面向对象的方式来思考、分析和解决问题。本书是为数据结构入门课程...
它不是从基于另一种程序设计语言的数据结构教材简单地“改编”而来的,因此在数据结构的实现上更加“地道”地运用了Java语言,并且自始至终强调以面向对象的方式来思考、分析和解决问题。本书是为数据结构入门课程...
它不是从基于另一种程序设计语言的数据结构教材简单地“改编”而来的,因此在数据结构的实现上更加“地道”地运用了Java语言,并且自始至终强调以面向对象的方式来思考、分析和解决问题。本书是为数据结构入门课程...
为提供其发挥能力的空间,有效提高其学习兴趣,提出一些要求更高、具有一定挑战性的任务,要求能进行分析、设计并实现、测试,包括:完成比教材里典型基本功能更强的拓展功能,开拓学生的思路,如统计线性表中给定值...
3.能够选择合适的数据结构和方法进行问题求解,具备采用C或C++或 JAVA语言设计与实现算法的能力。 一、线性表 (一)线性表的定义和基本操作 (二)线性表的实现 1.顺序存储结构 2.链式存储结构 3.线性表的应用 二、...
子类不能继承父类中访问权限为private的成员变量和方法,子类可以重写父类的方法,及命名与父类同名的成员变量。 子类通过隐藏父类的成员变量和重写父类的方法,把父类的状态和行为改变为自身的状态和行为。注意:...
1.栈和队列的共同特点是(只允许在端点处插入和删除元素) 4.栈通常采用的两种存储结构是(线性存储结构和链表存储结构) ...6. 算法分析的目的是(分析算法的效率以求改进) ............ .................
数据结构:⼋⼤数据结构分析 数据结构分类 数据结构是指相互之间存在着⼀种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成 。 常⽤的数据结构有:数组,栈,链表,队列,树,图,堆,散列表等,如图所...
9.4.1 线性表的实现分析 9.4.2 线性表的功能 9.5 小结 第10课 栈和队列 10.1 栈 10.1.1 栈的基本定义 10.1.2 栈的常用操作 10.1.3 栈的顺序存储结构及实现 10.1.4 栈的链式存储结构及实现 10.1.5 Java集合...
文章目录栈的应用场景与介绍栈的介绍出入栈的概念(如图所示)栈的应用场景数组模拟栈的思路分析图代码实现栈实现综合计算器要求思路分析代码实现 栈的应用场景与介绍 计算式:7*2*2-5+1-5*3-3=? 计算机底层是如何...
3.1.4 Strategy接口 线性表的顺序存储与实现 线性表的链式存储与实现.42 3.3.1 单链表 3.3.2 双向链表 3.3.3 线性表的单链表实现 两种实现的对比 3.4.1 基于时间的比较 3.4.2 基于空间的比较 链接表.54 ...