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

时间：2021-12-28 04:19:59

写在前面的话：读书破万卷，编码如有神
--------------------------------------------------------------------
下文主要对java.util.LinkedList<E>的构造方法和6个队列头、尾操作进行介绍，主要内容包括：

1、LinkedList构造方法介绍

2、LinkedList常用6个队头、尾操作介绍

参考内容：

1、JDK源码(1.7)

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

1、LinkedList两个构造方法                                                    

1.1、LinkedList构造方法（提供了两种构造方法）

1     //第一种: 默认构造函数
2     public LinkedList() {
3     }
4 
5     //第二种: 带子队列参数的构造函数
6     public LinkedList(Collection<? extends E> c) {
7         this();
8         addAll(c);
9     }

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

2、LinkedList常用6个队头、尾操作介绍                                    

(1) void addFirst(E e)

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

示例代码:

 1 import java.util.LinkedList;
 2 
 3 public class LinkedListDemo {
 4     public static void main(String[] args) {
 5         //创建一个LinkedList对象
 6         LinkedList<Student> linkedList = new LinkedList<Student>();
 7         
 8         //创建一个Student对象，并将其添加到LinkedList对象中
 9         Student stu1 = new Student(1,"zhangsan",20);
10         linkedList.addFirst(stu1);
11         System.out.println(linkedList);
12         
13         //创建一个Student对象，并将其添加到LinkedList对象中
14         Student stu2 = new Student(2,"lisi",21);
15         linkedList.addFirst(stu2);
16         System.out.println(linkedList);
17         
18         //创建一个Student对象，并将其添加到LinkedList对象中
19         Student stu3 = new Student(3,"wangwu",22);
20         linkedList.addFirst(stu3);
21         System.out.println(linkedList);
22     }
23 }
24 运行结果:
25 [Student [stuId=1, stuName=zhangsan, stuAge=20]]
26 [Student [stuId=2, stuName=lisi, stuAge=21], Student [stuId=1, stuName=zhangsan, stuAge=20]]
27 [Student [stuId=3, stuName=wangwu, stuAge=22], Student [stuId=2, stuName=lisi, stuAge=21], Student [stuId=1, stuName=zhangsan, stuAge=20]]
28 
29 从运行结果可以看出，调用addFirst(E e)方法往LinkedList对象中添加元素时，所添加的元素都在头部

源代码:

 1     /*
 2       将元素e插入到此双端队列的头部
 3     */
 4     public void addFirst(E e) {
 5         //调用内部方法来实现
 6         linkFirst(e);
 7     }
 8 
 9     /*
10      私有方法，将元素e链接到此双端队列的头部
11     */
12     private void linkFirst(E e) {
13         //引用f指向此双端队列的第一个节点（头部节点）
14         final Node<E> f = first;
15         //创建一个Node节点
16         final Node<E> newNode = new Node<>(null, e, f);
17         //设置此双端队列的first属性指向 刚新创建的Node节点
18         first = newNode;
19         //如果此时双端队列中没有节点存在，则设置此双端队列的last属性也指向刚新建的Node节点，否则设置原来的头节点的prev属性指向刚新建的Node节点
20         if (f == null)
21             last = newNode;
22         else
23             f.prev = newNode;
24         //双端队列中节点个数加1
25         size++;
26         //fast-fail机制加1
27         modCount++;
28     }

(2) void addLast(E e)

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

示例代码:

 1 import java.util.LinkedList;
 2 
 3 public class LinkedListDemo {
 4     public static void main(String[] args) {
 5         //创建一个LinkedList对象
 6         LinkedList<Student> linkedList = new LinkedList<Student>();
 7         
 8         //创建一个Student对象，并将其添加到LinkedList对象中
 9         Student stu1 = new Student(1,"zhangsan",20);
10         linkedList.addLast(stu1);
11         System.out.println(linkedList);
12         
13         //创建一个Student对象，并将其添加到LinkedList对象中
14         Student stu2 = new Student(2,"lisi",21);
15         linkedList.addLast(stu2);
16         System.out.println(linkedList);
17         
18         //创建一个Student对象，并将其添加到LinkedList对象中
19         Student stu3 = new Student(3,"wangwu",22);
20         linkedList.addLast(stu3);
21         System.out.println(linkedList);
22     }
23 }
24 
25 运行结果:
26 [Student [stuId=1, stuName=zhangsan, stuAge=20]]
27 [Student [stuId=1, stuName=zhangsan, stuAge=20], Student [stuId=2, stuName=lisi, stuAge=21]]
28 [Student [stuId=1, stuName=zhangsan, stuAge=20], Student [stuId=2, stuName=lisi, stuAge=21], Student [stuId=3, stuName=wangwu, stuAge=22]]
29 
30 可以看出，调用LinkedList的addLast方法是将元素添加到双端队列的尾部

