关于LinkedList

概念及特性

• 底层数据实现是双向链表数据结构，是无序列表，可以放相同元素
• 双向链表为链表结构的子数据结构，每个节点有三个字段：当前节点的数据字段，同时指向上一个节点和下一个节点的字段
• 集合中元素允许为null
• 元素存放顺序为存入顺序

构造器

1. 无参

   • 空参数的构造函数生成一个空链表
   • first=last=null

   /**
    * Constructs an empty list.
    */
   public LinkedList() {
   }
   

2. 集合参数

   • 传入一个集合，构造一个包含其集合元素的LInkedList集合
   • 按照集合元素的顺序作为节点
   • 如果参数collection为空，会抛出NullPointerException
   • addAll方法实现了将集合元素插入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);
}

方法

增：addFirst addLast /offerFirst offerLast

• addFirst、offerFirst：向第一个节点增加元素
• addLast、offerLast：向最后一个节点增加元素

删：removeFirst removeLast/peekFirst peekLast

• removeFirst、pollFirst删除第一个节点并返回其值，如果元素为空，前者抛NoSuchElementException异常，后者返回null
• removeLast、pollLast删除第一个节点并返回其值，如果元素为空，前者抛NoSuchElementException异常，后者返回null

得：getFirst getLast / pollFirst pollLast

• getFirst、peekFirst获取第一个节点，如果元素为空，前者抛NoSuchElementException异常，后者返回null
• getLast、peekLast获取最后个节点，如果元素为空，前者抛NoSuchElementException异常，后者返回null

例子

public class LinkedListDemo {
    public static void main(String[] args) {
        LinkedList linkedList = new LinkedList();

        //增加元素，倒序增加1234
        linkedList.addFirst("1");
        linkedList.addFirst("2");
        linkedList.addFirst("3");
        linkedList.addFirst("4");
        System.out.println(linkedList);
        //倒序获取列表元素，并删除
        while (!linkedList.isEmpty()) {
            System.out.println("取出元素为："+linkedList.removeLast());
            System.out.println("size："+linkedList.size());
        }
        System.out.println(linkedList);
        //当获取元素为空时，peekFirst返回null
        System.out.println(linkedList.peekFirst());
    }
}

输出结果

[4, 3, 2, 1]
取出元素为：1
size：3
取出元素为：2
size：2
取出元素为：3
size：1
取出元素为：4
size：0
[]
null

for循环

for (int i = 0; i < linkedList.size(); i++) {
    System.out.println(linkedList.get(i));
}

迭代器

for (Iterator it = linkedList.iterator();it.hasNext();) {
    System.out.println(it.next());
}