LinkedList （概念、使用，遍历，以及与ArrayList的区别）_linkedlist怎么区分使用

**List 的实现类之二--------LinkedList **

当在 ArrayList 任意位置进行插入或者删除元素时，需要将后序元素整体往前或往后搬移，时间复杂度为O(n)，效率比较低，因此：Java 集合中又引入了另一种结构 ：LinkedList，即链表结构;

LinkedList 介绍

LinkedList 是一个普通的类，底层采用链表结构，它继承自 AbstractList, 实现了 List 、Deque、Cloneable和 Serializable 等接口；

LinkedList 使用

LinkedList 的 2 种构造方式

由于底层结构是链表，所以没有容量一说，因此构造方式 比 ArrayList 少一个；

• 无参构造 LinkedList()

 List<Integer> list1=new LinkedList<>();
1

• 利用其他 Collection 中的元素构造： public LinkedList(Collection<? extends E> c)

 List<String> al = new ArrayList<>();
        al.add("111");
        al.add("222");
       //使用其他容器构造
       List<String> list1=new LinkedList<>(al);
       System.out.println(list1); //[111, 222]
1
2
3
4
5
6

LinkedList 的常见方法

（1） public boolean add(E e)： 尾部插入元素 e

 List<String> list=new LinkedList();
       list.add("0000");
       list.add("1111");
     System.out.println(list);  //[0000, 1111]
1
2
3
4

(2) public void add(int index, E e): 在index 位置插入e

 List<String> list=new LinkedList();
     list.add("0000");
     list.add("1111");
     list.add(0,"5555");
     System.out.println(list); //[5555, 0000, 1111]
1
2
3
4
5

(3) public boolean addAll(Collection<? extends E> c)：尾部插入 c 中的元素

//将list中的所有元素插入到list1中
   List<String> list=new LinkedList();
        list.add("0000");
        list.add("1111");
        List<String> list1=new LinkedList<>();
        list1.addAll(list);  
        System.out.println(list1); //[0000,1111]
1
2
3
4
5
6
7

（4） public int size()：获取有效元素的个数

   System.out.println(list.size());
1

(5) public E remove(int index) :删除 index 位置元素

 List<String> list=new LinkedList();
        list.add("0000");
        list.add("1111");
        list.remove(1);
        System.out.println(list); //[0000]
1
2
3
4
5

(6) public boolean remove(E e) ：删除指定元素 e

 List<String> list=new LinkedList();
        list.add("0000");
        list.add("1111");
        list.remove("0000");
        System.out.println(list);//[1111]
1
2
3
4
5

