疯狂java


您现在的位置: 疯狂软件 >> 新闻资讯 >> 正文

干了这杯Java之LinkedList


 

 
LinkedList和ArrayList一样实现了List接口
 
ArrayList内部为数组
LinkedList内外为双向链表
实现了Deque接口,双端列队的实现
 
 
图片来自Wiki
内部实现为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;
    }
}
LinkedList都一个元素都知道它上一个和下一个元素的地址
next属性表示下一个元素对象
prev属性表示上一个元素对象
item属性为当前元素对象
属性
 
transient int size = 0;
transient Node<E> first;
transient Node<E> last;
不能被序列化
add方法
 
public boolean add(E e) {
    linkLast(e);
    return true;
}
void linkLast(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;
    size++;
    modCount++;
}
原来last属性改为e
如果原last对象为空,则第一个元素为新元素
如果原last对象的next元素改为新元素
addFirst方法
 
private void linkFirst(E e) {
    final Node<E> f = first;
    final Node<E> newNode = new Node<>(null, e, f);
    first = newNode;
    if (f == null)
        last = newNode;
    else
        f.prev = newNode;
    size++;
    modCount++;
}
只改了原first元素的上一个元素地址
addList,只改了原last元素的下一个元素地址
set方法
 
public E set(int index, E element) {
    checkElementIndex(index);
    Node<E> x = node(index);
    E oldVal = x.item;
    x.item = element;
    return oldVal;
}
Node<E> node(int index) {
    // assert isElementIndex(index);
    if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}
索引是按循环查找的
就近原则
原来的元素会返回
indexOf方法
 
public int indexOf(Object o) {
    int index = 0;
    if (o == null) {
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null)
                return index;
            index++;
        }
    } else {
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item))
                return index;
            index++;
        }
    }
    return -1;
}
equals比较
toArray方法
 
public Object[] toArray() {
    Object[] result = new Object[size];
    int i = 0;
    for (Node<E> x = first; x != null; x = x.next)
        result[i++] = x.item;
    return result;
}
 
public <T> T[] toArray(T[] a) {
    if (a.length < size)
        a = (T[])java.lang.reflect.Array.newInstance(
                            a.getClass().getComponentType(), size);
    int i = 0;
    Object[] result = a;
    for (Node<E> x = first; x != null; x = x.next)
        result[i++] = x.item;
 
    if (a.length > size)
        a[size] = null;
 
    return a;
}
clear方法
 
public void clear() {
    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++;
}
所有都被清空
get方法
 
public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}
使用了循环
remove方法
 
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;
    f.item = null;
    f.next = null; // help GC
    first = next;
    if (next == null)
        last = null;
    else
        next.prev = null;
    size--;
    modCount++;
    return element;
}
remove索引
 
public E remove(int index) {
    checkElementIndex(index);
    return unlink(node(index));
}
E unlink(Node<E> x) {
    // assert x != null;
    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;
    size--;
    modCount++;
    return element;
}
remove object
 
public boolean remove(Object o) {
    if (o == null) {
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null) {
                unlink(x);
                return true;
            }
        }
    } else {
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item)) {
                unlink(x);
                return true;
            }
        }
    }
    return false;
}
结论:
 
不带索引的操作都是比较快的,比如add、removeFirst等
链表是往后添加的
可以从前、后添加移除数据
可以当堆栈、队列或双端队列操作