源代码:

 1     /*
 2        将元素e添加到此双端队列的尾部
 3     */
 4     public void addLast(E e) {
 5         //调用内部linkLast方法来完成
 6         linkLast(e);
 7     }
 8 
 9     /*
10        将元素e链接到此双端队列的尾部 
11     */
12     void linkLast(E e) {
13         //引用l指向此双端队列对象的尾节点
14         final Node<E> l = last;
15         //新建一个Node节点
16         final Node<E> newNode = new Node<>(l, e, null);
17         //设置此双端队列对象的last属性指向刚新建的Node节点
18         last = newNode;
19         //如果此双端队列中没有节点存在，则设置此双端队列对象的first属性也指向刚新建的Node节点，否则原来的尾节点的next属性指向刚新建的Node节点
20         if (l == null)
21             first = newNode;
22         else
23             l.next = newNode;
24         //双端队列中节点个数加1
25         size++;
26         //fast-fail机制加1
27         modCount++;
28     }

(3) E getFirst()

功能: 获取，但不移除此双端队列的第一个元素

示例代码:

 1 import java.util.LinkedList;
 2 
 3 public class LinkedListDemo {
 4     public static void main(String[] args) {
 5         /*********测试LinkedList的'E getFirst()'方法的使用**********/
 6         
 7         //创建一个LinkedList对象
 8         LinkedList<Student> linkedList = new LinkedList<Student>();
 9         
10         //创建一个Student对象，并将其添加到LinkedList对象中
11         Student stu1 = new Student(1,"zhangsan",20);
12         linkedList.addLast(stu1);
13         System.out.println(linkedList);
14         
15         //创建一个Student对象，并将其添加到LinkedList对象中
16         Student stu2 = new Student(2,"lisi",21);
17         linkedList.addLast(stu2);
18         System.out.println(linkedList);
19         
20         //创建一个Student对象，并将其添加到LinkedList对象中
21         Student stu3 = new Student(3,"wangwu",22);
22         linkedList.addLast(stu3);
23         System.out.println(linkedList);
24         
25         System.out.println("linkedList.getFirst() = " + linkedList.getFirst());
26         
27         
28         //创建一个LinkedList对象
29         LinkedList<Student> linkedList1 = new LinkedList<Student>();
30         //此时会抛出异常
31         System.out.println("linkedList1.getFirst() = " + linkedList1.getFirst());
32     }
33 }
34 
35 运行结果:
36 [Student [stuId=1, stuName=zhangsan, stuAge=20]]
37 [Student [stuId=1, stuName=zhangsan, stuAge=20], Student [stuId=2, stuName=lisi, stuAge=21]]
38 [Student [stuId=1, stuName=zhangsan, stuAge=20], Student [stuId=2, stuName=lisi, stuAge=21], Student [stuId=3, stuName=wangwu, stuAge=22]]
39 linkedList.getFirst() = Student [stuId=1, stuName=zhangsan, stuAge=20]
40 Exception in thread "main" java.util.NoSuchElementException
41     at java.util.LinkedList.getFirst(LinkedList.java:242)
42     at LinkedListDemo.main(LinkedListDemo.java:31)

源代码:

 1     /*
 2        获取，但不移除此双端队列的第一个元素
 3     */
 4     public E getFirst() {
 5         //引用f指向此双端队列对象的头节点
 6         final Node<E> f = first;
 7         //如果此双端队列中没有节点元素，则抛出异常
 8         if (f == null)
 9             throw new NoSuchElementException();
10         //返回此双端队列头节点的值
11         return f.item;
12     }

(4) E getLast()

功能: 获取，但不移除此双端队列的最后一个元素

