辰砂

辰砂

关注
发信
关注(28)粉丝(399)

java集合之LinkedList

title: java集合之LinkedList
tags: java集合
author: 辰砂

一. LinkedList概述：

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

注意，此实现不是同步的。如果不存在这样的对象，则应该使用 Collections.synchronizedList 方法来“包装”该列表。最好在创建时完成这一操作，以防止对列表进行意外的不同步访问，如下所示：

 List list = Collections.synchronizedList(new LinkedList(...));

java集合之LinkedList-LMLPHP

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

LinkedList 是一个继承于AbstractSequentialList的双向链表。它也可以被当作堆栈、队列或双端队列进行操作。

LinkedList 实现 List 接口，能对它进行队列操作。

LinkedList 实现 Deque 接口，即能将LinkedList当作双端队列使用。

LinkedList 实现了Cloneable接口，即覆盖了函数clone()，能克隆。

LinkedList 实现java.io.Serializable接口，这意味着LinkedList支持序列化，能通过序列化去传输。

LinkedList 是非同步的

二.LinkedList的用法 (参考优秀博文)


public class LinkedListTest {
    public static void main(String[] args) {
        // 测试LinkedList的API
        testLinkedListAPIs() ;

        // 将LinkedList当作 LIFO(后进先出)的堆栈
        useLinkedListAsLIFO();

        // 将LinkedList当作 FIFO(先进先出)的队列
        useLinkedListAsFIFO();
    }

    /*
     * 测试LinkedList中部分API
     */
    private static void testLinkedListAPIs() {
        String val = null;
        //LinkedList llist;
        //llist.offer("10");
        // 新建一个LinkedList
        LinkedList llist = new LinkedList();
        //---- 添加操作 ----
        // 依次添加1,2,3
        llist.add("1");
        llist.add("2");
        llist.add("3");

        // 将“4”添加到第一个位置
        llist.add(1, "4");


        System.out.println("\nTest \"addFirst(), removeFirst(), getFirst()\"");
        // (01) 将“10”添加到第一个位置。  失败的话，抛出异常！
        llist.addFirst("10");
        System.out.println("llist:"+llist);
        // (02) 将第一个元素删除。        失败的话，抛出异常！
        System.out.println("llist.removeFirst():"+llist.removeFirst());
        System.out.println("llist:"+llist);
        // (03) 获取第一个元素。          失败的话，抛出异常！
        System.out.println("llist.getFirst():"+llist.getFirst());


        System.out.println("\nTest \"offerFirst(), pollFirst(), peekFirst()\"");
        // (01) 将“10”添加到第一个位置。  返回true。
        llist.offerFirst("10");
        System.out.println("llist:"+llist);
        // (02) 将第一个元素删除。        失败的话，返回null。
        System.out.println("llist.pollFirst():"+llist.pollFirst());
        System.out.println("llist:"+llist);
        // (03) 获取第一个元素。          失败的话，返回null。
        System.out.println("llist.peekFirst():"+llist.peekFirst());


        System.out.println("\nTest \"addLast(), removeLast(), getLast()\"");
        // (01) 将“20”添加到最后一个位置。  失败的话，抛出异常！
        llist.addLast("20");
        System.out.println("llist:"+llist);
        // (02) 将最后一个元素删除。        失败的话，抛出异常！
        System.out.println("llist.removeLast():"+llist.removeLast());
        System.out.println("llist:"+llist);
        // (03) 获取最后一个元素。          失败的话，抛出异常！
        System.out.println("llist.getLast():"+llist.getLast());


        System.out.println("\nTest \"offerLast(), pollLast(), peekLast()\"");
        // (01) 将“20”添加到第一个位置。  返回true。
        llist.offerLast("20");
        System.out.println("llist:"+llist);
        // (02) 将第一个元素删除。        失败的话，返回null。
        System.out.println("llist.pollLast():"+llist.pollLast());
        System.out.println("llist:"+llist);
        // (03) 获取第一个元素。          失败的话，返回null。
        System.out.println("llist.peekLast():"+llist.peekLast());



        // 将第3个元素设置300。不建议在LinkedList中使用此操作，因为效率低！
        llist.set(2, "300");
        // 获取第3个元素。不建议在LinkedList中使用此操作，因为效率低！
        System.out.println("\nget(3):"+llist.get(2));


        // ---- toArray(T[] a) ----
        // 将LinkedList转行为数组
        String[] arr = (String[])llist.toArray(new String[0]);
        for(String str:arr) {
            System.out.println("str:"+str);
        }

        // 输出大小
        System.out.println("size:"+llist.size());
        // 清空LinkedList
        llist.clear();
        // 判断LinkedList是否为空
        System.out.println("isEmpty():"+llist.isEmpty()+"\n");

    }

