内功心法 -- java.util.LinkedList (7)

写在前面的话：读书破万卷，编码如有神
--------------------------------------------------------------------
下文主要对java.util.LinkedList<E>的10个双端队列操作进行介绍，主要内容包括：

1、LinkedList常用的10个双端队列操作介绍

参考内容：

1、JDK源码(1.7)

--------------------------------------------------------------------

1、LinkedList常用的10个双端队列操作介绍

(1)boolean offerFirst(E e)

功能: 将指定的元素e插入此双端队列的开头

示例代码:

 import java.util.LinkedList;

 public class LinkedListDemo {
     public static void main(String[] args) {
         /*********测试LinkedList的'boolean offerFirst(E e)'方法的使用**********/

         //创建一个LinkedList对象
         LinkedList<Student> linkedList = new LinkedList<Student>();

         //创建一个Student对象，并将其添加到LinkedList对象中
         Student stu1 = new Student(1,"zhangsan",20);
         linkedList.add(stu1);

         //创建一个Student对象，并将其添加到LinkedList对象中
         Student stu2 = new Student(2,"lisi",21);
         linkedList.add(stu2);

         //创建一个Student对象，并将其添加到LinkedList对象中
         Student stu3 = new Student(3,"wangwu",22);
         linkedList.add(stu3);
         System.out.println("linkedList:" + linkedList);

         Student stu4 = new Student(4,"oopp",22);
         System.out.println("linkedList.offerFirst(stu4):" + linkedList.offerFirst(stu4));
         System.out.println("linkedList:" + linkedList);
     }
 }

 运行结果:
 linkedList:[Student [stuId=1, stuName=zhangsan, stuAge=20], Student [stuId=2, stuName=lisi, stuAge=21], Student [stuId=3, stuName=wangwu, stuAge=22]]
 linkedList.offerFirst(stu4):true
 linkedList:[Student [stuId=4, stuName=oopp, stuAge=22], Student [stuId=1, stuName=zhangsan, stuAge=20], Student [stuId=2, stuName=lisi, stuAge=21], Student [stuId=3, stuName=wangwu, stuAge=22]]

源代码如下:

     /*
        将指定的元素e插入到此双端队列的开头
    */
     public boolean offerFirst(E e) {
         //调用内部方法addFirst实现
         addFirst(e);
         return true;
     }

     /*
        将指定的元素e插入到此双端队列的开头
    */
     public void addFirst(E e) {
         //调用内部方法linkFirst实现
         linkFirst(e);
     }

     /*
        将指定的元素e插入到此双端队列的开头
    */
     private void linkFirst(E e) {
         //引用f指向此双端队列的开头
         final Node<E> f = first;
         //新建一个Node节点
         final Node<E> newNode = new Node<>(null, e, f);
         //此双端队列对象的first属性指向刚新建的Node节点
         first = newNode;

         //如果此双端队列为空，
         //则双端队列对象的last属性也指向刚新建的Node节点
         //否则原双端队列的头节点的prev属性指向刚新建的Node节点
         if (f == null)
             last = newNode;
         else
             f.prev = newNode;
         //双端队列中元素个数加1
         size++;
         //fast-fail机制加1
         modCount++;
     }

(2)boolean offerLast(E e)

功能: 将指定的元素e插入此双端队列的尾部

