精华内容
下载资源
问答
  • LinkedList详解

    2021-01-26 21:09:42
    LinkedList详解 LinkedList是List接口的一个主要的实现类之一。以java8为例来了解一下LinkedList的源码实现 继承关系 public class LinkedList<E> extends AbstractSequentialList<E>

    原文链接http://zhhll.icu/2021/01/04/java%E5%9F%BA%E7%A1%80/%E9%9B%86%E5%90%88/LinkedList%E8%AF%A6%E8%A7%A3/

    LinkedList详解

    LinkedList是List接口的一个主要的实现类之一。以java8为例来了解一下LinkedList的源码实现

    继承关系

    public class LinkedList<E>
        extends AbstractSequentialList<E>
        implements List<E>, Deque<E>, Cloneable, java.io.Serializable
    

    LinkedList

    继承了AbstractSequentialList,实现了List接口、Deque接口、Cloneable接口、Serializable接口

    关键变量

    /**
    * 链表的长度
    */
    transient int size = 0;
    
    /**
     * 头节点
     * Invariant: (first == null && last == null) ||
     *            (first.prev == null && first.item != null)
     */
    transient Node<E> first;
    
    /**
     * 尾结点
     * Invariant: (first == null && last == null) ||
     *            (last.next == null && last.item != null)
     */
    transient Node<E> last;
    
    // 这里用到了一个内部类Node,看到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;
      }
    }
    

    构造器

    // 无参默认构造器
    public LinkedList() {
    }
    
    /**
     * 传入一个集合作为参数
     */
    public LinkedList(Collection<? extends E> c) {
        this();
        addAll(c);
    }
    
    public boolean addAll(Collection<? extends E> c) {
      return addAll(size, c);
    }
    
    public boolean addAll(int index, Collection<? extends E> c) {
      // 检查是否越界
      checkPositionIndex(index);
    
      Object[] a = c.toArray();
      // 新增元素的数量
      int numNew = a.length;
      if (numNew == 0)
        return false;
    	// 前置节点和后置节点
      Node<E> pred, succ;
      // index == size时表示是从链表尾部添加元素,所以前置节点为当前链表的尾结点
      if (index == size) {
        succ = null;
        pred = last;
      } else { // 不是从链表尾部添加,需要修改前置节点和后置节点
        succ = node(index);
        pred = succ.prev;
      }
    
      for (Object o : a) {
        @SuppressWarnings("unchecked") E e = (E) o;
        Node<E> newNode = new Node<>(pred, e, null);
        // 前置节点为null,表示这是头节点
        if (pred == null)
          first = newNode;
        else
          pred.next = newNode;
        pred = newNode;
      }
    	// succ == null,说明是从尾部添加的,将最后一个节点赋给尾结点
      if (succ == null) {
        last = pred;
      } else {
        pred.next = succ;
        succ.prev = pred;
      }
    
      size += numNew;
      modCount++;
      return true;
    }
    
    // 获取index位置的节点
    Node<E> node(int index) {
      // assert isElementIndex(index);
    	// index小于链表长度的一半,从链表头部开始遍历
      if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++)
          x = x.next;
        return x;
      } else { // index不小于链表长度的一半,从链表尾部开始遍历
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
          x = x.prev;
        return x;
      }
    }
    
    

    add方法

    // 逻辑比较简单,与上边addAll类似,一通插
    public void add(int index, E element) {
        checkPositionIndex(index);
    		// index == size表示在链表尾部添加
        if (index == size)
            linkLast(element);
        else // 否则在中间插入  先找到index所在位置的节点
            linkBefore(element, node(index));
    }
    
    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++;
    }
    
    void linkBefore(E e, Node<E> succ) {
      // assert succ != null;
      final Node<E> pred = succ.prev;
      final Node<E> newNode = new Node<>(pred, e, succ);
      succ.prev = newNode;
      if (pred == null)
      	first = newNode;
      else
      	pred.next = newNode;
      size++;
      modCount++;
    }
    

    remove方法

    LinkedList的remove方法比较

    public E remove(int index) {
      	// 检测该索引位置是否符合要求  index >= 0 && index < size
        checkElementIndex(index);
        return unlink(node(index));
    }
    
    // 找到当前索引位置的节点
    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;
      }
    }
    
    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;
    	// 前驱节点为null,表示为头节点,头节点指向后继节点即可
      if (prev == null) {
        first = next;
      } else {
        // 前驱节点的后继节点指向该元素的后继节点
        prev.next = next;
        x.prev = null;
      }
    	// 后继节点为null,表示为尾节点,尾节点指向前驱节点即可
      if (next == null) {
        last = prev;
      } else {
        // 后继节点的前驱节点指向该元素的前驱节点
        next.prev = prev;
        x.next = null;
      }
    
      x.item = null;
      size--;
      modCount++;
      return element;
    }
    

    迭代器

    LinkedList使用的迭代器是其父类AbstractSequentialList中的iterator方法

    // AbstractSequentialList类方法
    public Iterator<E> iterator() {
        return listIterator();
    }
    
    // LinkedList类方法
    public ListIterator<E> listIterator(int index) {
      checkPositionIndex(index);
      return new ListItr(index);
    }
    
    //  与ArrayList的迭代器不同的是,ArrayList的迭代器实现的是Iterator接口 而LinkedList为ListIterator接口,相当于ArrayList的listIterator()方法
    //  Iterator只能向前遍历,ListIterator可以向前也可以向后
    private class ListItr implements ListIterator<E> {
        private Node<E> lastReturned;
        private Node<E> next;
        private int nextIndex;
        private int expectedModCount = modCount;
    
        ListItr(int index) {
            // assert isPositionIndex(index);
            next = (index == size) ? null : node(index);
            nextIndex = index;
        }
    
        public boolean hasNext() {
            return nextIndex < size;
        }
    
        public E next() {
            checkForComodification();
            if (!hasNext())
                throw new NoSuchElementException();
    
            lastReturned = next;
            next = next.next;
            nextIndex++;
            return lastReturned.item;
        }
    
        public boolean hasPrevious() {
            return nextIndex > 0;
        }
    
        public E previous() {
            checkForComodification();
            if (!hasPrevious())
                throw new NoSuchElementException();
    
            lastReturned = next = (next == null) ? last : next.prev;
            nextIndex--;
            return lastReturned.item;
        }
    
        public int nextIndex() {
            return nextIndex;
        }
    
        public int previousIndex() {
            return nextIndex - 1;
        }
    
        public void remove() {
            checkForComodification();
            if (lastReturned == null)
                throw new IllegalStateException();
    
            Node<E> lastNext = lastReturned.next;
            unlink(lastReturned);
            if (next == lastReturned)
                next = lastNext;
            else
                nextIndex--;
            lastReturned = null;
            expectedModCount++;
        }
    
        public void set(E e) {
            if (lastReturned == null)
                throw new IllegalStateException();
            checkForComodification();
            lastReturned.item = e;
        }
    
        public void add(E e) {
            checkForComodification();
            lastReturned = null;
            if (next == null)
                linkLast(e);
            else
                linkBefore(e, next);
            nextIndex++;
            expectedModCount++;
        }
    
        public void forEachRemaining(Consumer<? super E> action) {
            Objects.requireNonNull(action);
            while (modCount == expectedModCount && nextIndex < size) {
                action.accept(next.item);
                lastReturned = next;
                next = next.next;
                nextIndex++;
            }
            checkForComodification();
        }
    
        final void checkForComodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }
    }
    

    由于本身的博客百度没有收录,博客地址http://zhhll.icu

    展开全文
  • Linkedlist详解

    2020-10-31 16:05:24
    LinkedList 是 Java 集合中比较常用的数据结构,与 ArrayList 一样,实现了 List 接口,只不过 ArrayList 是基于数组实现的,而 LinkedList 是基于链表实现的。所以 LinkedList 插入和删除方面要优于 ArrayList,而...

    一. 概述

    LinkedList 是 Java 集合中比较常用的数据结构,与 ArrayList 一样,实现了 List 接口,只不过 ArrayList 是基于数组实现的,而 LinkedList 是基于链表实现的。所以 LinkedList 插入和删除方面要优于 ArrayList,而随机访问上则 ArrayList 性能更好。
    除了 LIst 接口之外,LinkedList 还实现了 Deque,Cloneable,Serializable 三个接口。这说明该数据结构支持队列,克隆和序列化操作的。与 ArrayList 一样,允许 null 元素的存在,且是不支持多线程的。
    属性

    LinkedList 提供了以下三个成员变量。size,first,last。

    transient Node<E> first;
    transient Node<E> last;
    
    

    其中 size 为 LinkedList 的大小,first 和 last 分别为链表的头结点和尾节点。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;
        }
    }
    

    Node 是 LInkedList 的内部类,定义了存储的数据元素,前一个节点和后一个节点,典型的双链表结构。
    构造方法

    public LinkedList() {}
    public LinkedList(Collection<? extends E> c) {
        this();
        addAll(c);
    }
    
    

    LinkedList 提供了两个构造方法:LinkedList() 和 LinkedList(Collection<? extends E> c)。
    LinkedList() 仅仅构造一个空的列表,没有任何元素。size = 0。first 和 last 都为 null。
    后一个构造方法构造一个包含指定 Collection 中所有元素的列表,该构造方法首先会调用空的构造方法,然后通过 addAll() 的方式把 Collection 中的所有元素添加进去。

    调用 addAll() 方法,传入当前的节点个数 size,此时 size 为
    
    检查 index 是否越界
    
    将 collection 转换成数组
    
    遍历数组,将数组里面的元素创建为节点,并按照顺序连起来。
    
    修改当前的节点个数 size 的值
    
    操作次数 modCount 自增 1.
    
    public boolean addAll(Collection<? extends E> c) {
        return addAll(size, c);
    }
    public boolean addAll(int index, Collection<? extends E> c) {
        checkPositionIndex(index);
        Object[] a = c.toArray();
        int numNew = a.length;
        if (numNew == 0)
            return false;
        Node<E> pred, succ;
        if (index == size) {
            succ = null;
            pred = last;
        } else {
            succ = node(index);
            pred = succ.prev;
        }
        for (Object o : a) {
            @SuppressWarnings("unchecked") E e = (E) o;
            Node<E> newNode = new Node<>(pred, e, 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;
    }
    
    

    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++;
    }
    
    

    add 方法直接调用了 linkLast 方法,而 linkLast 方法是不对外开放的。该方法做了三件事情,新增一个节点,改变其前后引用,将 size 和 modCount 自增 1。其中 modCount 是记录对集合操作的次数。
    在指定的位置插入元素

    public void add(int index, E element) {
        checkPositionIndex(index);
        if (index == size)
            linkLast(element);
        else
            linkBefore(element, node(index));
    }
    private void checkPositionIndex(int index) {
        if (!isPositionIndex(index))
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
    private boolean isPositionIndex(int index) {
        return index >= 0 && index <= size;
    }
    void linkBefore(E e, Node<E> succ) {
        // assert succ != null;
        final Node<E> pred = succ.prev;
        final Node<E> newNode = new Node<>(pred, e, succ);
        succ.prev = newNode;
        if (pred == null)
            first = newNode;
        else
            pred.next = newNode;
        size++;
        modCount++;
    }
    
    

    首先检查下标是否越界,然后判断如果 index == size 则添加到末尾,否则将该元素插入的 index 的位置。其中 node(index) 是获取 index 位置的节点,linkBefore 负责把元素 e 插入到 succ 之前。

    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;
        }
    }
    
    

    可以看出 node() 方法这里写的还是挺赞的,不是傻乎乎的从头到尾或者从尾到头遍历链表,而是将 index 与 当前链表的一半做对比,比一半小从头遍历,比一半大从后遍历。对于数据量很大时能省下不少时间。
    get 操作

    很简单,首先获取节点,然后返回节点的数据即可。

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

    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;
    }
    
    

    先检查下标是否越界,然后调用 unlink 释放节点。
    移除指定元素

    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;
    }
    
    

    判断要移除的元素是否为 null,然后在遍历链表,找到钙元素第一次出现的位置,移除并返回 true。
    像其他的常用方法如:getFirst, getLast, removeFirst, removeLast, addFirst, addLast 等都很简单,扫一眼源码就能懂,我这里就不写了。

    迭代器

    LInkedList 的 iterator() 方法是在其父类 AbstractSequentialList 中定义的,最终一路 debug 到 LinkedList 类这里。其中 index 为 零。

    public ListIterator<E> listIterator(int index) {
        checkPositionIndex(index);
        return new ListItr(index);
    }
    
    

    我们来看看 ListItr。

    private Node<E> lastReturned;
        private Node<E> next;
        private int nextIndex;
        private int expectedModCount = modCount;
        ListItr(int index) {
            // assert isPositionIndex(index);
            next = (index == size) ? null : node(index);
            nextIndex = index;
        }
        public boolean hasNext() {
            return nextIndex < size;
        }
        public E next() {
            checkForComodification();
            if (!hasNext())
                throw new NoSuchElementException();
            lastReturned = next;
            next = next.next;
            nextIndex++;
            return lastReturned.item;
        }
         final void checkForComodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }
    }
    
    

    总结
    1、从源码可以看出 LinkedList 是基于链表实现的。如下图:

    2、在查找和删除某元素时,区分该元素为 null和不为 null 两种情况来处理,LinkedList 中允许元素为 null。

    3、基于链表实现不存在扩容问题。

    4、查找时先判断该节点位于前半部分还是后半部分,加快了速度

    5、因为基于链表,所以插入删除极快,查找比较慢。

    6、实现了栈和队列的相关方法,所以可作为栈,队列,双端队列来用。

    展开全文
  • LinkedList 详解

    2019-03-29 23:44:56
    LinkedList与ArrayList一样实现List接口,只是ArrayList是List接口的大小可变数组的实现,LinkedList是List接口链表的实现。 基于链表实现的方式使得LinkedList在插入和删除时更优于ArrayList,而随机访问则比...

    (注:本文内容基于JDK1.6)

    一、LinkedList概述:

    LinkedList与ArrayList一样实现List接口,只是ArrayList是List接口的大小可变数组的实现,LinkedList是List接口链表的实现。

    基于链表实现的方式使得LinkedList在插入和删除时更优于ArrayList,而随机访问则比ArrayList逊色些。

    LinkedList实现所有可选的列表操作,并允许所有的元素包括null。

    除了实现 List 接口外,LinkedList 类还为在列表的开头及结尾 get、remove 和 insert 元素提供了统一的命名方法。这些操作允许将链接列表用作堆栈、队列或双端队列。

    此类实现 Deque 接口,为 add、poll 提供先进先出队列操作,以及其他堆栈和双端队列操作。

    所有操作都是按照双重链接列表的需要执行的。

    在列表中编索引的操作将从开头或结尾遍历列表(从靠近指定索引的一端)。

    同时,与ArrayList一样此实现不是同步的。

    二、源码分析:

    LinkedList的定义:
    public class LinkedList<E>
        extends AbstractSequentialList<E>
        implements List<E>, Deque<E>, Cloneable, java.io.Serializable
    

    从这段代码中我们可以清晰地看出LinkedList继承AbstractSequentialList,实现List、Deque、Cloneable、Serializable。

    其中AbstractSequentialList提供了 List 接口的骨干实现,从而最大限度地减少了实现受“连续访问”数据存储(如链接列表)支持的此接口所需的工作,从而以减少实现List接口的复杂度。

    Deque一个线性 collection,支持在两端插入和移除元素,定义了双端队列的操作。

    在LinkedList中提供了两个基本属性size、header。

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

    其中size表示的LinkedList的大小,header表示链表的表头,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对象的源代码,Entry为LinkedList的内部类,它定义了存储的元素和该元素的前一个元素、后一个元素,这是典型的双向链表定义方式。

    来看 LinkedList的构造方法::

    public LinkedList() {
        header.next = header.previous = header;
    }
    public LinkedList(Collection<? extends E> c) {
        this();
        addAll(c);
    }
    

    LinkedList提供了两个构造方法。

    第一个构造方法不接受参数,只是将header节点的前一节点和后一节点都设置为自身(注意,这个是一个双向循环链表,如果不是循环链表,空链表的情况应该是header节点的前一节点和后一节点均为null),这样整个链表其实就只有header一个节点,用于表示一个空的链表。

    第二个构造方法接收一个Collection参数c,调用第一个构造方法构造一个空的链表,之后通过addAll将c中的元素全部添加到链表中。来看addAll的内容。

    public boolean addAll(Collection<? extends E> c) {
        return addAll(size, c);
    }
    
    // index参数指定collection中插入的第一个元素的位置
    public boolean addAll(int index, Collection<? extends E> c) {
        // 插入位置超过了链表的长度或小于0,报IndexOutOfBoundsException异常
        if (index < 0 || index > size)
            throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);
        Object[] a = c.toArray();
    	int numNew = a.length;
    	
    	// 若需要插入的节点个数为0则返回false,表示没有插入元素
        if (numNew==0)
            return false;
        modCount++;
        
        // 保存index处的节点。插入位置如果是size,则在头结点前面插入,否则获取index处的节点
    	Entry<E> successor = (index==size ? header : entry(index));
    
    	// 获取前一个节点,插入时需要修改这个节点的next引用
    	Entry<E> predecessor = successor.previous;
    
    	// 按顺序将a数组中的第一个元素插入到index处,将之后的元素插在这个元素后面
        for (int i=0; i<numNew; i++) {
    		// 结合Entry的构造方法,这条语句是插入操作,相当于C语言中链表中插入节点并修改指针
            Entry<E> e = new Entry<E>((E)a[i], successor, predecessor);
            // 插入节点后将前一节点的next指向当前节点,相当于修改前一节点的next指针
            predecessor.next = e;
            // 相当于C语言中成功插入元素后将指针向后移动一个位置以实现循环的功能
            predecessor = e;
    	}
    	// 插入元素前index处的元素链接到插入的Collection的最后一个节点
    	successor.previous = predecessor;
    	// 修改size
        size += numNew;
        return true;
    }
    

    构造方法中的调用了addAll(Collection<? extends E> c)方法,而在addAll(Collection<? extends E> c)方法中仅仅是将size当做index参数调用了addAll(int index,Collection<? extends E> c)方法。

    private Entry<E> entry(int index) {
    	if (index < 0 || index >= size)
    		throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);
    	Entry<E> e = header;
    	// 根据这个判断决定从哪个方向遍历这个链表 判断条件等价于index < size / 2
    	if (index < (size >> 1)) {
    		for (int i = 0; i <= index; i++)
    			e = e.next;
    	} else {
    		/**可以通过header节点向前遍历,说明这个一个循环双向链表。
    		*header的previous指向链表的最后一个节点。
    		*这也验证了构造方法中对于header节点的前后节点均指向自己的解释
    		*/
    		for (int i = size; i > index; i--)
    			e = e.previous;
            }
            return e;
        }
    

    结合上面代码中的注释及双向循环链表的知识,应该很容易理解LinkedList构造方法所涉及的内容。

    下面开始分析LinkedList的其他方法。

    add(E e):
    public boolean add(E e) {
         addBefore(e, header);
         return true;
     }
    

    从上面的代码可以看出,add(E e)方法只是调用了addBefore(E e,Entry entry)方法,并且返回true。

    addBefore(E e,Entry 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;
    }
    

    addBefore(E e,Entry entry)方法是个私有方法,所以无法在外部程序中调用(当然,这是一般情况,你可以通过反射上面的还是能调用到的)。

    addBefore(E e,Entry entry)先通过Entry的构造方法创建e的节点newEntry(包含了将其下一个节点设置为entry,上一个节点设置为entry.previous的操作,相当于修改newEntry的“指针”).

    之后修改插入位置后newEntry的前一节点的next引用和后一节点的previous引用,使链表节点间的引用关系保持正确。

    之后修改和size大小和记录modCount,然后返回新插入的节点。

    总结,addBefore(E e,Entry entry)实现在entry之前插入由e构造的新节点。而add(E e)实现在header节点之前插入由e构造的新节点。

    add(int index,E e):
    public void add(int index, E element) {
         addBefore(element, (index==size ? header : entry(index)));
     }
    

    也是调用了addBefore(E e,Entry entry)方法,只是entry节点由index的值决定。

    构造方法,addAll(Collection<? extends E> c),add(E e),addBefor(E e,Entry entry)方法可以构造链表并在指定位置插入节点,为了便于理解,下面给出插入节点的示意图。
    在这里插入图片描述

    addFirst(E e):
     public void addFirst(E e) {
         addBefore(e, header.next);
     }
    
    addLast(E e):
    public void addLast(E e) {
         addBefore(e, header);
     }
    

    看上面的示意图,结合addBefore(E e,Entry entry)方法,很容易理解addFrist(E e)只需实现在header元素的下一个元素之前插入,即示意图中的一号之前。

    addLast(E e)只需在实现在header节点前(因为是循环链表,所以header的前一个节点就是链表的最后一个节点)插入节点(插入后在2号节点之后)。

    clear():
    public void clear() {
    	Entry<E> e = header.next;
    	// e可以理解为一个移动的“指针”,因为是循环链表,所以回到header的时候说明已经没有节点了
    	while (e != header) {
        	// 保留e的下一个节点的引用
            Entry<E> next = e.next;
            // 接触节点e对前后节点的引用
            e.next = e.previous = null;
            // 将节点e的内容置空
            e.element = null;
            // 将e移动到下一个节点
            e = next;
    }
    	// 将header构造成一个循环链表,同构造方法构造一个空的LinkedList
    	header.next = header.previous = header;
    	// 修改size
        size = 0;
        modCount++;
    }
    

    上面代码中的注释已经足以解释这段代码的逻辑,需要注意的是提到的“指针”仅仅是概念上的类比,Java并不存在“指针”的概念,而只有引用,为了便于理解所以部分说明使用了“指针”。

    contains(Object o):
    public boolean contains(Object o) {
         return indexOf(o) != -1;
     }
    

    仅仅只是判断o在链表中的索引。先看indexOf(Object o)方法。

    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;
    }
    

    indexOf(Object o)判断o链表中是否存在节点的element和o相等,若相等则返回该节点在链表中的索引位置,若不存在则放回-1。

    contains(Object o)方法通过判断indexOf(Object o)方法返回的值是否是-1来判断链表中是否包含对象o。

    element():
    public E element() {
         return getFirst();
     }
    
    getFirst():
    public E getFirst() {
         if (size==0)
             throw new NoSuchElementException();
        return header.next.element;
     }
    

    element()方法调用了getFirst()返回链表的第一个节点的元素。

    为什么要提供功能一样的两个方法,像是包装了一下名字?

    其实这只是为了在不同的上下文“语境”中能通过更贴切的方法名调用罢了。

    get(int index):
    public E get(int index) {
         return entry(index).element;
     }
    

    get(int index)方法用于获得指定索引位置的节点的元素。它通过entry(int index)方法获取节点。entry(int index)方法遍历链表并获取节点,在上面有说明过,不再陈述。

    set(int index,E element):
    public E set(int index, E element) {
         Entry<E> e = entry(index);
         E oldVal = e.element;
         e.element = element;
         return oldVal;
     }
    

    先获取指定索引的节点,之后保留原来的元素,然后用element进行替换,之后返回原来的元素。

    getLast():
    public E getLast()  {
         if (size==0)
             throw new NoSuchElementException();
         return header.previous.element;
     }
    

    getLast()方法和getFirst()方法类似,只是获取的是header节点的前一个节点的元素。因为是循环链表,所以header节点的前一节点就是链表的最后一个节点。

    lastIndexOf(Object o):
    public int lastIndexOf(Object o) {
        int index = size;
        if (o==null) {
            for (Entry e = header.previous; e != header; e = e.previous) {
                index--;
                if (e.element==null)
                    return index;
            }
        } else {
            for (Entry e = header.previous; e != header; e = e.previous) {
                index--;
                if (o.equals(e.element))
                    return index;
            }
        }
        return -1;
    }
    

    因为查找的是last index,即最后一次出现的位置,所以采用由后向前的遍历方式。

    因为采用了有后向前的遍历,所以index被赋值为size,并且循环体内执行时都进行减操作。

    分两种情况判断是否存在,分别是null和不为空。

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

    在链表尾部插入元素。

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

    在链表开头插入元素。

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

    在链表末尾插入元素。

    上面这三个方法都只是调用了相应的add方法,同样只是提供了不同的方法名在不同的语境下使用。

    peek():
     public E peek() {
         if (size==0)
             return null;
         return getFirst();
     }
    
    peekFirst():
    public E peekFirst() {
         if (size==0)
             return null;
         return getFirst();
     }
    
    peekLast():
    public E peekLast() {
         if (size==0)
             return null;
         return getLast();
     }
    

    上面的三个方法也很简单,只是调用了对应的get方法。

    poll():
    public E poll() {
         if (size==0)
             return null;
         return removeFirst();
     }
    
    pollFirst():
    public E pollFirst() {
         if (size==0)
             return null;
         return removeFirst();
     }
    
    pollLast():
    public E pollLast() {
         if (size==0)
             return null;
         return removeLast();
     }
    

    poll相关的方法都是获取并移除某个元素。都是和remove操作相关。

    pop():
    public E pop() {
         return removeFirst();
     }
    
    push(E e):
    public void push(E e) {
         addFirst(e);
     }
    

    这两个方法对应栈的操作,即弹出一个元素和压入一个元素,仅仅是调用了removeFirst()和addFirst()方法。

    下面集中看remove相关操作的方法。

    remove():
    public E remove() {
         return removeFirst();
     }
    
    remove(int index):
    public E remove(int index) {
         return remove(entry(index));
     }
    
    remove(Object o):
    public boolean remove(Object o) {
        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;
    }
    
    removeFirst():
    public E removeFirst() {
         return remove(header.next);
     }
    
    removeLast():
    public E removeLast() {
         return remove(header.previous);
     }
    
    removeFirstOccurrence():
    public boolean removeFirstOccurrence(Object o) {
         return remove(o);
     }
    
    removeLastOccurence():
    public boolean removeLastOccurrence(Object o) {
        if (o==null) {
            for (Entry<E> e = header.previous; e != header; e = e.previous) {
                if (e.element==null) {
                    remove(e);
                    return true;
                }
            }
        } else {
            for (Entry<E> e = header.previous; e != header; e = e.previous) {
                if (o.equals(e.element)) {
                    remove(e);
                    return true;
                }
            }
        }
        return false;
    }
    

    几个remove方法最终都是调用了一个私有方法:remove(Entry e),只是其他简单逻辑上的区别。下面分析remove(Entry e)方法。

    private E remove(Entry<E> e) {
        if (e == header)
            throw new NoSuchElementException();
        // 保留将被移除的节点e的内容
    	E result = e.element;
    	// 将前一节点的next引用赋值为e的下一节点
        e.previous.next = e.next;
        // 将e的下一节点的previous赋值为e的上一节点
        e.next.previous = e.previous;
        // 上面两条语句的执行已经导致了无法在链表中访问到e节点,而下面解除了e节点对前后节点的引用
    	e.next = e.previous = null;
    	// 将被移除的节点的内容设为null
    	e.element = null;
    	// 修改size大小
        size--;
        modCount++;
        // 返回移除节点e的内容
        return result;
    }
    
    clone():
    public Object clone() {
        LinkedList<E> clone = null;
        try {
            clone = (LinkedList<E>) super.clone();
        } catch (CloneNotSupportedException e) {
            throw new InternalError();
        }
        clone.header = new Entry<E>(null, null, null);
        clone.header.next = clone.header.previous = clone.header;
        clone.size = 0;
        clone.modCount = 0;
        for (Entry<E> e = header.next; e != header; e = e.next)
            clone.add(e.element);
        return clone;
    }
    

    调用父类的clone()方法初始化对象链表clone,将clone构造成一个空的双向循环链表,之后将header的下一个节点开始将逐个节点添加到clone中。最后返回克隆的clone对象。

    toArray():
    public Object[] toArray() {
        Object[] result = new Object[size];
        int i = 0;
        for (Entry<E> e = header.next; e != header; e = e.next)
            result[i++] = e.element;
        return result;
    }
    

    创建大小和LinkedList相等的数组result,遍历链表,将每个节点的元素element复制到数组中,返回数组。

    toArray(T[] a):
    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 (Entry<E> e = header.next; e != header; e = e.next)
            result[i++] = e.element;
        if (a.length > size)
            a[size] = null;
        return a;
    }
    

    先判断出入的数组a的大小是否足够,若大小不够则拓展。

    这里用到了反射的方法,重新实例化了一个大小为size的数组。

    之后将数组a赋值给数组result,遍历链表向result中添加的元素。

    最后判断数组a的长度是否大于size,若大于则将size位置的内容设置为null,返回a。

    从代码中可以看出,数组a的length小于等于size时,a中所有元素被覆盖,被拓展来的空间存储的内容都是null;

    若数组a的length的length大于size,则0至size-1位置的内容被覆盖,size位置的元素被设置为null,size之后的元素不变。

    LinkedList的Iterator:

    除了Entry,LinkedList还有一个内部类:ListItr。

    ListItr实现了ListIterator接口,可知它是一个迭代器,通过它可以遍历修改LinkedList。在LinkedList中提供了获取ListItr对象的方法:listIterator(int index)。

    public ListIterator<E> listIterator(int index) {
         return new ListItr(index);
     }
    

    该方法只是简单的返回了一个ListItr对象。

    LinkedList中还有通过集成获得的listIterator()方法,该方法只是调用了listIterator(int index)并且传入0。

    下面详细分析ListItr。

    private class ListItr implements ListIterator<E> {
    // 最近一次返回的节点,也是当前持有的节点
        private Entry<E> lastReturned = header;
        // 对下一个元素的引用
        private Entry<E> next;
        // 下一个节点的index
        private int nextIndex;
        private int expectedModCount = modCount;
        // 构造方法,接收一个index参数,返回一个ListItr对象
        ListItr(int index) {
            // 如果index小于0或大于size,抛出IndexOutOfBoundsException异常
            if (index < 0 || index > size)
            throw new IndexOutOfBoundsException("Index: "+index+
                                ", Size: "+size);
            // 判断遍历方向
            if (index < (size >> 1)) {
            // next赋值为第一个节点
            next = header.next;
            // 获取指定位置的节点
            for (nextIndex=0; nextIndex<index; nextIndex++)
                next = next.next;
            } else {
    // else中的处理和if块中的处理一致,只是遍历方向不同
            next = header;
            for (nextIndex=size; nextIndex>index; nextIndex--)
                next = next.previous;
            }
        }
        // 根据nextIndex是否等于size判断时候还有下一个节点(也可以理解为是否遍历完了LinkedList)
        public boolean hasNext() {
            return nextIndex != size;
        }
        // 获取下一个元素
        public E next() {
            checkForComodification();
            // 如果nextIndex==size,则已经遍历完链表,即没有下一个节点了(实际上是有的,因为是循环链表,任何一个节点都会有上一个和下一个节点,这里的没有下一个节点只是说所有节点都已经遍历完了)
            if (nextIndex == size)
            throw new NoSuchElementException();
            // 设置最近一次返回的节点为next节点
            lastReturned = next;
            // 将next“向后移动一位”
            next = next.next;
            // index计数加1
            nextIndex++;
            // 返回lastReturned的元素
            return lastReturned.element;
        }
     
        public boolean hasPrevious() {
            return nextIndex != 0;
        }
        // 返回上一个节点,和next()方法相似
        public E previous() {
            if (nextIndex == 0)
            throw new NoSuchElementException();
     
            lastReturned = next = next.previous;
            nextIndex--;
            checkForComodification();
            return lastReturned.element;
        }
     
        public int nextIndex() {
            return nextIndex;
        }
     
        public int previousIndex() {
            return nextIndex-1;
        }
        // 移除当前Iterator持有的节点
        public void remove() {
                checkForComodification();
                Entry<E> lastNext = lastReturned.next;
                try {
                    LinkedList.this.remove(lastReturned);
                } catch (NoSuchElementException e) {
                    throw new IllegalStateException();
                }
            if (next==lastReturned)
                    next = lastNext;
                else
            nextIndex--;
            lastReturned = header;
            expectedModCount++;
        }
        // 修改当前节点的内容
        public void set(E e) {
            if (lastReturned == header)
            throw new IllegalStateException();
            checkForComodification();
            lastReturned.element = e;
        }
        // 在当前持有节点后面插入新节点
        public void add(E e) {
            checkForComodification();
            // 将最近一次返回节点修改为header
            lastReturned = header;
            addBefore(e, next);
            nextIndex++;
            expectedModCount++;
        }
        // 判断expectedModCount和modCount是否一致,以确保通过ListItr的修改操作正确的反映在LinkedList中
        final void checkForComodification() {
            if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        }
    }
    

    下面是一个ListItr的使用实例。

    LinkedList<String> list = new LinkedList<String>();
            list.add("First");
            list.add("Second");
            list.add("Thrid");
            System.out.println(list);
            ListIterator<String> itr = list.listIterator();
            while (itr.hasNext()) {
                System.out.println(itr.next());
            }
            try {
                System.out.println(itr.next());// throw Exception
            } catch (Exception e) {
                // TODO: handle exception
            }
            itr = list.listIterator();
            System.out.println(list);
            System.out.println(itr.next());
            itr.add("new node1");
            System.out.println(list);
            itr.add("new node2");
            System.out.println(list);
            System.out.println(itr.next());
            itr.set("modify node");
            System.out.println(list);
            itr.remove();
            System.out.println(list);
    

    运行结果:

    [First, Second, Thrid]
    First
    Second
    Thrid
    [First, Second, Thrid]
    First
    [First, new node1, Second, Thrid]
    [First, new node1, new node2, Second, Thrid]
    Second
    [First, new node1, new node2, modify node, Thrid]
    [First, new node1, new node2, Thrid]
    

    LinkedList还有一个提供Iterator的方法:descendingIterator()。

    该方法返回一个DescendingIterator对象。

    DescendingIterator是LinkedList的一个内部类。

    public Iterator<E> descendingIterator() {
         return new DescendingIterator();
     }
    

    下面分析详细分析DescendingIterator类。

    private class DescendingIterator implements Iterator {
        // 获取ListItr对象
    final ListItr itr = new ListItr(size());
    // hasNext其实是调用了itr的hasPrevious方法
        public boolean hasNext() {
            return itr.hasPrevious();
        }
    // next()其实是调用了itr的previous方法
        public E next() {
            return itr.previous();
        }
        public void remove() {
            itr.remove();
        }
    }
    

    从类名和上面的代码可以看出这是一个反向的Iterator,代码很简单,都是调用的ListItr类中的方法。

    原文转自:http://www.cnblogs.com/hzmark/archive/2012/12/25/LinkedList.html

    其他比较好的博客:

    https://blog.csdn.net/chenssy/article/details/18099417

    https://blog.csdn.net/sinat_36246371/article/details/53709625

    https://blog.csdn.net/i_lovefish/article/details/8042883

    展开全文
  • Linkedlist 详解

    2019-10-05 12:23:07
    Linkedlist基于链表的动态数组(双向链表): 可以被当作堆栈(后进先出)、队列(先进先出)或双端队列进行操作。 数据添加删除效率高,只需要改变指针指向即可,但是访问数据的平均效率低,需要对链表进行遍历...

    基本介绍

    Linkedlist基于链表的动态数组(双向链表):
    
        可以被当作堆栈(后进先出)、队列(先进先出)或双端队列进行操作。
    
        数据添加删除效率高,只需要改变指针指向即可,但是访问数据的平均效率低,需要对链表进行遍历。
    
        非同步,线程不安全。
    
        支持null元素、有顺序、元素可以重复
    
        不要使用普通for循环去遍历LinkedList,使用迭代器或者foreach循环(foreach循环的原理就是迭代器)去遍历LinkedList即可:
            这种方式是直接按照地址去找数据的,将会大大提升遍历LinkedList的效率。

    源码分析

    public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable {
    
        //实际大小
        transient int size = 0;
    
        //头节点
        transient Node<E> first;
    
        //尾节点
        transient Node<E> last;
    
        public LinkedList() {
        }
    
        public LinkedList(Collection<? extends E> c) {
            this();
            addAll(c);
        }
    
        //双向链表
        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;
            }
        }
    
        //添加在头节点
        private void linkFirst(E e) {
            //旧头节点
            final Node<E> f = first;
            //新节点的next指向旧头节点
            final Node<E> newNode = new Node<>(null, e, f);
            //头节点改成新节点
            first = newNode;
            //如果旧头节点为null,表示空链表,尾节点也指向新节点
            if (f == null)
                last = newNode;
            //旧头节点的prev指向新节点
            else
                f.prev = newNode;
            size++;
            modCount++;
        }
    
        //添加到链表尾部
        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++;
        }
    
        public void add(int index, E element) {
            //检查index是否合理
            checkPositionIndex(index);
            //如果index是size,则添加在尾部
            if (index == size)
                linkLast(element);
            else
                linkBefore(element, node(index));
        }
    
        //查找index处的节点
        Node<E> node(int index) {
            // assert isElementIndex(index);
    
            //如果index在左半边,则从头遍历(提到查找效率)
            if (index < (size >> 1)) {
                Node<E> x = first;
                for (int i = 0; i < index; i++)
                    x = x.next;
                return x;
            } else {
                //如果index在右半边,则从尾遍历(提到查找效率)
                Node<E> x = last;
                for (int i = size - 1; i > index; i--)
                    x = x.prev;
                return x;
            }
        }
    
        void linkBefore(E e, Node<E> succ) {
            // assert succ != null;
            //旧节点的前一个节点
            final Node<E> pred = succ.prev;
            //将新节点设置为:prev为旧节点的前一个节点,next为旧节点
            final Node<E> newNode = new Node<>(pred, e, succ);
            //旧节点的prev指向新节点
            succ.prev = newNode;
            //旧节点的前一个节点是空,表示旧节点是头节点,则重设头节点
            if (pred == null)
                first = newNode;
            //旧节点的前一个节点的next指向新节点
            else
                pred.next = newNode;
            size++;
            modCount++;
        }
    
        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;
        }
    
        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;    //帮助GC
            }
            //如果后是空,表示删除尾元素,前变成尾元素
            if (next == null) {
                last = prev;
            } else {
                //后的上一个变成前
                next.prev = prev;
                x.next = null;    //帮助GC
            }
    
            x.item = null;    //帮助GC
            size--;
            modCount++;
            return element;
        }
    
        public E getFirst() {
            final Node<E> f = first;
            if (f == null)
                throw new NoSuchElementException();
            return f.item;
        }
    
        public E get(int index) {
            checkElementIndex(index);
            return node(index).item;
        }
    }

    转载于:https://www.cnblogs.com/loveer/p/11533637.html

    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,452
精华内容 580
关键字:

linkedlist详解