上一篇Java从入门到放弃(八)集合框架之LinkedList源码(1)介绍了add和remove方法,这篇介绍LinkedList的set,get等方法。
1、get方法
public E get(int index) { checkElementIndex(index); return node(index).item; }
方法很简单,就是一个越界检查,然后调用node(index)方法获取对应的节点,然后返回节点的item。node(index)方法和链表结构上一篇已经讲过了,这里不再讲解。
2、set方法
public E set(int index, E element) {
checkElementIndex(index); //越界检查
Node<E> x = node(index); //获取对应节点
E oldVal = x.item;
x.item = element; //节点item指向新的元素
return oldVal;
}
这里还是使用了node(index)方法,把对应节点的item数据更改为新的元素,返回旧的元素。
3、pop(),push(),offer(),peek(),poll()方法
pop: 删除第一个节点并返回
public E pop() { return removeFirst(); }看一下removeFirst方法
public E removeFirst() { final Node<E> f = first; if (f == null) throw new NoSuchElementException(); return unlinkFirst(f); } private E unlinkFirst(Node<E> f) { // assert f == first && f != null; final E element = f.item; final Node<E> next = f.next; //获取first的next节点,即第二个节点 f.item = null; f.next = null; // help GC first = next; //将first指向第二个节点 if (next == null) last = null; else next.prev = null; size--; modCount++; return element; }
就是把头节点删除,first指向第二个节点。
push:在链表头加入一个元素,不返回
public void push(E e) { addFirst(e); } public void addFirst(E e) { linkFirst(e); } private void linkFirst(E e) { final Node<E> f = first; final Node<E> newNode = new Node<>(null, e, f); //新的节点,next指向first的节点 first = newNode; //first指向新的节点 if (f == null) last = newNode; else f.prev = newNode; //f的perv节点指向新节点 size++; modCount++; }
在开头加入一个节点,就是把first节点指向新的节点,然后把之前的first节点f的perv引用指向新节点。
offer:链表尾部增加元素,返回添加结果
public boolean offer(E e) { return add(e); }就是调用了add(e)方法,具体实现看上一篇博文。
peek:返回头部元素
public E peek() { final Node<E> f = first; return (f == null) ? null : f.item; }返回first节点的item元素。没有九返回null;
poll:删除第一个节点并返回
public E poll() { final Node<E> f = first; return (f == null) ? null : unlinkFirst(f); }和pop作用一样,区别就是pop如果没有第一个元素会抛出异常。
LinkedList除了这几个还有removeLast(),pollLast()等方法,所以可以很容易的用LinkedList实现一个队列或者栈的结构。
4、clear,size,isEmpty
public void clear() { // Clearing all of the links between nodes is "unnecessary", but: // - helps a generational GC if the discarded nodes inhabit // more than one generation // - is sure to free memory even if there is a reachable Iterator 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++; }
size方法和isEmpty就不贴代码了,size()就是返回size属性,isEmpty就是判断size是否等于0,
clear方法和ArrayList方法类似,就是把所有元素和引用都置为null,便于GC。
5、迭代器
和ArrayList不一样的是,iterator方法返回的是listIterator;这个方法是从AbstractSequentialList继承而来。
public Iterator<E> iterator() { return listIterator(); }关于listIterator和Iterator的区别具体看 Java从入门到放弃(七)集合框架之ArrayList的坑。
6、LinkedList和ArrayList的不同
LinkedList是基于双向链表实现的,各个节点直接的通过next和perv来连接,与数组不同,ArrayList的数组结构使得ArrayList可以通过索引快速访问元素,包括查询和修改,时间复杂度O(1),但是不便于添加和删除,因为每次添加或者删除要移动目标节点后的所有元素。而LinkedList基于链表结构,可以很快的进行添加和删除,只是把对应的next和perv更改就实现了添加删除,但是在查询和更改的时候,会比较慢,因为需要从first(或者last)遍历链表。
在查询和更改比较多的情况下使用ArrayList,在增加、删除比较多的情况下使用LinkedList.