示例代码:

 1 import java.util.LinkedList;
 2 
 3 public class LinkedListDemo {
 4     public static void main(String[] args) {
 5         /*********测试LinkedList的'E getLast()'方法的使用**********/
 6         
 7         //创建一个LinkedList对象
 8         LinkedList<Student> linkedList = new LinkedList<Student>();
 9         
10         //创建一个Student对象，并将其添加到LinkedList对象中
11         Student stu1 = new Student(1,"zhangsan",20);
12         linkedList.addLast(stu1);
13         System.out.println(linkedList);
14         
15         //创建一个Student对象，并将其添加到LinkedList对象中
16         Student stu2 = new Student(2,"lisi",21);
17         linkedList.addLast(stu2);
18         System.out.println(linkedList);
19         
20         //创建一个Student对象，并将其添加到LinkedList对象中
21         Student stu3 = new Student(3,"wangwu",22);
22         linkedList.addLast(stu3);
23         System.out.println(linkedList);
24         
25         System.out.println("linkedList.getLast() = " + linkedList.getLast());
26         
27         
28         //创建一个LinkedList对象
29         LinkedList<Student> linkedList1 = new LinkedList<Student>();
30         //此时会抛出异常
31         System.out.println("linkedList1.getLast() = " + linkedList1.getLast());
32     }
33 }
34 
35 运行结果:
36 [Student [stuId=1, stuName=zhangsan, stuAge=20]]
37 [Student [stuId=1, stuName=zhangsan, stuAge=20], Student [stuId=2, stuName=lisi, stuAge=21]]
38 [Student [stuId=1, stuName=zhangsan, stuAge=20], Student [stuId=2, stuName=lisi, stuAge=21], Student [stuId=3, stuName=wangwu, stuAge=22]]
39 linkedList.getLast() = Student [stuId=3, stuName=wangwu, stuAge=22]
40 Exception in thread "main" java.util.NoSuchElementException
41     at java.util.LinkedList.getLast(LinkedList.java:255)
42     at LinkedListDemo.main(LinkedListDemo.java:31)

源代码:

 1     /*获取，但不移除此双端队列的最后一个元素*/
 2     public E getLast() {
 3         //引用l指向此双端队列对象的尾节点
 4         final Node<E> l = last;
 5         //如果此双端队列中没有节点元素，则抛出异常
 6         if (l == null)
 7             throw new NoSuchElementException();
 8         //返回此双端队列尾节点的值
 9         return l.item;
10     }

(5) E removeFirst()

功能: 获取并移除此双端队列第一个元素

示例代码:

 1 import java.util.LinkedList;
 2 
 3 public class LinkedListDemo {
 4     public static void main(String[] args) {
 5         /*********测试LinkedList的'E removeFirst()'方法的使用**********/
 6         
 7         //创建一个LinkedList对象
 8         LinkedList<Student> linkedList = new LinkedList<Student>();
 9         
10         //创建一个Student对象，并将其添加到LinkedList对象中
11         Student stu1 = new Student(1,"zhangsan",20);
12         linkedList.addLast(stu1);
13         System.out.println(linkedList);
14         
15         //创建一个Student对象，并将其添加到LinkedList对象中
16         Student stu2 = new Student(2,"lisi",21);
17         linkedList.addLast(stu2);
18         System.out.println(linkedList);
19         
20         //创建一个Student对象，并将其添加到LinkedList对象中
21         Student stu3 = new Student(3,"wangwu",22);
22         linkedList.addLast(stu3);
23         System.out.println(linkedList);
24         
25         System.out.println("linkedList.removeFirst() = " + linkedList.removeFirst());
26         System.out.println(linkedList);
27     }
28 }
29 
30 运行结果:
31 [Student [stuId=1, stuName=zhangsan, stuAge=20]]
32 [Student [stuId=1, stuName=zhangsan, stuAge=20], Student [stuId=2, stuName=lisi, stuAge=21]]
33 [Student [stuId=1, stuName=zhangsan, stuAge=20], Student [stuId=2, stuName=lisi, stuAge=21], Student [stuId=3, stuName=wangwu, stuAge=22]]
34 linkedList.removeFirst() = Student [stuId=1, stuName=zhangsan, stuAge=20]
35 [Student [stuId=2, stuName=lisi, stuAge=21], Student [stuId=3, stuName=wangwu, stuAge=22]]

