ArrayList与LinkedList

ArrayList
Arraylist底层是基于数组的一个集合，ArrayList中可以储存一切类型的对象，比如基本类型或者引用类型。Arraylist由于底层基于数组实现，所以在存储时使用的内存是连续的，默认容量为10，每次扩容是在原来的基础上增加一半。Arraylist是线程不安全的。
Arraylist中常用方法：
add():插入元素
add(int index,E element):在指定位置上插入元素
clear():清除Arraylist中的元素
get(int index):获取指定下标的元素
indexOf(Object o):获取指定元素的下标索引
iterator():返回一个Arraylist的迭代器
remove(int index):删除指定位置的元素
remove(Object o):删除指定的参数
set(int index,E element):替换指定下标的元素
size():获取Arraylist中元素的长度
toArray():返回一个数组
更多方法请查看API
代码简易实现Arraylist
public class Text {
public static void main(String[] args) {

}
}
//实现ArrayList
class ListArray{
String[] data;
int size=0;
public ListArray(){
data=new String[10];
}
public ListArray(int initCapcity){
data=new String[initCapcity];
}

//数组扩容
public void grow() {
if (data.length <=1) {
data = Arrays.copyOf(data, data.length + 1);
} else
data = Arrays.copyOf(data, 
data.length + (data.length >> 1));
}

//下标是否越界
public void out(int index){
if(index<0||index>=size){
throw new IllegalArgumentException("Index:"+index);
}
}

//添加元素
public void add(String str){
if(size>=data.length){
grow();
}
data[size++]=str;
}

//插入元素
public void add(int index,String str){
if(index<0||index>size){ 
throw new IllegalArgumentException("Index:"+index);
}

if(size>=data.length){
grow();
}
System.arraycopy(data, index, data, index+1, size-index);
data[index]=str;
size++;
}

//根据下标删除(元素个数和长度相等，删除最后一个元素？)
public void remove(int index){
out(index);
System.arraycopy
(data, index+1, data, index, size-(index+1));
//
size--;
}

public void remove(String str){
int index=indexOf(str);
if(index!=-1){
remove(index);
}
}
//返回元素第一次出现的下标值
public int indexOf(String str){
for(int i=0;i<size;i++){ 
if(data[i]==str||
data[i]!=null&&
data[i].equals(str)){ return i;
}
}
return -1;
}


//清空集合
public void clear(){
size=0; 
}

public boolean contains(String str){
return indexOf(str)!=-1;
}

public String get(int index){
out(index);
return data[index];
}

public boolean isEmpty(){
return size==0;
}

//替换元素
public void set(int index,String str){
out(index);
data[index]=str;
}

//返回元素个数
public int size(){
return size;
}

//截取子列表
public ListArray subList(int fromindex,int toindex){
out(fromindex);
out(toindex);
if(toindex<fromindex){
throw new 
IllegalArgumentException
("FromIndex:"+fromindex+",ToIndex:"+toindex);
}
int count=toindex-fromindex;
ListArray list=new ListArray(count);
System.arraycopy(data, fromindex, list.data, 0, count);
list.size=count;
return list;
}


//重写toString方法
//输出对象的时候输出是元素
@Override
public String toString() {
StringBuilder sb=new StringBuilder("[");
for(int i=0;i<size;i++)//只遍历有元素的下标
sb.append(data[i]).append(", ");
}
String str=sb.toString();
if(size>0)
str=str.substring(0,str.length()-2);
//返回
return str+="]";
}

}
LinkedList
LinkdeList底层是以节点来存储数据的，是一个双向链表。在节点中需要存储上一个节点的地址值(prev)和下一个节点的地址值(next)(头节点只有下一个节点的地址值(next)，尾节点只有上一个节点的地址值(prev))。由于LinkdeList基于节点来存储数据，所以使用的内存不连续。LinkdeList是线程不安全的。
Arraylist中常用方法：
add():插入元素
add(int index,E element):在指定位置上插入元素
clear():清除Arraylist中的元素
element() :查找但不删除，此列表的头（第一个元素）
get(int index):获取指定下标的元素
getFirst():返回第一个元素。  
getLast():返回最后一个元素。
indexOf(Object o):获取指定元素的下标索引，如不存在就返回-1
remove(int index):删除指定位置的元素
remove(Object o):删除指定的参数
set(int index,E element):替换指定下标的元素
size():获取Arraylist中元素的长度
toArray():返回一个数组
更多方法请查看API
简易实现LinkdeList
public class LinkedListDemo { public static void main(String[] args) {

}

}//实现linkedlist
class ListLinked{
//属性
//元素个数
int size = 0;
//头节点---第一个节点
Node first;
//尾节点---最后一个节点
Node last;

//节点内部类
class Node{
//属性
//存储的元素
String item;
//上一个节点
Node prev;
//下一个节点
Node next;

//有参构造
public Node(String item,Node prive,Node next){
this.item = item;
this.next = next;
this.prev = prive;
}
}
//判断下标越界
private void out(int index) {
if(index<0||index>=size){
throw new IllegalArgumentException("index"+index);
} }
//
public Node getNode(int index){
Node no = this.first;
for(int i=0;i<index;i++ ){
no=no.next;
}
return no;
}
//添加
public void add(String str){
Node node = new Node(str, null, null);
if(size==0){
this.first = node;
this.last = node;
}else{
this.last.next = node;
node.prev = this.last;
}
this.last = node;
size++;
}
//插入
public void add(int index,String str){
if(index<0||index>size){
throw new IllegalArgumentException("index"+index);
}
Node node = new Node(str, null, null);
if(index==size){
add(str);
return;
}
if(index==0){
this.first.prev = node;
node.next = this.first;
this.first = node;
}else{ 
Node no = this.first;
for(int i=0;i<index;i++ ){
no=no.next;
}
no.prev.next = node;
node.prev=no.prev;
no.prev = node;
node.next = no;

}
size++;
}
//删除--根据下标
public void remove(int index){
out(index);
if(index==0){
this.first.next.prev = null;
this.first = this.first.next;

}else if(index==size-1){
this.last.prev.next=null;
this.last=this.last.prev;
}else{
Node no = getNode(index);
//
no.next.prev = no.prev;
//
no.prev.next = no.next;

}
size--;

}

//根据下标删除
public void remove(String str){
int index = indexOf(str);
//
if(index!=-1){
remove(index);
}
}
//查找
public int indexOf(String str) {
Node node = this.first;
for(int i=0;i<size;i++){ if(str==node.item||str!=null&&str.equals(node.item)){ return i;

}
node = node.next;
}
return -1;
}
//重写toString
public String toString(){
//
StringBuilder sBuilder=new StringBuilder("[");
Node no = this.first;
for(int i=0;i<size;i++){
sBuilder.append(no.item).append(", ");
no = no.next;
}
String str = sBuilder.toString();
if(size>0){
str = str.substring(0,str.length()-2);
}
return str + "]";
}

}
   ArrayList与LinkedList的对比:1. ArrayList与LinkedList都是线程不安全的。2.由于ArrayList底层由数组实现，所以查询速度较快，增删改速度较慢。内存是连续的。LinkedList底层是基于节点，所以增删较快，查询较慢。内存是连续的。  第一次写这类东西，不喜勿喷，要是有什么不对的地方请联系我加以改正。