【Java】LinkedList实现类的使用

LinkedList实现类的使用

1. package com.star.test04;
3. import java.util.Iterator;
4. import java.util.LinkedList;
6. /**
7.  * @author : Starshine
8.  */
9. public class Test {
10.     //这是main方法，程序的入口
11.     public static void main(String[] args) {
12.         /*
13.         LinkedList常用方法：
14.         增加 addFirst(E e) addLast(E e)
15.              offer(E e) offerFirst(E e) offerLast(E e)
16.         删除 poll()
17.             pollFirst() pollLast()  ---》JDK1.6以后新出的方法，提高了代码的健壮性
18.             removeFirst() removeLast()
19.         修改
20.         查看 element()
21.              getFirst()  getLast()
22.              indexOf(Object o)   lastIndexOf(Object o)
23.              peek()
24.              peekFirst() peekLast()
25.         判断
26.          */
27.         //创建一个LinkedList集合对象：
28.         LinkedList<String> list = new LinkedList<>();
29.         list.add("aaaaa");
30.         list.add("bbbbb");
31.         list.add("ccccc");
32.         list.add("ddddd");
33.         list.add("eeeee");
34.         list.add("bbbbb");
35.         list.add("fffff");
37.         list.addFirst("jj");
38.         list.addLast("hh");
40.         list.offer("kk");//添加元素在尾端
41.         list.offerFirst("pp");
42.         list.offerLast("rr");
43.         System.out.println(list);//LinkedList可以添加重复数据
44.         System.out.println(list.poll());//删除头上的元素并且将元素输出
45.         System.out.println(list.pollFirst());
46.         System.out.println(list.pollLast());
48.         System.out.println(list.removeFirst());
49.         System.out.println(list.removeLast());
50.         System.out.println(list);//LinkedList可以添加重复数据
52.         /*list.clear();//清空集合
53.         System.out.println(list);*/
54.         /*System.out.println(list.pollFirst());*/
55.         /*System.out.println(list.removeFirst());报错：Exception in thread "main" java.util.NoSuchElementException*/
58.         //集合的遍历：
59.         System.out.println("---------------------");
60.         //普通for循环：
61.         for(int i = 0;i<list.size();i++){
62.             System.out.println(list.get(i));
63.         }
64.         System.out.println("---------------------");
65.         //增强for：
66.         for(String s:list){
67.             System.out.println(s);
68.         }
69.         System.out.println("---------------------");
70.         //迭代器：
71.         /*Iterator<String> it = list.iterator();
72.         while(it.hasNext()){
73.             System.out.println(it.next());
74.         }*/
75.         //下面这种方式好，节省内存
76.         for(Iterator<String> it = list.iterator();it.hasNext();){
77.             System.out.println(it.next());
78.         }
79.     }
80. }

LinkedList简要底层原理图

模拟LinkedList源码

1. package com.star.test05;
3. /**
4.  * @author : Starshine
5.  */
6. public class MyLinkedList {
7.     //链中一定有一个首节点：
8.     Node first;
9.     //链中一定有一个尾节点：
10.     Node last;
11.     //计数器：
12.     int count = 0;
13.     //提供一个构造器：
14.     public MyLinkedList(){
16.     }
17.     //添加元素方法：
18.     public void add(Object o){
19.         if(first == null){//证明你添加的元素是第一个节点：
20.             //将添加的元素封装为一个Node对象：
21.             Node n = new Node();
22.             n.setPre(null);
23.             n.setObj(o);
24.             n.setNext(null);
25.             //当前链中第一个节点变为n
26.             first = n;
27.             //当前链中最后一个节点变为n
28.             last = n;
29.         }else{//证明已经不是链中第一个节点了
30.             //将添加的元素封装为一个Node对象：
31.             Node n = new Node();
32.             n.setPre(last);//n的上一个节点一定是当前链中的最后一个节点last
33.             n.setObj(o);
34.             n.setNext(null);
35.             //当前链中的最后一个节点的下一个元素 要指向n
36.             last.setNext(n);
37.             //将最后一个节点变为n
38.             last = n;
39.         }
40.         //链中元素数量加1
41.         count++;
42.     }
44.     //得到集合中元素的数量：
45.     public int getSize(){
46.         return count;
47.     }
49.     //通过下标得到元素：
50.     public Object get(int index){
51.         //获取链表的头元素：
52.         Node n = first;
53.         //一路next得到想要的元素
54.         for(int i=0;i<index;i++){
55.             n = n.getNext();
56.         }
57.         return n.getObj();
58.     }
59. }
60. class Test{
61.     //这是main方法，程序的入口
62.     public static void main(String[] args) {
63.         //创建一个MyLinkedList集合对象：
64.         MyLinkedList ml = new MyLinkedList();
65.         ml.add("aa");
66.         ml.add("bb");
67.         ml.add("cc");
68.         System.out.println(ml.getSize());
69.         System.out.println(ml.get(0));
70.     }
71. }

