Java源码分析 – LinkedList双向链表源码分析
本文由发表于6年前 | Java基础 | 评论数 2 |  被围观 11,454 views+

LinkedList就传说中的双向链表了。是List 接口的链接列表实现。实现所有可选的列表操作,并且允许所有元素(包括 null)。除了实现 List 接口外,LinkedList 类还为在列表的开头及结尾 get、remove 和 insert 元素提供了统一的命名方法。这些操作允许将链接列表用作堆栈、队列或双端队列。

查看LinkedList的构造函数:
/**
     * Constructs an empty list.
     */
    public LinkedList() {
        header.next = header.previous = header;
}

这里的header变量的定义如下:

private transient Entry<E> header = new Entry<E>(null, null, null);

表示双向循环链表的头结点。其中的Entry定义了双向链表的结构:

private static class Entry<E> {
	E element;
	Entry<E> next;
	Entry<E> previous;

	Entry(E element, Entry<E> next, Entry<E> previous) {
	    this.element = element;
	    this.next = next;
	    this.previous = previous;
	}
}

Entry中包括数据元素、前续结点和后续结点。

构造函数即是初始化一个只包含header头结点一个元素的双向链表。

可以得出:LinkedList实质上就是一个双向链表,并把header作为头结点。
查看LinkedList的add(E)方法:
public boolean add(E e) {
	addBefore(e, header);
        return true;
}

add(E)方法主要指向了addBefore(E, Entry)函数:

private Entry<E> addBefore(E e, Entry<E> entry) {
	Entry<E> newEntry = new Entry<E>(e, entry, entry.previous);
	newEntry.previous.next = newEntry;
	newEntry.next.previous = newEntry;
	size++;
	modCount++;
	return newEntry;
}

这个方法中传入的第二个参数entry为header头结点,表示把元素插入到header头结点之前。然后后两句分别表示设置前续结点的后续结点和后续结点的前续结点。以便连接成双向链表。

可以得出:LinkedList的add(E)方法把新结点插入到header头结点之前,即列表的结尾。
查看LinkedList的set(int, E)方法:
/**
     * Replaces the element at the specified position in this list with the
     * specified element.
     *
     * @param index index of the element to replace
     * @param element element to be stored at the specified position
     * @return the element previously at the specified position
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */
    public E set(int index, E element) {
        Entry<E> e = entry(index);
        E oldVal = e.element;
        e.element = element;
        return oldVal;
}

这个函数主要是设置某个索引位置的结点。首先调用了entry(int)方法:

/**
     * Returns the indexed entry.
     */
    private Entry<E> entry(int index) {
        if (index < 0 || index >= size)
            throw new IndexOutOfBoundsException("Index: "+index+
                                                ", Size: "+size);
        Entry<E> e = header;
        if (index < (size >> 1)) {
            for (int i = 0; i <= index; i++)
                e = e.next;
        } else {
            for (int i = size; i > index; i--)
                e = e.previous;
        }
        return e;
}

这里首先判断需要设置的位置是否越界,如果越界则抛出异常。然后通过循环找到需要替换的结点。

接下来回到set(int ,E)函数,把旧的结点替换成新的结点,并返回旧的结点。

可以得出:set(int ,E)方法需要循环遍历链表,时间开销比较大。
查看LinkedList的push(E)方法:
/**
     * Pushes an element onto the stack represented by this list.  In other
     * words, inserts the element at the front of this list.
     *
     * <p>This method is equivalent to {@link #addFirst}.
     *
     * @param e the element to push
     * @since 1.6
     */
    public void push(E e) {
        addFirst(e);
}

push(E)方法主要调用了addFirst(E)方法:

/**
     * Inserts the specified element at the beginning of this list.
     *
     * @param e the element to add
     */
    public void addFirst(E e) {
	addBefore(e, header.next);
}

这里继续调用addBefore(E, Entity)表示把新节点插入到header头结点之后。

