当前位置：首页 > article >正文

《Java核心技术卷I》链表

article 2024/11/22 21:41:23

链表

ArrayList底层是数组，增删慢。

集合框架中的类

从数组中删除一个元素

链表(linked list)解决这个问题，在Java程序中所有链表实际上是双向链接(doubly linked)，每个链接存放前面的引用。

删除元素很容易，将前后引用对象指向另一个就可以了。

小练习，增加5个元素，然后将第2个元素删除

package collection;

import java.util.Iterator;
import java.util.LinkedList;

public class LinkedListTest {

    public static void main(String[] args) {
        var staff = new LinkedList<String>();
        staff.add("Amy");
        staff.add("Bob");
        staff.add("Carl");
        staff.add("Dog");
        staff.add("Egg");
        Iterator<String> iter = staff.iterator();
        String f = iter.next();
        String s = iter.next();
        System.out.println(f);
        iter.remove();
        iter = staff.iterator();
        iter.forEachRemaining((e)->{
            System.out.println(e);
        });
    }
}

结果：Amy Amy Carl Dog Egg

Iterator接口中没有add方法，提供子接口ListIterator包含add方法，返回值为void，假定add操作总是能增加元素。

ListIterator接口有两个方法，E previous()和hasPrevious()用来反向遍历链表。

LinkedList返回了一个ListIterator接口的迭代器对象。

小案例

package collection;

import java.util.LinkedList;
import java.util.ListIterator;

public class LinkedListListIteratorTest {

    public static void main(String[] args) {
        var staff = new LinkedList<String>();
        staff.add("Amy");
        staff.add("Bob");
        staff.add("Carl");
        staff.add("Dog");
        staff.add("Egg");
        ListIterator<String> iter = staff.listIterator();
        iter.next();//略过第一个元素
        iter.add("Juliet");
        iter = staff.listIterator();
        iter.forEachRemaining((e)->{
            System.out.print(e+" ");
        });
    }

}
//结果：Amy Juliet Bob Carl Dog Egg

不略过任何元素，则当前元素插入后为表头，若迭代器越过链表最后一个元素(hasNext返回false)，插入的元素称为列表的新表尾。

链表有n个元素，会有n+1个位置可以添加新元素。

ABC三个元素就有4个位置，|ABC A|BC AB|C ABC|

set方法用新元素替换调用next和previous方法返回上一个元素。

某个迭代器修改集合，另一个迭代器访问，会出错，抛出ConcurrentModificationException异常。

package collection;

import java.util.LinkedList;
import java.util.ListIterator;

public class LinkedListListIteratorTest {

    public static void main(String[] args) {
        var staff = new LinkedList<String>();
        staff.add("Amy");
        staff.add("Bob");
        staff.add("Carl");
        staff.add("Dog");
        staff.add("Egg");
        ListIterator<String> iter1 = staff.listIterator();
        ListIterator<String> iter2 = staff.listIterator();
        iter1.next();
        iter1.remove();
        iter2.next();
    }

}
//Exception in thread "main" java.util.ConcurrentModificationException

LinkedList类提供了get方法反问特定元素，效率并不高。

注释：get方法做了一个微小的优化，如果索引大于size()/2，就从列表尾端搜索元素。

列表迭代器还有一个方法是告诉你当前位置的索引，有两个索引，nextIndex和previousIndex。

list.listIterator(n)将返回一个迭代器指向n的元素前面的位置，效率高。