关于集合List的源码分析
list是一个接口,继承collection,jdk1.8中新增 spliterator<e> spliterator() 方法
常用的实现类:
arraylist、vector、linklist
|--list:元素是有序的,元素可以重复。因为该集合体系有索引。
|--arraylist:底层的数据结构使用的是数组结构。特点:查询速度很快。但是增删稍慢。线程不同步。
|--linkedlist:底层使用的链表数据结构。特点:增删速度很快,查询稍慢。线程不同步。
|--vector:底层是数组数据结构。线程同步。被arraylist替代了。因为效率低。
arraylist
private static final int default_capacity = 10;
//arraylist的数组元素存储缓存区,arraylist的长度是这个缓存区的长度,任何elementdata == defaultcapacity_empty_elementdata的空arraylist都将扩展到default_capacity ,并作为第一个元素被添加 transient object[] elementdata; //默认初始化一个大小为10的object数组 public arraylist() { this.elementdata = defaultcapacity_empty_elementdata; }
1、arraylist(int initialcapacity) :创建一个大小为initialcapacity的object数组
2、arraylist(collection<? extends e> c):传进去一个collection类型的容器,转换并处理这个数组赋值给object数组
3、arraylist扩容,每次扩容都增加原来的一半,
private void grow(int mincapacity) { // overflow-conscious code int oldcapacity = elementdata.length; int newcapacity = oldcapacity + (oldcapacity >> 1); if (newcapacity - mincapacity < 0) newcapacity = mincapacity; if (newcapacity - max_array_size > 0) newcapacity = hugecapacity(mincapacity); // mincapacity is usually close to size, so this is a win: elementdata = arrays.copyof(elementdata, newcapacity); }
4、int size():返回数组中元素的数量
5、boolean isempty():判断数据是否为空
6、object[] toarray():把list转换为数组
7、e get(int index):返回指定位置的元素
8、e set(int index, e element):用element元素取代指定位置的元素
9、boolean add(e e):添加元素,如果添加元素超出范围,会自动扩容
10、add(int index, e element):在指定位置添加元素
11、e remove(int index):删除指定位置元素
12、boolean remove(object o):删除指定元素
13、void clear():清除arraylist中的元素
14、boolean addall(collection<? extends e> c):传进去一个collection类型的容器,并添加到arraylist中
15、listiterator<e> listiterator():arraylist特有的迭代器,创建一个一开始就指向列表索引为n的元素处的listiterator
linkedlist(来源https://www.cnblogs.com/xujian2014/p/4630785.html)注解做的很好,摘录一下
public class linkedlist<e> extends abstractsequentiallist<e> implements list<e>, deque<e>, cloneable, java.io.serializable { //实现serilizable接口时,将不需要序列化的属性前添加关键字transient,序列化对象的时候,这个属性就不会序列化到指定的目的地中。 transient int size = 0; //指向首节点 transient node<e> first; //指向最后一个节点 transient node<e> last; //构建一个空列表 public linkedlist() { } //构建一个包含集合c的列表 public linkedlist(collection<? extends e> c) { this(); addall(c); } //将节点值为e的节点作为首节点 private void linkfirst(e e) { final node<e> f = first; //构建一个prev值为null,next为f,节点值为e的节点 final node<e> newnode = new node<>(null, e, f); //将newnode作为首节点 first = newnode; //如果newnode后面没有节点就将newnode作为最后一个节点 if (f == null) last = newnode; //否则就将newnode赋给其prev else f.prev = newnode; //列表长度加一 size++; modcount++; } //将节点值为e的节点作为最后一个节点 void linklast(e e) { final node<e> l = last; //构建一个prev值为l,next为null,节点值为e的节点 final node<e> newnode = new node<>(l, e, null); last = newnode; if (l == null) first = newnode; else l.next = newnode; size++; modcount++; } //在非空节点succ之前插入节点e void linkbefore(e e, node<e> succ) { final node<e> pred = succ.prev; //将succ前面的节点和succ作为其prev和next final node<e> newnode = new node<>(pred, e, succ); //然后将newnode作为succ的prev succ.prev = newnode; //如果原来succ是首节点,则将newnode设置为首节点 if (pred == null) first = newnode; else pred.next = newnode; size++; modcount++; } //释放非空的首节点f private e unlinkfirst(node<e> f) { final e element = f.item; final node<e> next = f.next; f.item = null; f.next = null; // help gc //将first节点后面的节点设为首节点 first = next; if (next == null) last = null; else next.prev = null; size--; modcount++; return element; } //释放非空的尾节点l private e unlinklast(node<e> l) { final e element = l.item; final node<e> prev = l.prev; l.item = null; l.prev = null; // help gc last = prev; if (prev == null) first = null; else prev.next = null; size--; modcount++; return element; } //删除非空节点x e unlink(node<e> x) { final e element = x.item; final node<e> next = x.next; //x后面的节点 final node<e> prev = x.prev; //x前面的节点 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; } //返回列表首节点元素值 public e getfirst() { final node<e> f = first; if (f == null) throw new nosuchelementexception(); return f.item; } //返列表尾节点元素值 public e getlast() { final node<e> l = last; if (l == null) throw new nosuchelementexception(); return l.item; } //移除首节点 public e removefirst() { final node<e> f = first; if (f == null) throw new nosuchelementexception(); return unlinkfirst(f); } //删除尾节点 public e removelast() { final node<e> l = last; if (l == null) throw new nosuchelementexception(); return unlinklast(l); } //在列表首部插入节点e public void addfirst(e e) { linkfirst(e); } //在列表尾部插入节点e public void addlast(e e) { linklast(e); } //判断列表中是否包含有元素o public boolean contains(object o) { return indexof(o) != -1; } //返回列表长度大小 public int size() { return size; } //在列表尾部插入元素 public boolean add(e e) { linklast(e); return true; } //删除元素为o的节点 public boolean remove(object o) { if (o == null) { for (node<e> x = first; x != null; x = x.next) { if (x.item == null) { unlink(x); return true; } } } else { for (node<e> x = first; x != null; x = x.next) { if (o.equals(x.item)) { unlink(x); return true; } } } return false; } //将集合c中所有元素添加到列表的尾部 public boolean addall(collection<? extends e> c) { return addall(size, c); } //从指定的位置index开始,将集合c中的元素插入到列表中 public boolean addall(int index, collection<? extends e> c) { //首先判断插入位置的合法性 checkpositionindex(index); object[] a = c.toarray(); int numnew = a.length; if (numnew == 0) return false; node<e> pred, succ; if (index == size) {//说明在列表尾部插入集合元素 succ = null; pred = last; } else { //否则,找到index所在的节点 succ = node(index); pred = succ.prev; } for (object o : a) { @suppresswarnings("unchecked") e e = (e) o; node<e> newnode = new node<>(pred, e, null); if (pred == null) first = newnode; else pred.next = newnode; pred = newnode; } if (succ == null) { last = pred; } else { pred.next = succ; succ.prev = pred; } size += numnew; modcount++; return true; } //删除列表中所有节点 public void clear() { for (node<e> x = first; x != null; ) { node<e> next = x.next; x.item = null; x.next = null; x.prev = null; x = next; } first = last = null; size = 0; modcount++; } //获取指定索引位置节点的元素值 public e get(int index) { checkelementindex(index); return node(index).item; } //替换指定索引位置节点的元素值 public e set(int index, e element) { checkelementindex(index); node<e> x = node(index); e oldval = x.item; x.item = element; return oldval; } //在指定索引位置之前插入元素e public void add(int index, e element) { checkpositionindex(index); if (index == size) linklast(element); else linkbefore(element, node(index)); } //删除指定位置的元素 public e remove(int index) { checkelementindex(index); return unlink(node(index)); } //判断指定索引位置的元素是否存在 private boolean iselementindex(int index) { return index >= 0 && index < size; } private boolean ispositionindex(int index) { return index >= 0 && index <= size; } //构建 indexoutofboundsexception详细信息 private string outofboundsmsg(int index) { return "index: "+index+", size: "+size; } private void checkelementindex(int index) { if (!iselementindex(index)) throw new indexoutofboundsexception(outofboundsmsg(index)); } private void checkpositionindex(int index) { if (!ispositionindex(index)) throw new indexoutofboundsexception(outofboundsmsg(index)); } //返回指定索引位置的节点 node<e> node(int index) { //此处是一个小技巧,当index<size/2时,从列表前半部分开始,否则从后半部分开始 if (index < (size >> 1)) { node<e> x = first; for (int i = 0; i < index; i++) x = x.next; return x; } else { node<e> x = last; for (int i = size - 1; i > index; i--) x = x.prev; return x; } }//返回列表中第一次出现o的位置,若不存在则返回-1 public int indexof(object o) { int index = 0; if (o == null) { for (node<e> x = first; x != null; x = x.next) { if (x.item == null) return index; index++; } } else { for (node<e> x = first; x != null; x = x.next) { if (o.equals(x.item)) return index; index++; } } return -1; } //逆向搜索,返回第一出现o的位置,不存在则返回-1 public int lastindexof(object o) { int index = size; if (o == null) { for (node<e> x = last; x != null; x = x.prev) { index--; if (x.item == null) return index; } } else { for (node<e> x = last; x != null; x = x.prev) { index--; if (o.equals(x.item)) return index; } } return -1; } //获取列表首节点元素值 public e peek() { final node<e> f = first; return (f == null) ? null : f.item; } //获取列表首节点元素值,若为空则抛异常 public e element() { return getfirst(); } //检索首节点,若空则返回null,不为空则返回其元素值并删除首节点 public e poll() { final node<e> f = first; return (f == null) ? null : unlinkfirst(f); } //检索首节点,若空则抛异常,不为空则返回其元素值并删除首节点 public e remove() { return removefirst(); } //在列表尾部增加节点e public boolean offer(e e) { return add(e); } //在列表首部插入节点e public boolean offerfirst(e e) { addfirst(e); return true; } //在列表尾部插入节点e public boolean offerlast(e e) { addlast(e); return true; } public e peekfirst() { final node<e> f = first; return (f == null) ? null : f.item; } //获取列表尾节点元素值 public e peeklast() { final node<e> l = last; return (l == null) ? null : l.item; } public e pollfirst() { final node<e> f = first; return (f == null) ? null : unlinkfirst(f); } public e polllast() { final node<e> l = last; return (l == null) ? null : unlinklast(l); } //入栈 public void push(e e) { addfirst(e); } //出栈 public e pop() { return removefirst(); } //删除列表中第一出现o的节点 public boolean removefirstoccurrence(object o) { return remove(o); } //逆向搜索,删除第一次出现o的节点 public boolean removelastoccurrence(object o) { if (o == null) { for (node<e> x = last; x != null; x = x.prev) { if (x.item == null) { unlink(x); return true; } } } else { for (node<e> x = last; x != null; x = x.prev) { if (o.equals(x.item)) { unlink(x); return true; } } } return false; }
vector中的方法多为同步的,是线程安全的
上一篇: js实现添加删除表格(两种方法)
下一篇: freetds简介、安装、配置及使用介绍