示例代码:

 import java.util.LinkedList;

 public class LinkedListDemo {
     public static void main(String[] args) {
         /*********测试LinkedList的'boolean offerLast(E e) '方法的使用**********/

         //创建一个LinkedList对象
         LinkedList<Student> linkedList = new LinkedList<Student>();

         //创建一个Student对象，并将其添加到LinkedList对象中
         Student stu1 = new Student(1,"zhangsan",20);
         linkedList.add(stu1);

         //创建一个Student对象，并将其添加到LinkedList对象中
         Student stu2 = new Student(2,"lisi",21);
         linkedList.add(stu2);

         //创建一个Student对象，并将其添加到LinkedList对象中
         Student stu3 = new Student(3,"wangwu",22);
         linkedList.add(stu3);
         System.out.println("linkedList:" + linkedList);

         Student stu4 = new Student(4,"oopp",22);
         System.out.println("linkedList.offerLast(stu4):" + linkedList.offerLast(stu4));
         System.out.println("linkedList:" + linkedList);
     }
 }

 运行结果:
 linkedList:[Student [stuId=1, stuName=zhangsan, stuAge=20], Student [stuId=2, stuName=lisi, stuAge=21], Student [stuId=3, stuName=wangwu, stuAge=22]]
 linkedList.offerLast(stu4):true
 linkedList:[Student [stuId=1, stuName=zhangsan, stuAge=20], Student [stuId=2, stuName=lisi, stuAge=21], Student [stuId=3, stuName=wangwu, stuAge=22], Student [stuId=4, stuName=oopp, stuAge=22]]

源代码如下:

     /*
       将指定的元素e插入到此双端队列的尾部
    */
     public boolean offerLast(E e) {
         //调用方法addLast实现
         addLast(e);
         return true;
     }

     /*
       将指定的元素e插入到此双端队列的尾部
    */
     public void addLast(E e) {
         //调用方法linkLast实现
         linkLast(e);
     }

     /*
       将指定的元素e插入到此双端队列的尾部
    */
     void linkLast(E e) {
         //将引用l指向此双端队列的尾部
         final Node<E> l = last;
         //新建一个Node节点
         final Node<E> newNode = new Node<>(l, e, null);
         //此双端队列对象的last属性指向刚新建的Node节点
         last = newNode;

         //如果此双端队列为空
         //则双端队列对象的first属性指向刚新建的Node节点
         //否则原双端队列尾部对象的next属性指向刚新建的Node节点
         if (l == null)
             first = newNode;
         else
             l.next = newNode;
         //双端队列中节点元素个数加1
         size++;
         //fast-fail机制加1
         modCount++;
     }

(3)E peekFirst()

功能: 获取，但不移除此双端队列的第一个元素（如果此双端队列为空，则返回 null）

示例代码:

 import java.util.LinkedList;

 public class LinkedListDemo {
     public static void main(String[] args) {
         /*********测试LinkedList的'E peekFirst()  '方法的使用**********/

         //创建一个LinkedList对象
         LinkedList<Student> linkedList = new LinkedList<Student>();

         //创建一个Student对象，并将其添加到LinkedList对象中
         Student stu1 = new Student(1,"zhangsan",20);
         linkedList.add(stu1);

         //创建一个Student对象，并将其添加到LinkedList对象中
         Student stu2 = new Student(2,"lisi",21);
         linkedList.add(stu2);

         //创建一个Student对象，并将其添加到LinkedList对象中
         Student stu3 = new Student(3,"wangwu",22);
         linkedList.add(stu3);
         System.out.println("linkedList:" + linkedList);

         System.out.println("linkedList.peekFirst():" + linkedList.peekFirst());
         System.out.println("linkedList:" + linkedList);
     }
 }

 运行结果:
 linkedList:[Student [stuId=1, stuName=zhangsan, stuAge=20], Student [stuId=2, stuName=lisi, stuAge=21], Student [stuId=3, stuName=wangwu, stuAge=22]]
 linkedList.peekFirst():Student [stuId=1, stuName=zhangsan, stuAge=20]
 linkedList:[Student [stuId=1, stuName=zhangsan, stuAge=20], Student [stuId=2, stuName=lisi, stuAge=21], Student [stuId=3, stuName=wangwu, stuAge=22]]

源代码如下:

     /*
        获取，但不移除此双端队列的第一个元素
     */
     public E peekFirst() {
         final Node<E> f = first;
         return (f == null) ? null : f.item;
      }

(4)E peekLast()

功能: 获取，但不移除此双端队列的最后一个元素（如果此双端队列为空，则返回 null）