可以得出:push(E)方法主要是把新节点插入到header头结点之后。
查看LinkedList的pop()方法:
/**
     * Pops an element from the stack represented by this list.  In other
     * words, removes and returns the first element of this list.
     *
     * <p>This method is equivalent to {@link #removeFirst()}.
     *
     * @return the element at the front of this list (which is the top
     *         of the stack represented by this list)
     * @throws NoSuchElementException if this list is empty
     * @since 1.6
     */
    public E pop() {
        return removeFirst();
}

这里继续调用了removeFirst()方法:

/**
     * Removes and returns the first element from this list.
     *
     * @return the first element from this list
     * @throws NoSuchElementException if this list is empty
     */
    public E removeFirst() {
	return remove(header.next);
}

这里继续调用remove(Entry<E>)方法:

/**
     * Retrieves and removes the head (first element) of this list.
     *
     * @return the head of this list
     * @throws NoSuchElementException if this list is empty
     * @since 1.5
     */
    private E remove(Entry<E> e) {
	if (e == header)
	    throw new NoSuchElementException();

        E result = e.element;
	e.previous.next = e.next;
	e.next.previous = e.previous;
        e.next = e.previous = null;
        e.element = null;
	size--;
	modCount++;
        return result;
}

在调用remove(Entry<E>)方法时,传入了header的下一个结点。如果传入的下一个结点是header的话,表示此事链表中只有一个结点header,此时抛出异常。如果找到则删除该节点(注意这里双向链表删除结点时的步骤),并返回被删除的结点。

可以得出:pop()方法删除的是header头结点之后的结点,并返回被删除的结点。
★ LinkedList实质上就是一个双向链表,并把header作为头结点。
★ LinkedList的add(E)方法把新结点插入到header头结点之前。
★ set(int ,E)方法需要循环遍历链表,时间开销比较大。
★ push(E)方法主要是把新节点插入到header结点之前
★ pop()方法删除的是header头结点之后的结点,并返回被删除的结点。
除了文章中有特别说明,均为IT宅原创文章,转载请以链接形式注明出处。
本文链接:http://www.itzhai.com/java-source-code-analysis-linkedlist-doubly-linked-list-source-code-analysis.html
arthinking Java技术交流群:280755654,入门群:428693174 more
分享到:
 
2011 10/11
文章评论
    2条评论
  1. Ranger 2014年04月15日10:34:31  #-49楼 回复 回复

    在push()中说到,”这里继续调用addBefore(E, Entity)表示把新节点插入到header头结点之后。”
    然后总结中说,“push(E)方法主要是把新节点插入到header结点之前”

    想了一会才明白。

    既然把LinkedList当作Stack,就只有一个出入口,就是FirstElement,所以push()和pop()都以从head.next 为操作对象。

给我留言

有人回复时邮件通知我
Java基础的相关文章
随机文章 本月热门 热评
1 Java基础笔记 – 字符流分类详细介绍和各种字符流类介绍与使用 字符集 2011/10/22
2 jQuery中使用正则表达式验证电子邮件 2011/5/11
3 JUnit的使用和常用注解 2012/9/14
4 Android中的常用控件及其基本用法 2011/7/12
5 Servlet.service() for servlet jsp threw exception,NullPointerException 2011/7/27
6 UML笔记 OOAD面向对象的分析和设计介绍 2011/10/9
友情推荐 更多
破博客 文官洗碗安天下,武将打怪定乾坤。多么美好的年代,思之令人泪落。
Mr.5's Life 白天是一名程序员,晚上就是个有抱负的探索者
行知-追寻技术之美 关注大数据,分布式系统
我爱编程 编程成长轨迹
Cynthia's Blog 学习笔记 知识总结 思考感悟
 
猜您喜欢
欢迎关注我的公众号 IT宅
关于IT宅 文章归档

IT宅中的文章除了标题注明转载或有特别说明的文章,均为IT宅的技术知识总结,学习笔记或随笔。如果喜欢,请使用文章下面提供的分享组件。转载请注明出处并加入文章的原链接。 感谢大家的支持。

联系我们:admin@itzhai.com

Theme by arthinking. Copyright © 2011-2015 IT宅.com 保留所有权利.