Java基础之LinkedList

Java基础之LinkedList

1. 概述

LinkedList同时实现了List接口和Deque接口,也就是说它既可以看作一个顺序容器,又可以看作一个队列(Queue),同时又可以看作一个栈(Stack)。这样看来,LinkedList简直就是个全能冠军。当你需要使用栈或者队列时,可以考虑使用LinkedList,一方面是因为Java官方已经声明不建议使用Stack类,更遗憾的是,Java里根本没有一个叫做Queue的类(它是个接口名字)。关于栈或队列,现在的首选是ArrayDeque,它有着比LinkedList(当作栈或队列使用时)有着更好的性能。


2. 底层实现

  • LinkedList底层通过双向链表实现,双向链表的每个节点用内部类Node表示。LinkedList通过first和last引用分别指向链表的第一个和最后一个元素。
//Node内部类
private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;
    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

3. 常用方法介绍

本节将着重讲解插入和删除元素时双向链表的维护过程,也即是直接跟List接口相关的函数。

3.1 add()

add() 方法有两个版本,一个是 add(E e) ,该方法在 LinkedList 的末尾插入元素,因为有last指向链表末尾,在末尾插入元素的花费是常数时间。只需要简单修改几个相关引用即可;另一个是 add(int index, E element),该方法是在指定下表处插入元素,需要先通过线性查找找到具体位置,然后修改相关引用完成插入操作。

Java基础之LinkedList
结合上图,可以看出 add(E e) 的逻辑非常简单。

//add(E e)
public boolean add(E e) {
    final Node<E> l = last;  // 先保留原来的尾节点
    final Node<E> newNode = new Node<>(l, e, null);  // 声明并初始化待插入的节点
    last = newNode;  // 更新尾节点
    if (l == null)
        first = newNode;  //原来链表为空,这是插入的第一个元素
    else
        l.next = newNode;  // 原来的尾节点变为倒数第二个节点,更新其next指针
    size++;
    return true;
}

add(int index, E element) 的逻辑稍显复杂,可以分成两部分,1.先根据index找到要插入的位置;2.修改引用,完成插入操作。

//add(int index, E element)
 public void add(int index, E element) {
        checkPositionIndex(index);//index >= 0 && index <= size;
        if (index == size)//插入位置是末尾,包括列表为空的情况
            add(element);
        else {
            Node<E> succ = node(index);//1.先根据index找到要插入的位置
            //2.修改引用,完成插入操作。
            final Node<E> pred = succ.prev;
            final Node<E> newNode = new Node<>(pred, e, succ);
            succ.prev = newNode;
            if (pred == null)//插入位置为0
                first = newNode;
            else
                pred.next = newNode;
            size++;
        }
    }

上面代码中的 node(int index) 函数有一点小小的trick,因为链表双向的,可以从开始往后找,也可以从结尾往前找,具体朝那个方向找取决于条件 index < (size >> 1),也即是 index 是靠近前端还是后端。


3.2 remove()

remove() 方法也有两个版本,一个是删除跟指定元素相等的第一个元素 remove(Object o),另一个是删除指定下标处的元素 remove(int index)

Java基础之LinkedList
两个删除操作都要:1.先找到要删除元素的引用,2.修改相关引用,完成删除操作。在寻找被删元素引用的时候 remove(Object o) 调用的是元素的equals方法,而 remove(int index) 使用的是下标计数,两种方式都是线性时间复杂度。在步骤2中,两个 remove() 方法都是通过unlink(Node<E> x) 方法完成的。这里需要考虑删除元素是第一个或者最后一个时的边界情况。

//unlink(Node<E> x),删除一个Node
E unlink(Node<E> x) {
    final E element = x.item;
    final Node<E> next = x.next;
    final Node<E> prev = x.prev;
    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;//let GC work
    size--;
    return element;
}


3.3 get()

get(int index) 得到指定下标处元素的引用,通过调用上文中提到的 node(int index) 方法实现。

public E get(int index) {
    checkElementIndex(index);//index >= 0 && index < size;
    return node(index).item;
}
Node<E> node(int index) {
    // assert isElementIndex(index);
    if (index < (size >> 1)) {  // index在前半部分,从头指针开始查找
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {                    // index在后半部分,从尾指针开始查找
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

3.4 set()

set(int index, E element) 方法将指定下标处的元素修改成指定值,也是先通过 node(int index) 找到对应下表元素的引用,然后修改 Nodeitem 的值。

public E set(int index, E element) {
    checkElementIndex(index);
    Node<E> x = node(index);
    E oldVal = x.item;
    x.item = element;//替换新值
    return oldVal;
}

4. 遍历方法

4.1 Iterator方法遍历

for(Iterator it = list.iterator();it.hasNext();){
     System.out.println(it.next());
}

遍历时不能使用list的删除方法,否则会报并发修改异常,但是可以使用迭代器的删除方法


4.2 for循环遍历

for(int i = 0;i < list.size(); i ++){
    System.out.println(list.get(i));
}

遍历时可以修改list


4.3 增强for循环遍历

for(String tmp:list){
    System.out.println(tmp);
}

底层基于迭代器实现,遍历时不能使用list的删除方法,否则会报并发修改异常,但是可以使用迭代器的删除方法


4.4 用pollFirst()遍历

while(list.pollFirst() != null) {
	;
}

4.5 用pollLast()遍历

while(list.pollLast() != null) {
	;
}

4.6 用removeFirst()遍历

try {  
    while(list.removeFirst() != null)  
        ;  
} catch (NoSuchElementException e) {  
}  

4.7 用removeLast()遍历

try {
while(list.removeLast() != null)
;
} catch (NoSuchElementException e) {
}

6. 参考

上一篇:单链表反转(迭代和递归)


下一篇:记录·链表逆序