Go语言视频零基础入门到精通

javalearner

1.先看下LinkedList 的继承关系：

   
   
    2. 我们看到其主要实现了List,Queue接口，通过继承一个模板类AbstractSequentialList来实现链表，首先看下成员变量：
        private transient Entry<E> header = new Entry<E>(null, null, null);
    private transient int size = 0;
                        [/code]
    可以看到，有两个成员变量，一个是Entry-静态内部类,还有一个size，代表链表的实际大小，看下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;
        }
    }[/code]
    是一个静态内部类，包含三个成员变量，element-数据项，next-指向下一条数据项，previous-指向前一条数据项，可以看出这是一个双向链接，每个节点
    都会指向前一个节点和后一个节点。
    这里简要说明一下为什么要使用静态内部类：
    摘自网络：
   
     静态内部类的实例不会自动持有外部类的特定实例的引用, 因此在创建内部类的实例时, 不必创建外部类的实例.
      静态内部类可以直接访问外部类的静态成员, 如果要访问外部类的实例成员, 就必须通过外部类的实例去访问
     静态内部类中可以定义静态成员和实例成员
      客户类可以通过完整的类名直接访问静态内部类的静态成员.  那这里，我认为是方便外部类访问，同时因为不包含任何方法，可以不用拿出来单独形成一个类，其他的好处，暂时还没看出来:( 下边重点看下几个方法的实现： 增加一条记录，add(E o)，实现代码：       public boolean add(E o) {
        addBefore(o, header);
        return true;
    }[/code] 内部调用了addBefore，再看addBefore的实现方式：     private Entry<E> addBefore(E o, Entry<E> e) {[/code]         //创建一个新的Entry实例
        Entry<E> newEntry = new Entry<E>(o, e, e.previous);[/code]         //将header前一条数据的next指向newEntry，同时把header的previous指向newEntry,
        newEntry.previous.next = newEntry;
        newEntry.next.previous = newEntry;[/code]         //长度和修改计数递增
        size++;
        modCount++;
        return newEntry;
    }[/code]  在指定位置添加：     public void add(int index, E element) {
        addBefore(element, (index==size ? header : entry(index)));
    }[/code]传递参数为：待添加的数据项O和header引用，详细分析参见注释，这里我们可以清晰的看到如何在一个链表结构中添加一条记录。 删除一条记录，remove(Object c)：  public boolean remove(Object o) {
     //判断插入数据项是否为null
        if (o==null) {
            for (Entry<E> e = header.next; e != header; e = e.next) {
                if (e.element==null) {
                    remove(e);
                    return true;
                }
            }
        } else {
            for (Entry<E> e = header.next; e != header; e = e.next) {
                if (o.equals(e.element)) {
                    remove(e);
                    return true;
                }
            }
        }
        return false;
    }[/code] 再看 remove(e)方法：  private E remove(Entry<E> e) {
   if (e == header)
       throw new NoSuchElementException();
       //提取待删除数据作为返回值
          E result = e.element;
          /*将待删除数据的next付给前一条数据项的next
           * 将待删除数据的previous指向后一条数据previous
           * 同时释放待删除数据项的next和previous链接，是否element
           */
         
   e.previous.next = e.next;
   e.next.previous = e.previous;
          e.next = e.previous = null;
          e.element = null;
          //总条数size和修改计数递减
   size--;
   modCount++;
          return result;
}[/code] 这里需要注意的是我们需要释放待删除节点的next和previous链接 ，以便于JVM在适当的时候进行垃圾回收。 获取数据,get(int index)：   public E get(int index) {
        return entry(index).element;
    }[/code] 我们看下entry方法：           private Entry<E> entry(int index) {
                  //判断边界--前置条件判断
                if (index < 0 || index >= size)
                    throw new IndexOutOfBoundsException("Index: "+index+
                                               ", Size: "+size);
                //如果index小于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;
            }[/code]这里我们看到在链表中取值时，需要遍历整个链表，相对于ArrayList的随机访问，会有所缓慢 最后看下contails(Object o)     public boolean contains(Object o) {
        return indexOf(o) != -1;
    }[/code]  看下indexOf(Object c)  public int indexOf(Object o) {
                int index = 0;
                if (o==null) {
                    for (Entry e = header.next; e != header; e = e.next) {
                        if (e.element==null)
                            return index;
                        index++;
                    }
                } else {
                    for (Entry e = header.next; e != header; e = e.next) {
                        if (o.equals(e.element))
                            return index;
                        index++;
                    }
                }
                return -1;
            }[/code]  这里分两种情况进行遍历，跟删除是相同的。 3.典型应用： 暂无 4，优点与缺点 优点： LinkedList的中间插入或删除一个元素的开销是固定的 缺点：  LinkedList不支持高效的随机元素访问 最后，我感觉平时做项目ArrayList还是相对比较常用，LinkedList很少用，不知道有没有人在实际项目中使用过LinkedList ，切实的体会 到两者之间的差异，而不是向我最后分析的优缺点那样 都是些理论写的说辞，希望大家补充，谢谢。   
   
   
   
     
     
     大小: 21.8 KB  
     
     
     查看图片附件