(7) public boolean contains(E e）：是否包含元素 e

 List<String> list=new LinkedList();
     list.add("0000");
     list.add("1111");
     //包含返回true
     System.out.println(list.contains("0000")); 
      //不包含，返回false
    System.out.println(list.contains("9999"));
1
2
3
4
5
6
7

（8）public E get(int index)：获取 index 位置元素

List<String> list=new LinkedList();
      list.add("0000");
      list.add("1111");
   System.out.println(list.get(1)); //1111
1
2
3
4

(9) public E set(int index, E e)：将 index 位置元素设置为 e

List<String> list=new LinkedList();
        list.add("0000");
        list.add("1111");
        list.set(1,"2222");
     System.out.println(list);//[0000, 2222]
1
2
3
4
5

(10) public int indexOf(E e)：从前往后找，返回第一次 e 出现的下标

List<String> list=new LinkedList();
        list.add("0000");
        list.add("3333");
        list.add(1,"0000");
    System.out.println(list.indexOf("0000"));//0
1
2
3
4
5

(11) public int lastIndexOf(E e)：从后往前找，返回第一次 e出现的下标

List<String> list=new LinkedList();
        list.add("0000");
        list.add("3333");
        list.add(1,"0000");
     System.out.println(list.lastIndexOf("0000")); // 1
1
2
3
4
5

(12) public List<E> subList(int fromIndex, int toIndex)：截取 [fromIndex,toIndex) 部分

 List<String> list=new LinkedList();
        list.add("0000");
        list.add("1111");
        list.add("2222");
        list.add("3333");
        list.add("4444");
  System.out.println(list.subList(1,4));//[1111, 2222, 3333]
1
2
3
4
5
6
7

(13) public boolean isEmpty()：判定链表是否为空

 System.out.println(list.isEmpty());
1

(14) public void clear()：清空

 list.clear();
System.out.println(list.size()); //0
1
2

LinkedList 的遍历

两种遍历方式：
foreach
迭代器遍历

package day20211018;
import java.util.List;
import java.util.LinkedList;
import java.util.ListIterator;
public class Test {
    public static void main(String[] args) {
        LinkedList<Integer> list = new LinkedList<>();
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        // foreach 遍历
        for (int e:list) {
            System.out.print(e + " ");
        }
        System.out.println(); // 1 2 3 4
            // 迭代器遍历
            ListIterator<Integer> it = list.listIterator();
            while(it.hasNext()){
                System.out.print(it.next()+ " ");
            }
            System.out.println(); //1 2 3 4
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

补充----链表

链表的概念

链表在物理上：是一种非连续的存储结构；
在逻辑上：数据元素的逻辑顺序是通过链表中的引用来依次链接的；
生活中的实例：类似于火车的结构

链表中的元素存储在一个一个的结点之中；

结点中包含有两个字段：
value：每个结点中元素的值域
next：用来指向下一个结点

需要注意的是：每个结点都是一个对象，而 next只是个引用，并不是对象；

链表的常见结构

• 单向链表与双向链表

单向链表：

双向链表：

• 带头链表与不带头链表

不带头结点：

带头结点链表：

• 循环链表与非循环链表

非循环链表：

循环链表：

注：组合起来就有 8 种结构

链表实现

• （1 ） 模拟实现不带头结点的单链表

package day20211018;

   //模拟实现：不带头结点的单链表
public class SingleLinkList<E> {
   public static class Node<E> {
      E value;
      Node<E> next;

      //构造方法
      public Node(E value) {
         this.value = value;
      }
   }
      Node<E> head; //用来指向链表中的第一个有效结点
      //获取单链表的有效长度
      public int size(){
         Node<E> cur=head;
         int count=0;
         while(null != cur){
            count++;
            cur=cur.next;
         }
         return count;
      }


      // 头插 e
      public void addFirst(E e){
         Node<E> newNode=new  Node<>(e);
         if(null==head){
            head=newNode;
         }else{
            newNode.next=head;
            head=newNode;
         }
      }


      // 尾插e
      public void addLast(E e) {
         Node<E> newNode = new Node<>(e);
         if (null == head) {
            head = newNode;
         } else {
            //找最后一个结点
            //cur 指向第一个结点
            Node<E> cur = head;
            //pre 来标记最后一个结点的位置
            Node<E> pre = null;
            while (null != cur) {
               pre = cur;
               cur = cur.next;
            }
            //插入新结点
            pre.next = newNode;
         }
      }
      //任意位置插入e,第一个数据结点为0号位置
      public boolean addIndex(int position,E e){
         //1.检测参数是否合法
         if(position < 0 || position >= 4){
            throw new IllegalArgumentException("参数不合法");
         }
         if(0==position){
            addFirst(e);
            return true;
         }
         //2.找到position位置的结点，并将其前一个保存(插在position位置的前面)
         Node<E> cur=head;
         Node<E> pre=null;
         while(0 != position){
            pre=cur;
            cur=cur.next;
            position--;
         }
         //3 插入新结点

         Node<E> newNode=new Node<E>(e);
         newNode.next=cur;
         pre.next=newNode;

         return true;
      }

      //删除第一次出现关键字为e的结点
      public void remove(E e){
         Node<E> cur=head;
         Node<E> prev=null;
         //prev 用来标记cur
         while(null != cur){
            if(e.equals(cur.value)){
               cur.value=null;
               if(prev==null){
                  //说明删除的是第一个结点
                 head=cur.next;
            }else{
                  //删除其他结点
                  prev.next=cur.next;
               }
            return;
            }
            prev=cur;
            cur=cur.next;
         }
      }

      //删除所有值为e的结点
     public void removeAllKey(E e) {
        //时间复杂度O(N^2)
        /*while(contains(e)){
           remove(e);
        }*/
        Node<E> cur=head;
        Node<E> prev=null;
        while(null!= cur){
           if(e.equals(cur.value)){
              //删除结点
              cur.value=null;
              if(prev==null){
                 head=cur.next;
                 cur=head;
              }else{
                 prev.next=cur.next;
                 cur=prev.next;
              }

           }else{
              prev=cur;
              cur=cur.next;
           }

        }
      }

      //查找是否包含关键字 e
      public boolean contains(E e) {
         Node<E> cur=head;
         while(null!=cur){
            if(e.equals(cur.value)){
               return true;
            }
            cur=cur.next;
         }
         return false;
      }
     
      @Override
      public String toString(){
         Node<E> cur=head;
         String s="[";
         while(null!= cur){
            s+=cur.value;
            if(null !=cur.next){
               s+=",";
            }

            cur=cur.next;
         }
         s+="]";
         return s;
      }

      public static void main(String[] args) {
         SingleLinkList<Integer> s=new SingleLinkList<>();
         System.out.println(s); //[]
         //测试尾插
         s.addLast(1);
         s.addLast(2);
         s.addLast(3);
         s.addLast(4);
         System.out.println(s); //[1,2,3,4]
         System.out.println(s.size()); //4
         //测试是否包含元素e
         System.out.println(s.contains(2)); //true
         System.out.println(s.contains(5)); //false
         //测试头插
         s.addFirst(0);
         System.out.println(s);  //[0,1,2,3,4]
         //测试任意位置插入
         s.addIndex(0,0);
         System.out.println(s); //[0,0,1,2,3,4]
         s.addIndex(3,5);
         System.out.println(s); //[0,0,1,5,2,3,4]
         //删除所有值为0的元素
         s.removeAllKey(0);
         System.out.println(s); //[1,5,2,3,4]
         //测试remove
         s.remove(5);
         System.out.println(s); //[1,2,3,4]
      }
   }


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193

动起小手往下戳~~

• （2）模拟实现双链表 LinkedList（点开就能找到啦~~）

总结—ArrayList 与 LinkedList 的联系与区别

• 相同点：两者均实现了 List 接口；
• 不同点体现在以下方面：

（1）由于ArrayList 底层采用数组来存储元素,支持随机访问；
（2）LinkedList 底层采用双向链表结构，不支持随机访问；
（3）ArrayList 支持扩容，LinkedList 没有扩容这个概念；
（4）在存储空间上：ArrayList 在物理上是一定连续的，LinkedList 逻辑上是连续的，但物理上不一定连续；
（5）在任意位置进行元素的插入与删除时，ArrayList 需要通过搬移元素后，将位置腾出后，才可以进行插入，因此，时间复杂度为O(N)，效率慢；
LinkedList 只需要修改引用的指向即可，时间复杂度为O(1)，效率较高；
换句话说：在元素进行高效访问时，优先考虑 ArrayList，在进行任意位置插入与删除元素时，优先考虑 **LinkedList**.