示例代码:

 import java.util.LinkedList;

 public class LinkedListDemo {
     public static void main(String[] args) {
         /*********测试LinkedList的'E peekLast()'方法的使用**********/

         //创建一个LinkedList对象
         LinkedList<Student> linkedList = new LinkedList<Student>();

         //创建一个Student对象，并将其添加到LinkedList对象中
         Student stu1 = new Student(1,"zhangsan",20);
         linkedList.add(stu1);

         //创建一个Student对象，并将其添加到LinkedList对象中
         Student stu2 = new Student(2,"lisi",21);
         linkedList.add(stu2);

         //创建一个Student对象，并将其添加到LinkedList对象中
         Student stu3 = new Student(3,"wangwu",22);
         linkedList.add(stu3);
         System.out.println("linkedList:" + linkedList);

         System.out.println("linkedList.peekLast():" + linkedList.peekLast());
         System.out.println("linkedList:" + linkedList);
     }
 }

 运行结果:
 linkedList:[Student [stuId=1, stuName=zhangsan, stuAge=20], Student [stuId=2, stuName=lisi, stuAge=21], Student [stuId=3, stuName=wangwu, stuAge=22]]
 linkedList.peekLast():Student [stuId=3, stuName=wangwu, stuAge=22]
 linkedList:[Student [stuId=1, stuName=zhangsan, stuAge=20], Student [stuId=2, stuName=lisi, stuAge=21], Student [stuId=3, stuName=wangwu, stuAge=22]]

源代码如下:

     /*
        获取，但不移除此双端队列的最后一个元素
     */
     public E peekLast() {
         //引用l指向此双端队列的最后一个元素
         final Node<E> l = last;
         //返回双端队列最后一个元素
         return (l == null) ? null : l.item;
     }

(5)E pollFirst()

功能: 获取并移除此双端队列的第一个元素（如果此双端队列为空，则返回 null）

示例代码:

 import java.util.LinkedList;

 public class LinkedListDemo {
     public static void main(String[] args) {
         /*********测试LinkedList的'E pollFirst()'方法的使用**********/

         //创建一个LinkedList对象
         LinkedList<Student> linkedList = new LinkedList<Student>();

         //创建一个Student对象，并将其添加到LinkedList对象中
         Student stu1 = new Student(1,"zhangsan",20);
         linkedList.add(stu1);

         //创建一个Student对象，并将其添加到LinkedList对象中
         Student stu2 = new Student(2,"lisi",21);
         linkedList.add(stu2);

         //创建一个Student对象，并将其添加到LinkedList对象中
         Student stu3 = new Student(3,"wangwu",22);
         linkedList.add(stu3);
         System.out.println("linkedList:" + linkedList);

         System.out.println("linkedList.pollFirst():" + linkedList.pollFirst());
         System.out.println("linkedList:" + linkedList);
     }
 }

 运行结果:
 linkedList:[Student [stuId=1, stuName=zhangsan, stuAge=20], Student [stuId=2, stuName=lisi, stuAge=21], Student [stuId=3, stuName=wangwu, stuAge=22]]
 linkedList.pollFirst():Student [stuId=1, stuName=zhangsan, stuAge=20]
 linkedList:[Student [stuId=2, stuName=lisi, stuAge=21], Student [stuId=3, stuName=wangwu, stuAge=22]]

源代码如下:

     /*
         获取并移除此双端队列的第一个元素（如果双端队列为空，则返回null）
     */
     public E pollFirst() {
         //引用f指向此双端队列的第一个节点元素
         final Node<E> f = first;
         //返回并移除双端队列的第一个元素
         return (f == null) ? null : unlinkFirst(f);
     }

     /*
        获取并移除此双端队列的第一个元素
     */
     private E unlinkFirst(Node<E> f) {
         // assert f == first && f != null;
         //记录双端队列的第一个节点的值
         final E element = f.item;
         //记录双端队列的第二个节点
         final Node<E> next = f.next;

         //将双端队列的头节点的item、next都设置为null,帮助GC回收
         f.item = null;
         f.next = null; // help GC

         //此双端队列对象的first属性指向第二个节点
         //如果第二个节点尾null,则设置双端队列对象的last属性为null
         //否则设置第二个节点的prev属性为null
         first = next;
         if (next == null)
             last = null;
         else
             next.prev = null;
         //此双端队列中元素个数减1
         size--;
         //fast-fail机制加1
         modCount++;
         //返回被删除的节点
         return element;
     }

