四川盐亭网站制作公司

如何用源码分析LinkedList

这篇文章将为大家详细讲解有关如何用源码分析LinkedList，文章内容质量较高，因此小编分享给大家做个参考，希望大家阅读完这篇文章后对相关知识有一定的了解。

创新互联建站专注于淮安网站建设服务及定制，我们拥有丰富的企业做网站经验。 热诚为您提供淮安营销型网站建设，淮安网站制作、淮安网页设计、淮安网站官网定制、微信小程序开发服务，打造淮安网络公司原创品牌,更为您提供淮安网站排名全网营销落地服务。

LinkedList简介
public class LinkedList
    extends AbstractSequentialList
    implements List, Deque, Cloneable, java.io.Serializable{
}

  • LinkedList继承了AbstractSequentialList，主要方法通过迭代器实现。

  • LinkedList实现了List；所以它是一个队列，支持添加、删除、修改、遍历等操作。

  • LinkedList实现了Deque；能将它可以当做双端队列进行使用。

  • LinkedList实现了Cloneable接口，重写了clone方法，因此可以进行克隆。

  • LinkedList实现了Serializable接口，因此可以进行序列化。

  • LinkedList的操作是非线程安全的

成员变量
/** 当前集合的头节点 **/
transient Node first;

/** 当前集合的尾节点 **/
transient Node last;

/** 当前集合的实际节点数量 **/
transient int size;
Node分析
private static class Node {
    E item;
    Node next;
    Node prev;

    Node(Node prev, E element, Node next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

双向链表的具体节点类，每个节点每个节点又包含三个变量：

  • item保存当前节点的具体数据

  • prev保存当前节点的上一个节点

  • next保存当前节点的下一个节点

构造函数
/** 无参构造一个空的集合 **/
public LinkedList() {
}

/** 根据已有集合构造一个LinkedList **/
public LinkedList(Collection c) {
    this();
    addAll(c);
}
元素添加

集合添加元素方法主要有以下几个方法：

  • 在集合头部添加元素，通过linkFirst方法实现；如：addFirst(E e)、offerFirst(E e)、push(E e)。

  • 在集合尾部添加元素，通过linkLast方法实现；如：add(E e)、addLast(E e)、offer(E e)、offerLast(E e)。

  • 在集合指定位置添加元素；如：add(int index, E element)。

  • 在集合中添加新的集合；如：addAll(Collection c)、addAll(int index, Collection c)。

linkFirst(E e)

private void linkFirst(E e) {
    final Node f = first;
    final Node newNode = new Node<>(null, e, f);
    first = newNode;
    if (f == null) last = newNode;
    else f.prev = newNode;
    size ++;
    modCount ++;
}

public void addFirst(E e) {
    linkFirst(e);
}

public boolean offerFirst(E e) {
    addFirst(e);
    return true;
}

public void push(E e) {
    addFirst(e);
}

  • 先获取到首部节点first，再根据首部节点生成新的首部节点newNode

  • 如果原首部节点first为空，那么尾部节点也为newNode，否则设置原节点的上一个为newNode

linkLast(E e)

private void linkLast(E e) {
    final Node l = last;
    final Node newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null) {
        first = newNode;
    } else {
        l.next = newNode;
    }
    size ++;
    modCount ++;
}

public boolean add(E e) {
    linkLast(e);
    return true;
}

public void addLast(E e) {
    linkLast(e);
}

public boolean offer(E e) {
    return add(e);
}

public boolean offerLast(E e) {
    addLast(e);
    return true;
}

  • 先获取到尾部节点last，再根据尾部节点生成新的尾部节点newNode

  • 如果原尾部节点last为空，那么首部节点也为newNode，否则设置原节点的下一个为newNode

add(int index, E element)

/** 添加元素element到当前集合的index位置 **/
public void add(int index, E element) {
    //校验index是否合法
    checkPositionIndex(index);
    if (index == size)
        linkLast(element);
    else
        linkBefore(element, node(index));
}

/** 检查index合法 **/
private void checkPositionIndex(int index) {
    if (index < 0 || index > size) {
        throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
    }
}

/** 在给定元素前插入元素 **/
void linkBefore(E e, Node succ) {
    final Node prev = succ.prev;
    final Node newNode = new Node<>(prev, e, succ);
    succ.prev = newNode;
    if (prev == null) {
        first = newNode;
    } else {
        prev.next = newNode;
    }
    size ++;
    modCount ++;
}

/** 根据index定位元素 **/
private Node node(int index) {
    if (index < size >> 1) {
        Node e = first;
        for (int i = 0; i < index; i++) e = e.next;
        return e;
    } else {
        Node e = last;
        for (int i = size - 1; i > index; i--) e = e.prev;
        return e;
    }
}

  • 先校验index位置，如果是最后一个则直接调用linkLast(E e)

  • 不是最后的位置，则先根据index查找Node节点；如果index小于总长度一般，就从头往尾找，否则就从尾往头部找

  • 最后将元素插入到找到的Node节点前面

addAll(Collection c)

/** 通过下面的addAll(int index, Collection c)方法实现**/
public boolean addAll(Collection c) {
    return addAll(size, c);
}

/** 在当前集合index位置插入集合c中所有元素 **/
public boolean addAll(int index, Collection c) {
    //校验index
    checkPositionIndex(index);
    Object[] a = c.toArray();
    int numNew = a.length;
    if (numNew == 0) return false;
    Node succ, pred;
    if (index == size) {
        succ = null;
        pred = last;
    } else {
        succ = node(index);
        pred = succ.prev;
    }

    for (Object o : a) {
        Node newNode = new Node(pred, o, null);
        if (pred == null) first = newNode;
        else pred.next = newNode;
        pred = newNode;
    }

    if (succ == null) {
        last = pred;
    } else {
        pred.next = succ;
        succ.prev = pred;
    }

    size += numNew;
    modCount ++;
    return true;
}
元素移除

元素移除主要有以下几个方法：

