List 集合(实现类有ArrayList和LinkedList)
1.有索引：List 集合是有索引的
2.有序性：List 集合是有序的保证了装入集合时的顺序
3.重复性：List 集合允许存储重复的元素
1、List list1 = new ArrayList();
底层数据结构是数组，查询快，增删慢；线程不安全，效率高。
2、List list3 = new LinkedList();
底层数据结构是链表，查询慢，增删快；线程不安全，效率高。
3、List list2 = new Vector();
底层数据结构是数组，查询快，增删慢；线程安全，效率低，这个集合几乎被淘汰。
List 常用方法学习
public class TestList {
public static void main(String[] args) {
List list = new ArrayList();
Collection list2 = new ArrayList();
//增加元素
list.add("1");
list.add("2");
list.add("3");
list.add("5");
list.add("4");
list.add("5");
//增加元素
list.remove("1");
//改变元素
list.set(4,"被修改了");
System.out.println(list);
//构造 List 的迭代器
Iterator it = list.iterator();
//通过迭代器遍历元素
while(it.hasNext()){
Object obj = it.next();
System.out.println(obj);
}
// List 独有的 遍历方式
for(int i = 0 ; i < list.size() ; i++){
System.out.println(list.get(i));
}
/**
List<E> subList(int fromIndex, int toIndex)
获取一个子集合
参数1 是开始截取的索引
参数2 是结束截取的索引
包含参数1 不包含参数2*/
List li = list.subList(2, list.size());
System.out.println(li);
}
}
public int indexOf(Object o) {
if (o == null) {
for (int i = 0; i < size; i++)
if (elementData[i]==null)
return i;
} else {
for (int i = 0; i < size; i++)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
public int lastIndexOf(Object o) {
if (o == null) {
for (int i = size-1; i >= 0; i--)
if (elementData[i]==null)
return i;
} else {
for (int i = size-1; i >= 0; i--)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
ArrayList--底层是数组
每增加一个元素，就会判断数组是否需要扩容，拿现在size + 1 去判断，如果需要扩容，那就扩容1.5倍。
int newCapacity = oldCapacity + (oldCapacity >> 1);然后
elementData[size++] = 要添加的元素
public boolean add(Object obj){
ensureCapacityInternal(size+1)//扩容
elementData[size++] = obj;
return ture;
}
每移除一个元素，会先确定元素的位置，确定元素的值，然后把 要删除的位置之前的，之后的copy到新数组，新数组替换 elementData ，然后把最后一位size赋值为null size也要 --
public E remove(int index){
rangeCheck(index);
modcount++;
E oldValue = elementData(index)
int numMoved = size - index -1;
if(numMoved>0)
System.arraycopy(elementData,index+1,elementData,index,numMoved);
elementData[--size]=null;
return oldValue;
}
LinkedList--底层是链表
链式存储的线性表
Node 对象：Node对象有 三个属性
item：要存储的对象
next：下一个元素对象 (last 的next 一般为 null)
prev：上一个元素对象 (first 的prev 一般为 null)
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null){
first = newNode;
}else{
l.next = newNode;
}
size++;
modCount++;
}
E unlink(Node<E> x) {
// assert x != null;
final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;
if (prev == null) {
first = next;
} else {
prev.next = next;
x.prev = null;
}
if (next == null) {
last = prev;
} else {
next.prev = prev;
x.next = null;
}
x.item = null;
size--;
modCount++;
return element;
}
2. 记录 要移除的对象的 上一个指向(prev) 存储的值(value) 下一个指向(next)
3. prev 代表的对象 next 属性不再指向被移除的对象 改为指向 next代表的对象
4. next 代表的对象 它的 prev 属性不要指向被移除的对象 改为指向 prve代表的对象
同时要考虑 被移除对象可能是 first 或 last , 处理方式会有所不同
要得到第一个 Node对象，然后不停的寻找下一个对象即 next 属性，然后一直寻找到最后的，中间地址跳转频繁 ：
文章转载自Spark大数据，如果涉嫌侵权，请发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。