    /**
     * 将LinkedList当作 LIFO(后进先出)的堆栈
     */
    private static void useLinkedListAsLIFO() {
        System.out.println("\nuseLinkedListAsLIFO");
        // 新建一个LinkedList
        LinkedList stack = new LinkedList();

        // 将1,2,3,4添加到堆栈中
        stack.push("1");
        stack.push("2");
        stack.push("3");
        stack.push("4");
        // 打印“栈”
        System.out.println("stack:"+stack);

        // 删除“栈顶元素”
        System.out.println("stack.pop():"+stack.pop());

        // 取出“栈顶元素”
        System.out.println("stack.peek():"+stack.peek());

        // 打印“栈”
        System.out.println("stack:"+stack);
    }

    /**
     * 将LinkedList当作 FIFO(先进先出)的队列
     */
    private static void useLinkedListAsFIFO() {
        System.out.println("\nuseLinkedListAsFIFO");
        // 新建一个LinkedList
        LinkedList queue = new LinkedList();

        // 将10,20,30,40添加到队列。每次都是插入到末尾
        queue.add("10");
        queue.add("20");
        queue.add("30");
        queue.add("40");
        // 打印“队列”
        System.out.println("queue:"+queue);

        // 删除(队列的第一个元素)
        System.out.println("queue.remove():"+queue.remove());

        // 读取(队列的第一个元素)
        System.out.println("queue.element():"+queue.element());

        // 打印“队列”
        System.out.println("queue:"+queue);
    }

三.源码解读

1.数据结构

LinkedList 是一个双向链表。内部类 Node 是 LinkedList 中的基本数据结构，包含当前节点值，上一个节点得引用，和下个节点的引用。

// 链表中有多少个节点，默认为 0
transient int size = 0;
// 头节点
transient Node<E> first;
// 尾节点
transient Node<E> last;
    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集合之LinkedList-LMLPHP

2.构造方法

比较简单，默认无参构造，和一个 Collection 参数的构造（ 将里面元素按顺序前后连接，修改节点个数，并且操作次数 + 1 ）。

    public LinkedList() {
    }

    /**
     * Constructs a list containing the elements of the specified
     * collection, in the order they are returned by the collection's
     * iterator.
     *
     * @param  c the collection whose elements are to be placed into this list
     * @throws NullPointerException if the specified collection is null
     */
    public LinkedList(Collection<? extends E> c) {
        this();
        addAll(c);
    }

3.添加方法ADD

// 尾部插入
public boolean add(E e) {
    // 去为节点加
    linkLast(e);
    return true;
}
// 将指定的元素防止在链表的尾节点，以前的尾节点变成它前面的节点，如果上个尾节点为null，说明以前是的空链表。
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增加
    size++;
    modCount++;
}
add(int index, E element)
  public void add(int index, E element) {
  // 边界校验
      checkPositionIndex(index);
      if (index == size)
          linkLast(element);
      else
          linkBefore(element, node(index));
  }
  /**
   * Returns the (non-null) Node at the specified element index.
   */
  Node<E> node(int index) {
      // assert isElementIndex(index);
// 双链表可以分别从 头节点 或者尾节点开始遍历，计算它是在前面一半，还是在后面的位置，决定遍历方式。
// 这也是LinkedList 为什么要使用双向链表，提升了使用游标操作链表的效率。
      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;
      }
  }
  /**
   * Inserts element e before non-null Node succ.
   */
  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++;
  }

