链表

链表

ArrayList、LinkedList对比

1、LinkedList没有随机访问功能。 2、利用index访问LinledList需要使用循环。 3、LinkedList双参数方法是常数级别，而ArrayList是O(n)。 5、LinkedList没有初始容量大小的构造函数。 6、含有ArrayList没有的方法。

public boolean addFirst(Object element);

public boolean addLast(Object element);

public Object getFirst();

public Object getLast();

public Object removeFirst();

public Object removeLast();

7、数据访问较多时，ArrayList O(1)优于LinkedList O(n)。 8、ArrayList利用索引线性循环，而LinkedList需要利用迭代器。

LinkedList迭代器

1、双向迭代 2、code case

public class LinkedListDemo1 {

    public static void main(String[] args) {
        LinkedList<Integer> list=new LinkedList<Integer>();
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);

        ListIterator<Integer> it=list.listIterator(0);
        while(it.hasPrevious()){
            //System.out.println(it.next());
            System.out.println(it.previous());
        }
    }

}

LinkedList源码分析

• public void add(int index,Object element); index为非末尾，为了获取index位置的Node，从header字段开始循环，根据index与(size/2)决定正向进行还是 反向进行。

 public void add(int index, E element) {
        checkPositionIndex(index);

        if (index == size)
            linkLast(element);
        else
            linkBefore(element, node(index));
    }

• remove()类似add(int index,Object element)

 public E remove(int index) {
        checkElementIndex(index);
        return unlink(node(index));
    }

`

• ListIterator

1、源码分析

 public ListIterator<E> listIterator(int index) {
        checkPositionIndex(index);
        return new ListItr(index);
    }

    private class ListItr implements ListIterator<E> {
        private Node<E> lastReturned = null;
        private Node<E> next;
        private int nextIndex;
        private int expectedModCount = modCount;

        ListItr(int index) {
            // assert isPositionIndex(index);
            next = (index == size) ? null : node(index);
            nextIndex = index;
        }

2、previous()方法 a.源码分析

```java
public E previous() {
        checkForComodification();
        if (!hasPrevious())
            throw new NoSuchElementException();

        lastReturned = next = (next == null) ? last : next.prev;
        nextIndex--;
        return lastReturned.item;
    }

```
b.如果交替使用next() previous()返回同一值。

```java
public static void main(String[] args) {
    LinkedList<Integer> list=new LinkedList<Integer>();
    list.add(1);
    list.add(2);

    ListIterator<Integer> it=list.listIterator();
    System.out.println(it.next());
    System.out.println(it.previous());
    System.out.println(it.next());
    //System.out.println(it.next());   
}

```