(6)E pollLast()

功能: 获取并移除此双端队列的最后一个元素（如果此双端队列为空，则返回 null）

示例代码:

 import java.util.LinkedList;

 public class LinkedListDemo {
     public static void main(String[] args) {
         /*********测试LinkedList的'E pollLast()'方法的使用**********/

         //创建一个LinkedList对象
         LinkedList<Student> linkedList = new LinkedList<Student>();

         //创建一个Student对象，并将其添加到LinkedList对象中
         Student stu1 = new Student(1,"zhangsan",20);
         linkedList.add(stu1);

         //创建一个Student对象，并将其添加到LinkedList对象中
         Student stu2 = new Student(2,"lisi",21);
         linkedList.add(stu2);

         //创建一个Student对象，并将其添加到LinkedList对象中
         Student stu3 = new Student(3,"wangwu",22);
         linkedList.add(stu3);
         System.out.println("linkedList:" + linkedList);

         System.out.println("linkedList.pollLast():" + linkedList.pollLast());
         System.out.println("linkedList:" + linkedList);
     }
 }

 运行结果:
 linkedList:[Student [stuId=1, stuName=zhangsan, stuAge=20], Student [stuId=2, stuName=lisi, stuAge=21], Student [stuId=3, stuName=wangwu, stuAge=22]]
 linkedList.pollLast():Student [stuId=3, stuName=wangwu, stuAge=22]
 linkedList:[Student [stuId=1, stuName=zhangsan, stuAge=20], Student [stuId=2, stuName=lisi, stuAge=21]]

源代码如下:

     /*
        获取并移除此双端队列的最后一个元素(如果此双端队列为空，则返回null)
     */
     public E pollLast() {
         //引用l指向双端独立的最后一个节点
         final Node<E> l = last;
         //返回并移除此双端队列的最后一个节点
         return (l == null) ? null : unlinkLast(l);
     }

     /*
       返回并移除此双端队列的最后一个节点
    */
     private E unlinkLast(Node<E> l) {
         // assert l == last && l != null;
         //记录双端队列的最后一个节点的值
         final E element = l.item;
         //记录双端队列的倒数第二个节点
         final Node<E> prev = l.prev;

         //设置双端队列最后一个节点的item、prev为null,帮助GC回收
         l.item = null;
         l.prev = null; // help GC

         //双端队列对象的last属性指向双端队列的倒数第二个节点
         last = prev;
         //如果双端队列的倒数第二个节点为null
         //则双端队列的first属性为null
         //否则双端队列的倒数第二个节点的next属性为null
         if (prev == null)
             first = null;
         else
             prev.next = null;
         //双端队列中的元素个数减1
         size--;
         //fast-fail机制加1
         modCount++;
         //返回并移除的节点
         return element;
     }

(7)void push(E e)

功能: 将一个元素推入此双端队列所表示的堆栈；如果成功，则返回 true

