java编程

java LinkedList数据结构

字号+ 作者:风潇潇 来源:原创 2017-03-30 15:33 我要评论( )

java链表数据结构,看了一下源码,画了个结构图记录一下

看了一下linkedlist的源码。看了java里面的linkedlist是个双向链表。
实际上里面有个自定义的数据结构叫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;
        }
    }

对应图中的圆。





具体操作不再解释,具体可以去看源码。
感觉java里面的源码还是写的不错,比如如下,它做了优化:
  /**
     * 返回index位置的元素
     */
    Node<E> node(int 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;
        }
    }

这里有个 size >> 1 。这是就是将size右移 一位。
size =3;
在电脑里,size是补码形式:
0000000000000000000000000000011
右移一位:
0000000000000000000000000000001
size =1,就相当于size/2 +1
但为啥不用size/2 +1 来算呢?因为size/2 在电脑里要做多次加法,而右移只要做一次。大大加快效率


转载请注明出处。

1.本站遵循行业规范,任何转载的稿件都会明确标注作者和来源;2.本站的原创文章,请转载时务必注明文章作者和来源,不尊重原创的行为我们将追究责任;3.作者投稿可能会经我们编辑修改或补充。

相关文章
  • java的HashMap源码分析

    java的HashMap源码分析

    2017-03-31 12:26

网友点评
评论列表(网友评论仅供网友表达个人看法,并不表明本站同意其观点或证实其描述)