debug验证数据添加成功：

LinkedList源码解析

【1】JDK1.7和JDK1.8的LinkedList的源码是一致的

【2】源码：

1. public class LinkedList<E>{//E是一个泛型，具体的类型要在实例化的时候才会最终确定
2.         transient int size = 0;//集合中元素的数量
3.         //Node的内部类
4.         private static class Node<E> {
5.         E item;//当前元素
6.         Node<E> next;//指向下一个元素地址
7.         Node<E> prev;//上一个元素地址
9.         Node(Node<E> prev, E element, Node<E> next) {
10.             this.item = element;
11.             this.next = next;
12.             this.prev = prev;
13.         }
14.     }
16.         transient Node<E> first;//链表的首节点
17.         transient Node<E> last;//链表的尾节点
18.         //空构造器：
19.         public LinkedList() {
20.     }
21.         //添加元素操作：
22.         public boolean add(E e) {
23.         linkLast(e);
24.         return true;
25.     }
26.         void linkLast(E e) {//添加的元素e
27.         final Node<E> l = last;//将链表中的last节点给l 如果是第一个元素的话 l为null
28.                 //将元素封装为一个Node具体的对象：
29.         final Node<E> newNode = new Node<>(l, e, null);
30.                 //将链表的last节点指向新的创建的对象：
31.         last = newNode;
32.                
33.         if (l == null)//如果添加的是第一个节点
34.             first = newNode;//将链表的first节点指向为新节点
35.         else//如果添加的不是第一个节点
36.             l.next = newNode;//将l的下一个指向为新的节点
37.         size++;//集合中元素数量加1操作
38.         modCount++;
39.     }
40.         //获取集合中元素数量
41.         public int size() {
42.         return size;
43.     }
44.         //通过索引得到元素：
45.         public E get(int index) {
46.         checkElementIndex(index);//健壮性考虑
47.         return node(index).item;
48.     }
49.        
50.     Node<E> node(int index) {
51.         //如果index在链表的前半段，那么从前往后找
53.         if (index < (size >> 1)) {
54.             Node<E> x = first;
55.             for (int i = 0; i < index; i++)
56.                 x = x.next;
57.             return x;
58.         } else {//如果index在链表的后半段，那么从后往前找
59.             Node<E> x = last;
60.             for (int i = size - 1; i > index; i--)
61.                 x = x.prev;
62.             return x;
63.         }
64.     }
66. }

面试题：iterator(),Iterator,Iterable关系

【1】面试题：对应的关系：

【2】hasNext(),next()的具体实现：

【3】增强for循环  底层也是通过迭代器实现的：

ListIterator迭代器

【1】加入字符串：

1. package com.star.test06;
3. import java.util.ArrayList;
4. import java.util.Iterator;
5. import java.util.List;
7. /**
8.  * @author : Starshine
9.  */
10. public class Test2 {
11.     //这是main方法，程序的入口
12.     public static void main(String[] args) {
13.         ArrayList<String> list = new ArrayList<>();
14.         list.add("aa");
15.         list.add("bb");
16.         list.add("cc");
17.         list.add("dd");
18.         list.add("ee");
19.         //在"cc"之后添加一个字符串"kk"
20.         Iterator<String> it = list.iterator();
21.         while(it.hasNext()){
22.             if("cc".equals(it.next())){
23.                 list.add("kk");
24.             }
25.         }
27.     }
28. }

发现报错：

出错原因：就是迭代器和list同时对集合进行操作：

解决办法：事情让一个“人”做 --》引入新的迭代器：ListIterator

迭代和添加操作都是靠ListIterator来完成的：

1. package com.star.test06;
3. import java.util.ArrayList;
4. import java.util.Iterator;
5. import java.util.List;
6. import java.util.ListIterator;
8. /**
9.  * @author : Starshine
10. */
11. public class Test2 {
12.     //这是main方法，程序的入口
13.     public static void main(String[] args) {
14.         ArrayList<String> list = new ArrayList<>();
15.         list.add("aa");
16.         list.add("bb");
17.         list.add("cc");
18.         list.add("dd");
19.         list.add("ee");
20.         //在"cc"之后添加一个字符串"kk"
21.         ListIterator<String> it = list.listIterator();
22.         while(it.hasNext()){
23.             if("cc".equals(it.next())){
24.                 it.add("kk");
25.             }
26.         }
27.         System.out.println(it.hasNext());
28.         System.out.println(it.hasPrevious());
29.         //逆向遍历：
30.         while(it.hasPrevious()){
31.             System.out.println(it.previous());
32.         }
33.         System.out.println(it.hasNext());
34.         System.out.println(it.hasPrevious());
35.         System.out.println(list);
37.     }
38. }