一.手写ArrayList
public class ArrayList {
private Object[] elementData; //底层数组
private int size; //数组大小
public int size(){
/*
* 返回数组大小
*/
return size;
}
public ArrayList(){
/*
* 无参构造器，通过显式调用含参构造器
*/
this();
}
public ArrayList(int initialCapacity){
/*
* 1.含参构造器
* 2.要对传入的初始量的合法性进行检测
* 3.通过新建数组实现
*/
if(initialCapacity<){
try {
throw new Exception();
} catch (Exception e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
elementData=new Object[initialCapacity];
}
public boolean isEmpty(){
/*
* 判断是否为空
*/
return size==;
}
public Object get(int index){//获取指定位置的元素
/*
* 1.获取指定下标的对象
* 2.下标合法性检测
*/
rangeCheck(index);
return elementData[index];
}
public boolean add(Object obj){//在末尾添加元素
/*
* 添加对象（不指定位置）
* 注意数组扩容
*/
ensureCapacity();
elementData[size]=obj;
size++;
return true;
}
public void add(int index,Object obj){//在指定位置添加元素
/*
* 插入操作（指定位置）
* 1.下标合法性检查
* 2.数组容量检查、扩容
* 3.数组复制（原数组，开始下标，目的数组，开始下标，长度）
*/
rangeCheck(index);
ensureCapacity();
System.arraycopy(elementData, index, elementData, index+,size-index);
elementData[index]=obj;
size++;
}
public Object remove(int index){//删除指定位置元素
/*
* 1.删除指定下标对象，并返回其值
* 2.下标合法性检测
* 3.通过数组复制实现
* 4.因为前移，数组最后一位要置为空
*/
rangeCheck(index);
int arrnums=size-index-;
Object oldValue=elementData[index];
if(arrnums>){
System.arraycopy(elementData, index+, elementData,index, arrnums);
}
elementData[--size]=null;
return oldValue;
}
public boolean remove(Object obj){//删除指定元素
/*
* 1.删除指定对象
* 2.通过遍历
* 3.equals的底层运用，找到下标，调用remove(int i)
*/
for(int i=;i<size;i++){
if(get(i).equals(obj)){ //注意底层用的是equals不是“==”
remove(i);
}
break;
}
return true;
}
public Object set(int index,Object obj){//修改指定位置的元素
/*
* 1.将指定下标的对象改变
* 2.下标合法性检查
* 3.直接通过数组的赋值来实现改变
* 4.返回旧值
*/
rangeCheck(index);
Object oldValue=elementData[index];
elementData[index]=obj;
return oldValue;
}
private void rangeCheck(int index){
/*
* 对下标的检查
*/
if(index<||index>=size){
try {
throw new Exception();
} catch (Exception e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
}
private void ensureCapacity(){
/*
* 1.对容器容量的检查
* 2.数组扩容，通过数组复制来实现（量和值两者都要保障）
*/
if(size==elementData.length){
Object[] newArray=new Object[size*+];
System.arraycopy(elementData, , newArray, , elementData.length);
elementData=newArray;
}
}
public int indexOf(Object obj) {//查询元素第一次出现的位置
//ArrayList中的元素可以为null，如果为null返回null的下标
if (obj == null) {
for (int i = ; i < size; i++)
if (elementData[i]==null)
return i;
} else {
for (int i = ; i < size; i++)
if (obj.equals(elementData[i]))
return i;
}
//如果没有找到对应的元素返回-1。
return -;
}
public int lastIndexOf(Object obj) {//查询元素最后一次出现的位置
if (obj == null) {
//如果o为null从后往前找到第一个为null的下标
for (int i = size-; i >= ; i--)
if (elementData[i]==null)
return i;
} else {
//从后往前找到第一个值为o的下标
for (int i = size-; i >= ; i--)
if (obj.equals(elementData[i]))
return i;
}
return -;
}
}
二.手写LinkedList
package com.whzc.ywb.study.section03.linkedList;
/**
* 自己实现链表
* @author ywb
*
* @param <E>
*/
public class LinkedList<E> { private class Node{
public E e;//元素
public Node next;//指针
public Node(E e,Node next) {//传入元素和指针
this.e = e;
this.next = next;
}
public Node(){//不传入元素和指针
this(null,null);//this是传入两个参数的构造器
}
public Node(E e){
this(e,null);
} @Override
public String toString() {
return "Node [e=" + e + "]";
}
} private Node dummyHead;
private int size;
public LinkedList(){
dummyHead = new Node(null,null);
size = ;
}
public int getSize(){
return size;
}
public boolean isEmpty(){
return size == ;
}
public void addFirst(E e){//在链表头添加元素
/*Node node = new Node(e);
node.next = head;
head = node;*/ //用下面一行代码代替
//head = new Node(e,head);//括号内的head是之前的链表的头结点，左边的head是现在的头结点
add(,e);
}
public void addLast(E e){//在链表的尾部添加元素
add(size,e);
}
public void add(int index,E e){//在链表中间添加元素
if(index < || index > size){
throw new IllegalArgumentException("索引越界异常");
}
Node prev = dummyHead;//定义一个指针指向头结点
for(int i = ; i < index ; i++){
prev = prev.next;//将这个指针移动到要插入的位置的前一个元素
}
/*Node node = new Node(e);
node.next = prev.next;
prev.next = node;*/ //注意这两行代码的顺序。用下面一行代码实现
prev.next = new Node(e,prev.next);
size ++;
}
public E get(int index){
if(index < || index > size){
throw new IllegalArgumentException("索引越界异常");
}
Node cur = dummyHead.next;
for(int i = ; i < index ; i++){
cur = cur.next;
}
return cur.e;
}
public E getFirst(){
return get();
}
public E getLast(){
return get(size-);
}
public void update(int index,E e){//修改某个元素
if(index < || index > size){
throw new IllegalArgumentException("索引越界异常");
}
Node cur = dummyHead.next;
for(int i = ; i < index ; i++){
cur = cur.next;
}
cur.e = e;
}
public boolean contains(E e){//查询链表中是否存在某个元素
Node node = dummyHead.next;
while (node != null){
if(node.e.equals(e)){
return true;
}
node = node.next;
}
return false;
}
public void delete(int index){//删除元素
if(index < || index > size){
throw new IllegalArgumentException("索引越界异常");
}
Node prev = dummyHead;
for(int i = ; i < index ; i++){
prev = prev.next;
}
/*prev.next = prev.next.next;//注意！！！ 这是错误的
prev.next.next = null;*/
Node cur = prev.next;
prev.next = cur.next;
cur.next = null;
size--;
}
public void deleteFirst(){
delete();
}
public void deleteLast(){
delete(size-);
}
public void deleteElement(E e){ Node prev = dummyHead;
while(prev.next != null){
if(prev.next.e.equals(e))
break;
prev = prev.next;
} if(prev.next != null){
Node delNode = prev.next;
prev.next = delNode.next;
delNode.next = null;
size --;
}
}
}
三.分析ArrayList和LinkedList的区别
从底层上分析
ArrayList的底层是由数组实现的，而LinkedList的底层是由链表实现的。
ArrayList的空间浪费主要体现在在list列表的结尾预留一定的容量空间，而LinkedList的空间花费则体现在它的每一个元素都需要消耗相当的空间
从效率上分析
1.当随机访问List时（get和set操作），ArrayList比LinkedList的效率更高，因为LinkedList是线性的数据存储方式，所以需要移动指针从前往后依次查找。
2.当对数据进行增加和删除的操作时(add和remove操作)，LinkedList比ArrayList的效率更高，因为ArrayList是数组，所以在其中进行增删操作时，会对操作点之后所有数据的下标索引造成影响，需要进行数据的移动。
3.从利用效率来看，ArrayList*性较低，因为它需要手动的设置固定大小的容量，但是它的使用比较方便，只需要创建，然后添加数据，通过调用下标进行使用；而LinkedList*性较高，能够动态的随数据量的变化而变化，但是它不便于使用。
4.ArrayList主要控件开销在于需要在lList列表预留一定空间；而LinkList主要控件开销在于需要存储结点信息以及结点指针信息。对ArrayList和LinkedList而言，在列表末尾增加一个元素所花的开销都是固定的。对 ArrayList而言，主要是在内部数组中增加一项，指向所添加的元素，偶尔可能会导致对数组重新进行分配；而对LinkedList而言，这个开销是 统一的，分配一个内部Entry对象。
5.LinkedList集合不支持 高效的随机随机访问（RandomAccess），因为可能产生二次项的行为。