LinkedList链表

一.链表与数组以及ArrayList类的区别

从数组的中间位置删除一个元素要付出很大的代价，其原因是数组中处于被删除元素之后的所有元素都要向数组的前端移动。在数组中间位置上插入一个元素也是如此。
链表解决了这个问题。尽管数组在连续的存储位置上存放对象的引用，但链表却将每个对象存放在独立的结点中。每个结点还存放着序列中下一个结点的引用。在Java程序设计语言中，所有链表实际上都是双向链接的—即每个结点还存放着指向前驱结点的引用。
从链表中删除一个元素，即需要更新被删除元素附近的链接
链表与ArrayList集合之间还有一个重要的区别。链表是一个有序集合，每个对象的位置很重要。LinkedList.add()方法将对象添加到链表尾部。但是，常常需要将元素添加到链表中间。由于迭代器是描述集合位置的，所以这种依赖于位置的add方法将有迭代器负责。只有对自然有序的集合使用迭代器添加元素才有实际意义。Set类型其中元素完全无序，因此在Iterator接口中就没有add方法。相反的，集合类库提供了子接口ListIterator，其中包含add方法。

二.`ListIterator`接口

ListIterator接口除了提供add方法外，还提供了反向遍历链表的方法

E previous()
boolean hasPrevios()

与next方法一样，previous方法返回越过的对象。
Add方法在迭代器位置之前添加一个新对象。当用一个刚刚由Iterator方法返回，并且指向链表表头的迭代器调用add操作时，新添加的元素将变成列表的新表头。当迭代器越过链表的最后一个元素时(即hasNext返回false)，添加的元素将会变成列表的新表尾。
可以想象，如果某个迭代器修改集合时，另一个迭代器对其进行遍历，一定会出现混乱的情况，代码将会抛出ConcurrentModificationException异常。
为了避免发生并发修改异常，可以根据需要给容器附加许多的迭代器，但是这些迭代器只能读取列表。另外，再单独附加一个既能读又能写的迭代器。
有一种简单的方法可以检测到并发修改的问题。集合可以跟踪改写操作(诸如添加或删除元素)的次数。每个迭代器都维护一个独立的计数值。在每个迭代器方法的开始处检查自己改写操作的计数值是否与集合的改写操作计数值一致。如果不一致，就抛出一个ConcurrentModificationException异常。

三.常用API调用

public class LinkedListTest {
    public static void main(String[] args) {
        List<String> a = new LinkedList<>();

        a.add("Amy");
        a.add("Carl");
        a.add("Erica");
        a.add(1,"whz");

        List<String> b = new LinkedList<>();

        b.add("Bob");
        b.add("Doug");
        b.add("Frances");
        b.add("Gloria");

        //listIterator()与iterator()方法有不同
        ListIterator<String> aIter = a.listIterator();
        Iterator<String> bIter = b.iterator();

        while (bIter.hasNext()){
            if(aIter.hasNext()){
                aIter.next();
            }
            aIter.add(bIter.next());
        }
        //System.out.println(a);

        bIter = b.iterator();
        while (bIter.hasNext()){
            bIter.next();
            if(bIter.hasNext()){
                bIter.next();
               // bIter.remove();
            }
        }
        // System.out.println(b);
        System.out.println("a + b =" + a);
        a.removeAll(b);
        System.out.println("a - b =" + a);
    }
}

// java.util.Linked<E>

LinkedList(Collection<? extends E> elements)  //构造一个链表，并将集合中所有的元素添加到这个链表中

void addFirst(E element)  //将元素添加到列表头部
void addLast(E element)  //将元素添加到列表尾部

E getFirst()  //返回列表头部元素
E getLast()  //返回列表尾部元素

E removeFirst()  //删除并返回头部元素
E removeLast()  //删除并返回尾部元素

一.链表与数组以及ArrayList类的区别

二.ListIterator接口

三.常用API调用

相关推荐

二.`ListIterator`接口