ArrayList和LinkedList

发表时间:2017-05-09 12:43:54 浏览量( 20 ) 留言数( 0 )

学习目标:

1、了解Java的历史

2、为什么要学习Java语言

3、端正学习态度


学习过程:

一、集合框架介绍

集合框架有一个共有的接口Collection,集合对象就是将多个元素组成一个单元的对象,集合数据的一般操作就是用于存储、检索、删除和修改等操作。集合框架是用于表示和操纵集合的统一体系结构。

java集合框架的优点:

  • 提供有用的数据结构和算法,从而减少编程工作

  • 提高了程序速度和质量,因为它提供了高性能的数据结构和算法

  • 允许不同 API 之间的互操作,API之间可以来回传递集合

  • 可以方便地扩展或改写集合

java集合框架提供了四种容器可以选择使用,分别是Queue、List、Set和Map。为了该框架的高效/规范和易于扩展性,集合框架被设计成一组层次分明的标准化接口与实现,接口图如下:

attcontent/5113dc29-780a-4abc-b079-adbece738101.png

二、ArrayList

List表示的是一种有序的对象容器数据结构,java中使用List接口来规定这类数据结构。List接口实现了Collection

ArrayList和我们之前介绍的数组有很多的优势,ArrayList的特点总结如下:

  • ArrayList 对象是长度可变的对象引用数组,类似于动态数组

  • 继承 AbstractList 并实现 List 接口,方法统一

  • 动态扩展,随着元素的添加,元素的数目会增加,列表也会随着扩展

  • 访问和遍历对象时,它提供更好的性能

三、常用方法举例

对ArrayList的常用方法,无非就是添加、删除数据,和访问数据,这里就不做太多论述了,你可以阅读以下下面的的代码:

 package com;

import java.util.ArrayList;

import com.pojo.Student;

public class ArrayListStr {
	
	public static void main(String[] args) {
		//线性结构  在这里你可以和数组对比一下
		int nums[]={1,3,4,4};
		System.out.println(nums[3]);
		
		//初始化三个学生对象。
		Student stu1=new Student();
		stu1.setAge(23);
		stu1.setName("张三1");
		
		Student stu2=new Student();
		stu2.setAge(24);
		stu2.setName("张三2");
		
		Student stu3=new Student();
		stu3.setAge(25);
		stu3.setName("张三3");
		
		//定义一个ArrayList对象,
		ArrayList stus=new ArrayList();
		//把三个学生对象添加到一个ArrayList对象中
		stus.add(stu1);
		stus.add(stu2);
		stus.add(stu3);
		//也可以添加一个字符串对象
		stus.add("1234");
		
		System.out.println(stus.size());//ArrayList大小
		System.out.println(stus.isEmpty());//判断是否为空
		System.out.println(stus.contains(stu2));//是否包含某个对象
		

                //访问  随机访问
		Student temp=(Student)stus.get(2);	
		System.out.println(temp.getName());
		
		//动态添加
		Student stu4=new Student();
		stu4.setAge(25);
		stu4.setName("张三4");
		stus.add(stu4);
		//删除
		stus.remove(stu2);

		
		//顺序访问  访问全部
		for(int i=0;i<stus.size();i++){
			Object object=stus.get(i);
			//以后会使用泛型优化,现在最好先判断
			if(object instanceof Student){
				Student stu=(Student)object;
				System.out.println(stu.getName());
			}	
		}
		
	        //转换为数组。
		Student [] stuarray=(Student [])stus.toArray();
		
	}

}


四、linkedlist介绍

LinkedList实现了链表的数据结构,链式结构使得LinkedList相对于顺序结构的ArrayList来说,在列表中插入数据或删除数据时效率更高。它实现了List接口并继承于AbstractSequentialList。构造方法如下:

LinkedList();               //创建默认的空链表

LinkedList(Collection c);    //创建链表,将现有集合c放入链表

由于都是实现List接口,所以和ArrayList的很多方法都是一致,其实现虽然完全不同,不过方法的调用和含义是一致的,所以这里我们就介绍几个ArrayList所不同的方法:

void addFirst(Object obj);    //在头部添加数据

void addLast(Object obj);    //在尾部添加数据

void add(int index,Object obj);    //指定位置添加数据

Object getFirst( );          //从头部读取数据

Object getLast( );           //从尾部读取数据

Object removeFirst( );       //从头部移除数据

Object removeLast( );        //从尾部移除数据

五、常用方法举例

  package com.stu;

import java.util.LinkedList;
import java.util.Vector;

import com.pojo.Student;

public class LinkedListStu {
	
	public static void main(String[] args) {
		LinkedList linkedList=new LinkedList();
	
		Student stu1=new Student();
		stu1.setName("张三1");
		linkedList.add(stu1);
		
		Student stu2=new Student();
		stu2.setName("张三2");
		
		Student stu3=new Student();
		stu3.setName("张三3");
		
		linkedList.add(stu3);//默认添加到末尾
		
		linkedList.remove(stu3);
		
		System.out.println("大小:"+linkedList.size());
		System.out.println("是否为空:"+linkedList.isEmpty());
		System.out.println("是否包含:"+linkedList.contains(stu2));
		
		System.out.println(linkedList.get(2));
		
		//linkedList比较特有的方法
		linkedList.add(0, stu2);//指定位置添加
		linkedList.removeFirst();
		linkedList.removeLast();
		linkedList.addFirst(stu1);
		linkedList.addLast(stu3);
		
		for(int i=0;i<linkedList.size();i++){
			Object object=linkedList.get(i);
			if(object instanceof Student){
				Student stu=(Student)object;
				System.out.println(stu.getName());
			}
		}
		
		
	}

}

六、ArrayList和LinkList的区别

ArrayList和LinkList的区别实际上就是数据结构中顺序表和链表直接的区别。


顺序表的特点是逻辑上相邻的数据元素,物理存储位置也相邻,ArrayList的存储空间需要预先分配,并在运行中可以动态在扩充,它的优点是: 

  1. 节省空间,不用为表示节点间的逻辑关系而增加额外的存储开销。

  2. 随机访问速度高,顺序表具有按元素序号随机访问。

 缺点: 

  1. 在顺序表中做插入、删除操作时,平均移动表中的一半元素,因此对较大的顺序表效率低。 

  2. 需要预先分配足够大的存储空间,估计过大,可能会导致顺序表后部大量闲置;预先分配过小,又会造成溢出。

在链表中逻辑上相邻的数据元素,物理存储位置不一定相邻,它使用指针实现元素之间的逻辑关系。并且,链表的存储空间是动态分配的。LinkList采用双向链表的方式实现,它的最大特点是:

  1. 插入、删除运算方便。

  2. 不需要预先分布连续的存储空间。

缺点:

  1. 要占用额外的存储空间存储元素之间的关系,存储密度降低。

  2. 链表不是一种随机存储结构,不能随机存取元素。

可见ArrayList和LinkList的优缺点是互补的,要看实际的应用需要来决定使用哪一种存储方式,例如,要经常查找线性表中的第i个元素,对于顺序表可以直接计算出a(i)的的地址,不用去查找,其时间复杂度为0(1).而链表必须从链表头开始,依次向后查找,平均需要0(n)的时间。所以,如果经常做的运算是按序号访问数据元素,显然顺表优于链表。反之,如果经常需要增删数据的,那么在顺序表中平均移动表中一半的元素,当数据元素的信息量较大而且表比较长时,而在链表中作插入、删除,虽然要找插入位置,但是不需要移动数据,所以LinkList又比ArrayList效率要高。