示例代码:

 import java.util.LinkedList;

 public class LinkedListDemo {
     public static void main(String[] args) {
         /*********测试LinkedList的'void push(E e)'方法的使用**********/

         //创建一个LinkedList对象
         LinkedList<Student> linkedList = new LinkedList<Student>();

         //创建一个Student对象，并将其添加到LinkedList对象中
         Student stu1 = new Student(1,"zhangsan",20);
         linkedList.add(stu1);

         //创建一个Student对象，并将其添加到LinkedList对象中
         Student stu2 = new Student(2,"lisi",21);
         linkedList.add(stu2);

         //创建一个Student对象，并将其添加到LinkedList对象中
         Student stu3 = new Student(3,"wangwu",22);
         linkedList.add(stu3);
         System.out.println("linkedList:" + linkedList);

         Student stu4 = new Student(4,"xiaohong",22);
         linkedList.push(stu4);
         System.out.println("linkedList:" + linkedList);
     }
 }

 运行结果:
 linkedList:[Student [stuId=1, stuName=zhangsan, stuAge=20], Student [stuId=2, stuName=lisi, stuAge=21], Student [stuId=3, stuName=wangwu, stuAge=22]]
 linkedList:[Student [stuId=4, stuName=xiaohong, stuAge=22], Student [stuId=1, stuName=zhangsan, stuAge=20], Student [stuId=2, stuName=lisi, stuAge=21], Student [stuId=3, stuName=wangwu, stuAge=22]]

源代码如下:

     /*
         将元素e添加到此双端队列所表示的堆栈中
     */
     public void push(E e) {
         //调用addFirst方法实现
         addFirst(e);
     }

(8)E pop()

功能: 从此双端队列所表示的堆栈中弹出一个元素

示例代码:

 import java.util.LinkedList;

 public class LinkedListDemo {
     public static void main(String[] args) {
         /*********测试LinkedList的'E pop()'方法的使用**********/

         //创建一个LinkedList对象
         LinkedList<Student> linkedList = new LinkedList<Student>();

         //创建一个Student对象，并将其添加到LinkedList对象中
         Student stu1 = new Student(1,"zhangsan",20);
         linkedList.add(stu1);

         //创建一个Student对象，并将其添加到LinkedList对象中
         Student stu2 = new Student(2,"lisi",21);
         linkedList.add(stu2);

         //创建一个Student对象，并将其添加到LinkedList对象中
         Student stu3 = new Student(3,"wangwu",22);
         linkedList.add(stu3);
         System.out.println("linkedList:" + linkedList);

         System.out.println("linkedList.pop():" + linkedList.pop());
         System.out.println("linkedList:" + linkedList);
     }
 }

 运行结果:
 linkedList:[Student [stuId=1, stuName=zhangsan, stuAge=20], Student [stuId=2, stuName=lisi, stuAge=21], Student [stuId=3, stuName=wangwu, stuAge=22]]
 linkedList.pop():Student [stuId=1, stuName=zhangsan, stuAge=20]
 linkedList:[Student [stuId=2, stuName=lisi, stuAge=21], Student [stuId=3, stuName=wangwu, stuAge=22]]

源代码如下:

    /*
      从此双端队列所表示的堆栈中弹出一个元素
    */
    public E pop() {
        //调用removeFirst方法实现
        return removeFirst();
    }

(9)boolean removeFirstOccurrence(Object o)

功能: 从此双端队列移除第一次出现的指定元素

示例代码:

import java.util.LinkedList;

public class LinkedListDemo {
    public static void main(String[] args) {
        /*********测试LinkedList的'boolean removeFirstOccurrence(Object o)'方法的使用**********/

        //创建一个LinkedList对象
        LinkedList<Student> linkedList = new LinkedList<Student>();

        //创建一个Student对象，并将其添加到LinkedList对象中
        Student stu1 = new Student(1,"zhangsan",20);
        linkedList.add(stu1);

        //创建一个Student对象，并将其添加到LinkedList对象中
        Student stu2 = new Student(2,"lisi",21);
        linkedList.add(stu2);

        //创建一个Student对象，并将其添加到LinkedList对象中
        Student stu3 = new Student(3,"wangwu",22);
        linkedList.add(stu3);
        System.out.println("linkedList:" + linkedList);

        System.out.println("linkedList.removeFirstOccurrence(stu2):" + linkedList.removeFirstOccurrence(stu2));
        System.out.println("linkedList:" + linkedList);
    }
}

