写在前面的话：读书破万卷，编码如有神
--------------------------------------------------------------------
下文主要对java.util.LinkedList<E>的10个双端队列操作进行介绍，主要内容包括：
1、LinkedList常用的10个双端队列操作介绍
参考内容：
1、JDK源码(1.7)
--------------------------------------------------------------------
1、LinkedList常用的10个双端队列操作介绍
(1)boolean offerFirst(E e)
功能: 将指定的元素e插入此双端队列的开头
示例代码:
1 import java.util.LinkedList; 2 3 public class LinkedListDemo { 4 public static void main(String[] args) { 5 /*********测试LinkedList的'boolean offerFirst(E e)'方法的使用**********/ 6 7 //创建一个LinkedList对象 8 LinkedList<Student> linkedList = new LinkedList<Student>(); 9 10 //创建一个Student对象，并将其添加到LinkedList对象中 11 Student stu1 = new Student(1,"zhangsan",20); 12 linkedList.add(stu1); 13 14 //创建一个Student对象，并将其添加到LinkedList对象中 15 Student stu2 = new Student(2,"lisi",21); 16 linkedList.add(stu2); 17 18 //创建一个Student对象，并将其添加到LinkedList对象中 19 Student stu3 = new Student(3,"wangwu",22); 20 linkedList.add(stu3); 21 System.out.println("linkedList:" + linkedList); 22 23 24 Student stu4 = new Student(4,"oopp",22); 25 System.out.println("linkedList.offerFirst(stu4):" + linkedList.offerFirst(stu4)); 26 System.out.println("linkedList:" + linkedList); 27 } 28 } 29 30 运行结果: 31 linkedList:[Student [stuId=1, stuName=zhangsan, stuAge=20], Student [stuId=2, stuName=lisi, stuAge=21], Student [stuId=3, stuName=wangwu, stuAge=22]] 32 linkedList.offerFirst(stu4):true 33 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]]
源代码如下:
1 /* 2 将指定的元素e插入到此双端队列的开头 3 */ 4 public boolean offerFirst(E e) { 5 //调用内部方法addFirst实现 6 addFirst(e); 7 return true; 8 } 9 10 /* 11 将指定的元素e插入到此双端队列的开头 12 */ 13 public void addFirst(E e) { 14 //调用内部方法linkFirst实现 15 linkFirst(e); 16 } 17 18 /* 19 将指定的元素e插入到此双端队列的开头 20 */ 21 private void linkFirst(E e) { 22 //引用f指向此双端队列的开头 23 final Node<E> f = first; 24 //新建一个Node节点 25 final Node<E> newNode = new Node<>(null, e, f); 26 //此双端队列对象的first属性指向刚新建的Node节点 27 first = newNode; 28 29 //如果此双端队列为空， 30 //则双端队列对象的last属性也指向刚新建的Node节点 31 //否则原双端队列的头节点的prev属性指向刚新建的Node节点 32 if (f == null) 33 last = newNode; 34 else 35 f.prev = newNode; 36 //双端队列中元素个数加1 37 size++; 38 //fast-fail机制加1 39 modCount++; 40 }
(2)boolean offerLast(E e)
功能: 将指定的元素e插入此双端队列的尾部
示例代码:
1 import java.util.LinkedList; 2 3 public class LinkedListDemo { 4 public static void main(String[] args) { 5 /*********测试LinkedList的'boolean offerLast(E e) '方法的使用**********/ 6 7 //创建一个LinkedList对象 8 LinkedList<Student> linkedList = new LinkedList<Student>(); 9 10 //创建一个Student对象，并将其添加到LinkedList对象中 11 Student stu1 = new Student(1,"zhangsan",20); 12 linkedList.add(stu1); 13 14 //创建一个Student对象，并将其添加到LinkedList对象中 15 Student stu2 = new Student(2,"lisi",21); 16 linkedList.add(stu2); 17 18 //创建一个Student对象，并将其添加到LinkedList对象中 19 Student stu3 = new Student(3,"wangwu",22); 20 linkedList.add(stu3); 21 System.out.println("linkedList:" + linkedList); 22 23 24 Student stu4 = new Student(4,"oopp",22); 25 System.out.println("linkedList.offerLast(stu4):" + linkedList.offerLast(stu4)); 26 System.out.println("linkedList:" + linkedList); 27 } 28 } 29 30 运行结果: 31 linkedList:[Student [stuId=1, stuName=zhangsan, stuAge=20], Student [stuId=2, stuName=lisi, stuAge=21], Student [stuId=3, stuName=wangwu, stuAge=22]] 32 linkedList.offerLast(stu4):true 33 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]]
源代码如下:
1 /* 2 将指定的元素e插入到此双端队列的尾部 3 */ 4 public boolean offerLast(E e) { 5 //调用方法addLast实现 6 addLast(e); 7 return true; 8 } 9 10 /* 11 将指定的元素e插入到此双端队列的尾部 12 */ 13 public void addLast(E e) { 14 //调用方法linkLast实现 15 linkLast(e); 16 } 17 18 /* 19 将指定的元素e插入到此双端队列的尾部 20 */ 21 void linkLast(E e) { 22 //将引用l指向此双端队列的尾部 23 final Node<E> l = last; 24 //新建一个Node节点 25 final Node<E> newNode = new Node<>(l, e, null); 26 //此双端队列对象的last属性指向刚新建的Node节点 27 last = newNode; 28 29 //如果此双端队列为空 30 //则双端队列对象的first属性指向刚新建的Node节点 31 //否则原双端队列尾部对象的next属性指向刚新建的Node节点 32 if (l == null) 33 first = newNode; 34 else 35 l.next = newNode; 36 //双端队列中节点元素个数加1 37 size++; 38 //fast-fail机制加1 39 modCount++; 40 }
(3)E peekFirst()
功能: 获取，但不移除此双端队列的第一个元素（如果此双端队列为空，则返回 null）
示例代码:
1 import java.util.LinkedList; 2 3 public class LinkedListDemo { 4 public static void main(String[] args) { 5 /*********测试LinkedList的'E peekFirst() '方法的使用**********/ 6 7 //创建一个LinkedList对象 8 LinkedList<Student> linkedList = new LinkedList<Student>(); 9 10 //创建一个Student对象，并将其添加到LinkedList对象中 11 Student stu1 = new Student(1,"zhangsan",20); 12 linkedList.add(stu1); 13 14 //创建一个Student对象，并将其添加到LinkedList对象中 15 Student stu2 = new Student(2,"lisi",21); 16 linkedList.add(stu2); 17 18 //创建一个Student对象，并将其添加到LinkedList对象中 19 Student stu3 = new Student(3,"wangwu",22); 20 linkedList.add(stu3); 21 System.out.println("linkedList:" + linkedList); 22 23 System.out.println("linkedList.peekFirst():" + linkedList.peekFirst()); 24 System.out.println("linkedList:" + linkedList); 25 } 26 } 27 28 运行结果: 29 linkedList:[Student [stuId=1, stuName=zhangsan, stuAge=20], Student [stuId=2, stuName=lisi, stuAge=21], Student [stuId=3, stuName=wangwu, stuAge=22]] 30 linkedList.peekFirst():Student [stuId=1, stuName=zhangsan, stuAge=20] 31 linkedList:[Student [stuId=1, stuName=zhangsan, stuAge=20], Student [stuId=2, stuName=lisi, stuAge=21], Student [stuId=3, stuName=wangwu, stuAge=22]]
源代码如下:
1 /* 2 获取，但不移除此双端队列的第一个元素 3 */ 4 public E peekFirst() { 5 final Node<E> f = first; 6 return (f == null) ? null : f.item; 7 }
(4)E peekLast()
功能: 获取，但不移除此双端队列的最后一个元素（如果此双端队列为空，则返回 null）
示例代码:
1 import java.util.LinkedList; 2 3 public class LinkedListDemo { 4 public static void main(String[] args) { 5 /*********测试LinkedList的'E peekLast()'方法的使用**********/ 6 7 //创建一个LinkedList对象 8 LinkedList<Student> linkedList = new LinkedList<Student>(); 9 10 //创建一个Student对象，并将其添加到LinkedList对象中 11 Student stu1 = new Student(1,"zhangsan",20); 12 linkedList.add(stu1); 13 14 //创建一个Student对象，并将其添加到LinkedList对象中 15 Student stu2 = new Student(2,"lisi",21); 16 linkedList.add(stu2); 17 18 //创建一个Student对象，并将其添加到LinkedList对象中 19 Student stu3 = new Student(3,"wangwu",22); 20 linkedList.add(stu3); 21 System.out.println("linkedList:" + linkedList); 22 23 System.out.println("linkedList.peekLast():" + linkedList.peekLast()); 24 System.out.println("linkedList:" + linkedList); 25 } 26 } 27 28 运行结果: 29 linkedList:[Student [stuId=1, stuName=zhangsan, stuAge=20], Student [stuId=2, stuName=lisi, stuAge=21], Student [stuId=3, stuName=wangwu, stuAge=22]] 30 linkedList.peekLast():Student [stuId=3, stuName=wangwu, stuAge=22] 31 linkedList:[Student [stuId=1, stuName=zhangsan, stuAge=20], Student [stuId=2, stuName=lisi, stuAge=21], Student [stuId=3, stuName=wangwu, stuAge=22]]
源代码如下:
1 /* 2 获取，但不移除此双端队列的最后一个元素 3 */ 4 public E peekLast() { 5 //引用l指向此双端队列的最后一个元素 6 final Node<E> l = last; 7 //返回双端队列最后一个元素 8 return (l == null) ? null : l.item; 9 }
(5)E pollFirst()
功能: 获取并移除此双端队列的第一个元素（如果此双端队列为空，则返回 null）
示例代码:
1 import java.util.LinkedList; 2 3 public class LinkedListDemo { 4 public static void main(String[] args) { 5 /*********测试LinkedList的'E pollFirst()'方法的使用**********/ 6 7 //创建一个LinkedList对象 8 LinkedList<Student> linkedList = new LinkedList<Student>(); 9 10 //创建一个Student对象，并将其添加到LinkedList对象中 11 Student stu1 = new Student(1,"zhangsan",20); 12 linkedList.add(stu1); 13 14 //创建一个Student对象，并将其添加到LinkedList对象中 15 Student stu2 = new Student(2,"lisi",21); 16 linkedList.add(stu2); 17 18 //创建一个Student对象，并将其添加到LinkedList对象中 19 Student stu3 = new Student(3,"wangwu",22); 20 linkedList.add(stu3); 21 System.out.println("linkedList:" + linkedList); 22 23 System.out.println("linkedList.pollFirst():" + linkedList.pollFirst()); 24 System.out.println("linkedList:" + linkedList); 25 } 26 } 27 28 运行结果: 29 linkedList:[Student [stuId=1, stuName=zhangsan, stuAge=20], Student [stuId=2, stuName=lisi, stuAge=21], Student [stuId=3, stuName=wangwu, stuAge=22]] 30 linkedList.pollFirst():Student [stuId=1, stuName=zhangsan, stuAge=20] 31 linkedList:[Student [stuId=2, stuName=lisi, stuAge=21], Student [stuId=3, stuName=wangwu, stuAge=22]]
源代码如下:
1 /* 2 获取并移除此双端队列的第一个元素（如果双端队列为空，则返回null） 3 */ 4 public E pollFirst() { 5 //引用f指向此双端队列的第一个节点元素 6 final Node<E> f = first; 7 //返回并移除双端队列的第一个元素 8 return (f == null) ? null : unlinkFirst(f); 9 } 10 11 /* 12 获取并移除此双端队列的第一个元素 13 */ 14 private E unlinkFirst(Node<E> f) { 15 // assert f == first && f != null; 16 //记录双端队列的第一个节点的值 17 final E element = f.item; 18 //记录双端队列的第二个节点 19 final Node<E> next = f.next; 20 21 //将双端队列的头节点的item、next都设置为null,帮助GC回收 22 f.item = null; 23 f.next = null; // help GC 24 25 //此双端队列对象的first属性指向第二个节点 26 //如果第二个节点尾null,则设置双端队列对象的last属性为null 27 //否则设置第二个节点的prev属性为null 28 first = next; 29 if (next == null) 30 last = null; 31 else 32 next.prev = null; 33 //此双端队列中元素个数减1 34 size--; 35 //fast-fail机制加1 36 modCount++; 37 //返回被删除的节点 38 return element; 39 }
(6)E pollLast()
功能: 获取并移除此双端队列的最后一个元素（如果此双端队列为空，则返回 null）
示例代码:
1 import java.util.LinkedList; 2 3 public class LinkedListDemo { 4 public static void main(String[] args) { 5 /*********测试LinkedList的'E pollLast()'方法的使用**********/ 6 7 //创建一个LinkedList对象 8 LinkedList<Student> linkedList = new LinkedList<Student>(); 9 10 //创建一个Student对象，并将其添加到LinkedList对象中 11 Student stu1 = new Student(1,"zhangsan",20); 12 linkedList.add(stu1); 13 14 //创建一个Student对象，并将其添加到LinkedList对象中 15 Student stu2 = new Student(2,"lisi",21); 16 linkedList.add(stu2); 17 18 //创建一个Student对象，并将其添加到LinkedList对象中 19 Student stu3 = new Student(3,"wangwu",22); 20 linkedList.add(stu3); 21 System.out.println("linkedList:" + linkedList); 22 23 System.out.println("linkedList.pollLast():" + linkedList.pollLast()); 24 System.out.println("linkedList:" + linkedList); 25 } 26 } 27 28 运行结果: 29 linkedList:[Student [stuId=1, stuName=zhangsan, stuAge=20], Student [stuId=2, stuName=lisi, stuAge=21], Student [stuId=3, stuName=wangwu, stuAge=22]] 30 linkedList.pollLast():Student [stuId=3, stuName=wangwu, stuAge=22] 31 linkedList:[Student [stuId=1, stuName=zhangsan, stuAge=20], Student [stuId=2, stuName=lisi, stuAge=21]]
源代码如下:
1 /* 2 获取并移除此双端队列的最后一个元素(如果此双端队列为空，则返回null) 3 */ 4 public E pollLast() { 5 //引用l指向双端独立的最后一个节点 6 final Node<E> l = last; 7 //返回并移除此双端队列的最后一个节点 8 return (l == null) ? null : unlinkLast(l); 9 } 10 11 /* 12 返回并移除此双端队列的最后一个节点 13 */ 14 private E unlinkLast(Node<E> l) { 15 // assert l == last && l != null; 16 //记录双端队列的最后一个节点的值 17 final E element = l.item; 18 //记录双端队列的倒数第二个节点 19 final Node<E> prev = l.prev; 20 21 //设置双端队列最后一个节点的item、prev为null,帮助GC回收 22 l.item = null; 23 l.prev = null; // help GC 24 25 //双端队列对象的last属性指向双端队列的倒数第二个节点 26 last = prev; 27 //如果双端队列的倒数第二个节点为null 28 //则双端队列的first属性为null 29 //否则双端队列的倒数第二个节点的next属性为null 30 if (prev == null) 31 first = null; 32 else 33 prev.next = null; 34 //双端队列中的元素个数减1 35 size--; 36 //fast-fail机制加1 37 modCount++; 38 //返回并移除的节点 39 return element; 40 }
(7)void push(E e)
功能: 将一个元素推入此双端队列所表示的堆栈；如果成功，则返回 true
示例代码:
1 import java.util.LinkedList; 2 3 public class LinkedListDemo { 4 public static void main(String[] args) { 5 /*********测试LinkedList的'void push(E e)'方法的使用**********/ 6 7 //创建一个LinkedList对象 8 LinkedList<Student> linkedList = new LinkedList<Student>(); 9 10 //创建一个Student对象，并将其添加到LinkedList对象中 11 Student stu1 = new Student(1,"zhangsan",20); 12 linkedList.add(stu1); 13 14 //创建一个Student对象，并将其添加到LinkedList对象中 15 Student stu2 = new Student(2,"lisi",21); 16 linkedList.add(stu2); 17 18 //创建一个Student对象，并将其添加到LinkedList对象中 19 Student stu3 = new Student(3,"wangwu",22); 20 linkedList.add(stu3); 21 System.out.println("linkedList:" + linkedList); 22 23 Student stu4 = new Student(4,"xiaohong",22); 24 linkedList.push(stu4); 25 System.out.println("linkedList:" + linkedList); 26 } 27 } 28 29 运行结果: 30 linkedList:[Student [stuId=1, stuName=zhangsan, stuAge=20], Student [stuId=2, stuName=lisi, stuAge=21], Student [stuId=3, stuName=wangwu, stuAge=22]] 31 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]]
源代码如下:
1 /* 2 将元素e添加到此双端队列所表示的堆栈中 3 */ 4 public void push(E e) { 5 //调用addFirst方法实现 6 addFirst(e); 7 }
(8)E pop()
功能: 从此双端队列所表示的堆栈中弹出一个元素
示例代码:
1 import java.util.LinkedList; 2 3 public class LinkedListDemo { 4 public static void main(String[] args) { 5 /*********测试LinkedList的'E pop()'方法的使用**********/ 6 7 //创建一个LinkedList对象 8 LinkedList<Student> linkedList = new LinkedList<Student>(); 9 10 //创建一个Student对象，并将其添加到LinkedList对象中 11 Student stu1 = new Student(1,"zhangsan",20); 12 linkedList.add(stu1); 13 14 //创建一个Student对象，并将其添加到LinkedList对象中 15 Student stu2 = new Student(2,"lisi",21); 16 linkedList.add(stu2); 17 18 //创建一个Student对象，并将其添加到LinkedList对象中 19 Student stu3 = new Student(3,"wangwu",22); 20 linkedList.add(stu3); 21 System.out.println("linkedList:" + linkedList); 22 23 System.out.println("linkedList.pop():" + linkedList.pop()); 24 System.out.println("linkedList:" + linkedList); 25 } 26 } 27 28 运行结果: 29 linkedList:[Student [stuId=1, stuName=zhangsan, stuAge=20], Student [stuId=2, stuName=lisi, stuAge=21], Student [stuId=3, stuName=wangwu, stuAge=22]] 30 linkedList.pop():Student [stuId=1, stuName=zhangsan, stuAge=20] 31 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]]
源代码如下:
1 /* 2 从此双端队列移除第一次出现的指定元素o 3 */ 4 public boolean removeFirstOccurrence(Object o) { 5 //调用方法remove实现 6 return remove(o); 7 }
(10)boolean removeLastOccurrence(Object o)
功能: 从此双端队列移除最后一次出现的指定元素
示例代码:
1 import java.util.LinkedList; 2 3 public class LinkedListDemo { 4 public static void main(String[] args) { 5 /*********测试LinkedList的'boolean removeLastOccurrence(Object o)'方法的使用**********/ 6 7 //创建一个LinkedList对象 8 LinkedList<Student> linkedList = new LinkedList<Student>(); 9 10 //创建一个Student对象，并将其添加到LinkedList对象中 11 Student stu1 = new Student(1,"zhangsan",20); 12 linkedList.add(stu1); 13 14 //创建一个Student对象，并将其添加到LinkedList对象中 15 Student stu2 = new Student(2,"lisi",21); 16 linkedList.add(stu2); 17 18 //创建一个Student对象，并将其添加到LinkedList对象中 19 Student stu3 = new Student(3,"wangwu",22); 20 linkedList.add(stu3); 21 linkedList.add(stu2); 22 linkedList.add(stu3); 23 System.out.println("linkedList:" + linkedList); 24 25 System.out.println("linkedList.removeLastOccurrence(stu2):" + linkedList.removeLastOccurrence(stu2)); 26 System.out.println("linkedList:" + linkedList); 27 } 28 } 29 30 运行结果: 31 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]] 32 linkedList.removeLastOccurrence(stu2):true 33 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]]
源代码如下:
1 /* 2 从此双端队列移除最后一次出现的指定元素o 3 */ 4 public boolean removeLastOccurrence(Object o) { 5 if (o == null) { 6 //当元素o为null时 7 //循环逆序遍历此双端队列，查询值为null的节点 8 for (Node<E> x = last; x != null; x = x.prev) { 9 if (x.item == null) { 10 //移除此节点 11 unlink(x); 12 return true; 13 } 14 } 15 } else { 16 //当元素o不为null时 17 //循环逆序遍历此双端队列，查询值等于节点o的值的节点 18 for (Node<E> x = last; x != null; x = x.prev) { 19 if (o.equals(x.item)) { 20 //移除此节点 21 unlink(x); 22 return true; 23 } 24 } 25 } 26 return false; 27 }
--------------------------------------------------------------------
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>