源代码:

 1     /*
 2        获取并移除此双端队列第一个节点
 3     */
 4     public E removeFirst() {
 5         //引用f指向此双端队列对象的头节点
 6         final Node<E> f = first;
 7         //如果此双端队列中没有节点元素，则抛出异常
 8         if (f == null)
 9             throw new NoSuchElementException();
10         //调用内部方法unlinkFirst()方法
11         return unlinkFirst(f);
12     }
13 
14     /*
15       
16     */
17     private E unlinkFirst(Node<E> f) {
18         // assert f == first && f != null;
19         //记录此双端队列的头节点
20         final E element = f.item;
21         //记录此双端队列的头节点的下一个节点
22         final Node<E> next = f.next;
23 
24         //将引用设置null,帮助GC回收
25         f.item = null;
26         f.next = null; // help GC
27 
28         //赋值此双端队列对象的first属性 = next
29         first = next;
30         //如果此双端对象中只有一个节点，则设置此双端队列对象的last属性为null,否则设置next引用指向的节点的prev=null
31         if (next == null)
32             last = null;
33         else
34             next.prev = null;
35         //设置双端队列中元素个数减1
36         size--;
37         //fast-fail机制加1
38         modCount++;
39         //返回删除的节点
40         return element;
41     }

(6) E removeLast()

功能: 获取并移除此双端队列的最后一个元素

示例代码:

 1 import java.util.LinkedList;
 2 
 3 public class LinkedListDemo {
 4     public static void main(String[] args) {
 5         /*********测试LinkedList的'E removeLast()'方法的使用**********/
 6         
 7         //创建一个LinkedList对象
 8         LinkedList<Student> linkedList = new LinkedList<Student>();
 9         
10         //创建一个Student对象，并将其添加到LinkedList对象中
11         Student stu1 = new Student(1,"zhangsan",20);
12         linkedList.addLast(stu1);
13         System.out.println(linkedList);
14         
15         //创建一个Student对象，并将其添加到LinkedList对象中
16         Student stu2 = new Student(2,"lisi",21);
17         linkedList.addLast(stu2);
18         System.out.println(linkedList);
19         
20         //创建一个Student对象，并将其添加到LinkedList对象中
21         Student stu3 = new Student(3,"wangwu",22);
22         linkedList.addLast(stu3);
23         System.out.println(linkedList);
24         
25         System.out.println("linkedList.removeLast() = " + linkedList.removeLast());
26         System.out.println(linkedList);
27         
28         //创建一个LinkedList对象
29         LinkedList<Student> linkedList2 = new LinkedList<Student>();
30         //此方法将会抛出异常
31         linkedList2.removeLast();
32     }
33 }
34 
35 运行结果:
36 [Student [stuId=1, stuName=zhangsan, stuAge=20]]
37 [Student [stuId=1, stuName=zhangsan, stuAge=20], Student [stuId=2, stuName=lisi, stuAge=21]]
38 [Student [stuId=1, stuName=zhangsan, stuAge=20], Student [stuId=2, stuName=lisi, stuAge=21], Student [stuId=3, stuName=wangwu, stuAge=22]]
39 linkedList.removeLast() = Student [stuId=3, stuName=wangwu, stuAge=22]
40 [Student [stuId=1, stuName=zhangsan, stuAge=20], Student [stuId=2, stuName=lisi, stuAge=21]]
41 Exception in thread "main" java.util.NoSuchElementException
42     at java.util.LinkedList.removeLast(LinkedList.java:281)
43     at LinkedListDemo.main(LinkedListDemo.java:31)

源代码:

 1     /*
 2       获取并移除此双端队列最后一个节点
 3     */
 4     public E removeLast() {
 5         //引用l指向此双端队列对象的尾节点
 6         final Node<E> l = last;
 7         //如果此双端队列中没有节点元素，则抛出异常
 8         if (l == null)
 9             throw new NoSuchElementException();
10         //调用内部方法unlinkLast()
11         return unlinkLast(l);
12     }
13 
14     /*
15       获取并移除此双端队列最后一个节点
16     */
17     private E unlinkLast(Node<E> l) {
18         // assert l == last && l != null;
19         //记录此双端队列的尾节点
20         final E element = l.item;
21         //记录此双端队列的尾节点的前一个节点
22         final Node<E> prev = l.prev;
23         //将引用设置null,帮助GC回收
24         l.item = null;
25         l.prev = null; // help GC
26 
27         //赋值此双端队列对象的last属性 = prev
28         last = prev;
29         //如果此双端对象中只有一个节点，则设置此双端队列对象的first属性为null,否则设置prev引用指向的节点的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     }

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

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>

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

标签：

相关文章