  • 移除指定位置的元素，通过unlink方法实现；如：``remove(int index)`。

  • 移除链表中指定的对象；如：remove(Object o)。

  • 移除集合头部元素，通过unlinkFirst方法实现；如：remove()、removeFirst()、poll()、pollFirst()、pop()。

  • 移除集合尾部元素，通过unlinkLast方法实现；如：removeLast()、pollLast()。

remove(int index)

E unlink(Node x) {
    final E element = x.item;
    final Node prev = x.prev;
    final Node next = x.next;
    if (prev == null) {
        first = next;
    } else {
        prev.next = next;
        x.prev = null;
    }
    if (next == null) {
        last = prev;
    } else {
        last.prev = prev;
        x.next = null;
    }
    x.item = null;
    size --;
    modCount ++;
    return element;
}

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

private void checkElementIndex(int index) {
    if (index < 0 || index >= size) {
        throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
    }
}

  • 通过checkElementIndex方法校验索引index。

  • 通过unlink方法移除掉此节点。

remove(Object o)

public boolean remove(Object o) {
    if (o == null) {
        for (Node x = first; x != null; x = x.next) {
            if (x.item == null) {
                unlink(x);
                return true;
            }
        }
    } else {
        for (Node x = first; x != null; x = x.next) {
            if (o.equals(x.item)) {
                unlink(x);
                return true;
            }
        }
    }
    return false;
}

  • 先判断对象o是否为null。

  • 循环所有节点 判断每个节点的元素值是否和对象o相等；如果相等就移除掉该节点并返回true。

unlinkFirst(Node f)

private E unlinkFirst(Node f) {
    final E element = f.item;
    final Node next = f.next;
    f.item = null;
    f.next = null;
    first = next;
    if (next == null) {
        last = null;
    } else {
        next.prev = null;
    }
    size --;
    modCount ++;
    return element;
}

public E remove() {
    return removeFirst();
}

/** 移除集合头部元素，如果元素为空，抛出NoSuchElementException异常 **/
public E removeFirst() {
    final Node f = first;
    if (f == null) throw new NoSuchElementException();
    return unlinkFirst(f);
}

public E poll() {
    return pollFirst();
}

/** 移除集合头部元素，如果元素为空则返回null **/
public E pollFirst() {
    final Node f = first;
    return f == null ? null : unlinkFirst(f);
}

public E pop() {
    return removeFirst();
}

unlinkLast(Node l)

private E unlinkLast(Node l) {
    final E element = l.item;
    final Node prev = l.prev;
    l.item = null;
    l.prev = null;
    last = prev;
    if (prev == null) {
        first = null;
    } else {
        prev.next = null;
    }
    size --;
    modCount ++;
    return element;
}

/** 移除集合尾部元素，如果元素为空，抛出NoSuchElementException异常 **/
public E removeLast() {
    final Node l = last;
    if (l == null) throw new NoSuchElementException();
    return unlinkLast(l);
}

/** 移除集合尾部元素，如果元素为空则返回null **/
public E pollLast() {
    final Node l = last;
    return l == null ? null : unlinkLast(l);
}
元素查找

元素查找主要有以下几个方法：

  • 查找指定位置的元素；如：get(int index)。

  • 查找集合头部元素；如：element()、getFirst()、peek()、peekFirst()。

  • 查找集合尾部元素；如：getLast()、peekLast()。

get(int index)

public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}

getFirst()

public E element() {
    return getFirst();
}

/** 查找集合头部元素，如果元素为空，抛出NoSuchElementException异常 **/
public E getFirst() {
    final Node e = first;
    if (e == null) throw new NoSuchElementException();
    return e.item;
}

public E peek() {
    final Node node = first;
    return node == null ? null : node.item;
}

/** 查找集合头部元素，如果元素为空就返回null **/
public E peekFirst() {
    final Node node = first;
    return node == null ? null : node.item;
}

getLast()

/** 查找集合尾部元素，如果元素为空，抛出NoSuchElementException异常 **/
public E getLast() {
    final Node e = last;
    if (e == null) throw new NoSuchElementException();
    return e.item;
}

/** 查找集合尾部元素，如果元素为空就返回null **/
public E peekLast() {
    final Node node = last;
    return node == null ? null : node.item;
}
元素更新

元素更新只有一个方法：set(int index, E e)

set(int index, E element)

public E set(int index, E element) {
    checkElementIndex(index);
    //查询index位置的节点
    Node node = node(index);
    E oldValue = node.item;
    //设置为最新元素
    node.item = element
    return oldValue;
}

  • 先判断索引index是否越界

  • 获取节点node及原元素oldValue

  • 将节点node设置为新的元素element

  • 返回原元素oldValue。

关于如何用源码分析LinkedList就分享到这里了，希望以上内容可以对大家有一定的帮助，可以学到更多知识。如果觉得文章不错，可以把它分享出去让更多的人看到。


名称栏目：如何用源码分析LinkedList
文章位置：http://scyanting.com/article/poosih.html

其他资讯