运行结果:
linkedList:[Student [stuId=1, stuName=zhangsan, stuAge=20], Student [stuId=2, stuName=lisi, stuAge=21], Student [stuId=3, stuName=wangwu, stuAge=22]]
linkedList.removeFirstOccurrence(stu2):true
linkedList:[Student [stuId=1, stuName=zhangsan, stuAge=20], Student [stuId=3, stuName=wangwu, stuAge=22]]

源代码如下:

     /*
        从此双端队列移除第一次出现的指定元素o
     */
     public boolean removeFirstOccurrence(Object o) {
         //调用方法remove实现
         return remove(o);
     }

(10)boolean removeLastOccurrence(Object o)

功能: 从此双端队列移除最后一次出现的指定元素

示例代码:

 import java.util.LinkedList;

 public class LinkedListDemo {
     public static void main(String[] args) {
         /*********测试LinkedList的'boolean removeLastOccurrence(Object o)'方法的使用**********/

         //创建一个LinkedList对象
         LinkedList<Student> linkedList = new LinkedList<Student>();

         //创建一个Student对象，并将其添加到LinkedList对象中
         Student stu1 = new Student(1,"zhangsan",20);
         linkedList.add(stu1);

         //创建一个Student对象，并将其添加到LinkedList对象中
         Student stu2 = new Student(2,"lisi",21);
         linkedList.add(stu2);

         //创建一个Student对象，并将其添加到LinkedList对象中
         Student stu3 = new Student(3,"wangwu",22);
         linkedList.add(stu3);
         linkedList.add(stu2);
         linkedList.add(stu3);
         System.out.println("linkedList:" + linkedList);

         System.out.println("linkedList.removeLastOccurrence(stu2):" + linkedList.removeLastOccurrence(stu2));
         System.out.println("linkedList:" + linkedList);
     }
 }

 运行结果:
 linkedList:[Student [stuId=1, stuName=zhangsan, stuAge=20], Student [stuId=2, stuName=lisi, stuAge=21], Student [stuId=3, stuName=wangwu, stuAge=22], Student [stuId=2, stuName=lisi, stuAge=21], Student [stuId=3, stuName=wangwu, stuAge=22]]
 linkedList.removeLastOccurrence(stu2):true
 linkedList:[Student [stuId=1, stuName=zhangsan, stuAge=20], Student [stuId=2, stuName=lisi, stuAge=21], Student [stuId=3, stuName=wangwu, stuAge=22], Student [stuId=3, stuName=wangwu, stuAge=22]]

源代码如下:

     /*
        从此双端队列移除最后一次出现的指定元素o
    */
     public boolean removeLastOccurrence(Object o) {
         if (o == null) {
             //当元素o为null时
             //循环逆序遍历此双端队列，查询值为null的节点
             for (Node<E> x = last; x != null; x = x.prev) {
                 if (x.item == null) {
                     //移除此节点
                     unlink(x);
                     return true;
                 }
             }
         } else {
             //当元素o不为null时
             //循环逆序遍历此双端队列，查询值等于节点o的值的节点
             for (Node<E> x = last; x != null; x = x.prev) {
                 if (o.equals(x.item)) {
                     //移除此节点
                     unlink(x);
                     return true;
                 }
             }
         }
         return false;
     }

--------------------------------------------------------------------

java.util.LinkedList<E>系列文章

java.util.LinkedList<E>(1)　　java.util.LinkedList<E>(2)　　java.util.LinkedList<E>(3)

java.util.LinkedList<E>(4)　　java.util.LinkedList<E>(5)　　java.util.LinkedList<E>(6)

java.util.LinkedList<E>(7)　　java.util.LinkedList<E>(8)　　

--------------------------------------------------------------------

相关知识

java.util.Collection<E> 　　java.util.AbstractCollection<E> 　　java.util.List<E>

java.util.AbstractList<E> 　　java.util.Iterator<E> 　　java.util.ListIterator<E>

Java中的标记接口 　　迭代器模式 　　Java中的深拷贝和浅拷贝  java.util.Arrays

java.util.Queue<E>　　java.util.Deque<E>