检查索引是否越界，虽然 ListedList 中没有索引概念；
如果 index 和 size 相同，则在尾节点上加上元素；
不相同的话，先去遍历链表查找到索引位置的节点，然后在它的前面插入节点。

java集合之LinkedList-LMLPHP

 1.s->prior=p->prior;
 2. p->prior->next=s;
 3. s->next=p;
 4. p->prior=s;

4.获取元素Get

public E get(int index) {
// 检查索引越界；
// 跟上面的一样，查找该索引位置的节点，然后获取它的元素。
    checkElementIndex(index);
    return node(index).item;
}

5.删除元素Remove

   public E remove() {
       return removeFirst();
   }
   // 移除头节点
   public E removeFirst() {
       final Node<E> f = first;
       if (f == null)
           throw new NoSuchElementException();
       return unlinkFirst(f);
   }
   // 参数 f 为头节点
// 将头节点指向 next 节点，如果 next节点 为 null 则链表 为 null ，链表大小减 1 ，修改次数记录加 1.
   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));
}
    /**
     * Unlinks non-null node 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;
        // 如果本节点为头节点，头节点指向next
        if (prev == null) {
            first = next;
        } else {
            // 不是头节点，则将前节点和后节点连接起来，然后删掉本节点的引用 GC
            prev.next = next;
            x.prev = null;
        }
        // 如果是尾节点，则将尾节点指向前节点
        if (next == null) {
            last = prev;
        } else {
            // 连接，双向链表，双方都有引用，删除自身的引用GC
            next.prev = prev;
            x.next = null;
        }
        // 删除自身 GC
        x.item = null;
        size--;
        modCount++;
        return element;
    }

// 遍历 equals 找出 node，然后调用 unlink(Node<E> x)
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;
    }

java集合之LinkedList-LMLPHP

6.更新元素Set

/**
*有索引，第一件事去检查索引是否越界；根据索引找出 node；
*替换 node 的元素，返回 该索引位置 Node 的旧元素的值。
*注意，Set 方法不增加LinkedList 的修改次数
*/
public E set(int index, E element) {
    checkElementIndex(index);
    Node<E> x = node(index);
    E oldVal = x.item;
    x.item = element;
    return oldVal;
}

7.清空clear()

//释放所有的元素，让他们直接无引用，垃圾回收器发现这些 node 元素是不可达的时候，释放内存。
// 数据恢复默认；修改次数记录加一。
public void clear() {
       // Clearing all of the links between nodes is "unnecessary", but:
       // - helps a generational GC if the discarded nodes inhabit
       //   more than one generation
       // - is sure to free memory even if there is a reachable Iterator
       for (Node<E> x = first; x != null; ) {
           Node<E> next = x.next;
           x.item = null;
           x.next = null;
           x.prev = null;
           x = next;
       }
       first = last = null;
       size = 0;
       modCount++;
   }

四、ArrayList和LinkedList比较

  1. ArrayList的实现是基于数组，LinkedList的实现是基于双向链表。

  2. 对于随机访问，ArrayList优于LinkedList

  3. 对于插入和删除操作，LinkedList优于ArrayList

  4. LinkedList比ArrayList更占内存，因为LinkedList的节点除了存储数据，还存储了两个引用，一个指向前一个元素，一个指向后一个元素。

参考

https://blog.wuwii.com/java-linkedlist.html#more

https://www.cnblogs.com/skywang12345/p/3308807.html

11-09 14:48
Powered by LMLPHP ©2024 辰砂 0.088655