【JavaDS】浅谈集合LinkedList的使用

た入场券 2023-09-26 10:03 168阅读 0赞

![在这里插入图片描述][078b66f87e3c4e309d7f34d79c5776c4.gif_pic_center]✨**博客主页:**[ **XIN-XIANG荣**][_XIN-XIANG]  
✨**系列专栏:**[**【Java实现数据结构】**][Java]  
✨**一句短话:** **难在坚持,贵在坚持,成在坚持!**

#### 文章目录 ####

*  一. 什么是LinkedList?
 *  二. LinkedList的使用
 *   *  1. 构造方法
     *  2. 常用方法
     *  3. LinkedList的遍历
 *  三. ArrayList和LinkedList的区别

## 一. 什么是LinkedList? ##

LinkedList的底层是双向链表结构，由于链表没有将元素存储在连续的空间中，元素存储在单独的节点中，然后通过引用将节点连接起来了，因此在在任意位置插入或者删除元素时，不需要搬移元素，效率比较高。

![img][]

在集合框架中，LinkedList也实现了List接口，具体如下：

![img][img 1]

【说明】

1.  LinkedList实现了List接口
2.  LinkedList的底层使用了双向链表
3.  LinkedList没有实现RandomAccess接口，因此LinkedList不支持随机访问
4.  LinkedList的任意位置插入和删除元素时效率比较高，时间复杂度为O(1)

## 二. LinkedList的使用 ##

### 1. 构造方法 ###

<table> 
 <thead> 
  <tr> 
   <th><strong>方法</strong></th> 
   <th><strong>解释</strong></th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>LinkedList()</td> 
   <td>无参构造 , 创建一个新的空linkedList</td> 
  </tr> 
  <tr> 
   <td>LinkedList(Collection&lt;? extends E&gt; c)</td> 
   <td>一个其他集合容器中元素构造List</td> 
  </tr> 
 </tbody> 
</table>

代码示例:

public static void main(String[] args) {
        
            // 构造一个空的LinkedList
            List<Integer> list1 = new LinkedList<>();
            List<String> list2 = new java.util.ArrayList<>();
            list2.add("张三");
            list2.add("李四");
            list2.add("王五");
            // 使用ArrayList构造LinkedList
            List<String> list3 = new LinkedList<>(list2);
        }

### 2. 常用方法 ###

<table> 
 <thead> 
  <tr> 
   <th><strong>方法</strong></th> 
   <th><strong>解释</strong></th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>boolean add(E e)</td> 
   <td>尾插 e</td> 
  </tr> 
  <tr> 
   <td>void add(int index, E element)</td> 
   <td>将 e 插入到 index 位置</td> 
  </tr> 
  <tr> 
   <td>boolean addAll(Collection&lt;? extends E&gt; c)</td> 
   <td>尾插 c 中的元素</td> 
  </tr> 
  <tr> 
   <td>boolean addAll(int index, Collection&lt;? extends E&gt; c)</td> 
   <td>将 c 中的元素添加到指定位置</td> 
  </tr> 
  <tr> 
   <td>E remove(int index)</td> 
   <td>删除 index 位置元素</td> 
  </tr> 
  <tr> 
   <td>boolean remove(Object o)</td> 
   <td>删除遇到的第一个 o</td> 
  </tr> 
  <tr> 
   <td>E remove()</td> 
   <td>删除第一个元素</td> 
  </tr> 
  <tr> 
   <td>E removeFirst()</td> 
   <td>删除第一个元素</td> 
  </tr> 
  <tr> 
   <td>E removeLast()</td> 
   <td>删除最后一个元素</td> 
  </tr> 
  <tr> 
   <td>E get(int index)</td> 
   <td>获取下标 index 位置元素</td> 
  </tr> 
  <tr> 
   <td>E set(int index, E element)</td> 
   <td>将下标 index 位置元素设置为 element</td> 
  </tr> 
  <tr> 
   <td>void clear()</td> 
   <td>清空</td> 
  </tr> 
  <tr> 
   <td>boolean contains(Object o)</td> 
   <td>判断 o 是否在线性表中</td> 
  </tr> 
  <tr> 
   <td>int indexOf(Object o)</td> 
   <td>返回第一个 o 所在下标</td> 
  </tr> 
  <tr> 
   <td>int lastIndexOf(Object o)</td> 
   <td>返回最后一个 o 的下标</td> 
  </tr> 
  <tr> 
   <td>List subList(int fromIndex, int toIndex)</td> 
   <td>截取部分 list</td> 
  </tr> 
  <tr> 
   <td>int size()</td> 
   <td>返回链表元素个数</td> 
  </tr> 
 </tbody> 
</table>

代码示例:

public static void main(String[] args) {
        
            LinkedList<Integer> list = new LinkedList<>();
            list.add(1); // add(elem): 表示尾插
            list.add(2);
            list.add(3);
            list.add(4);
            list.add(5);
            list.add(6);
            list.add(7);
            System.out.println(list.size());
            System.out.println(list);
    
            // 在起始位置插入0
            list.add(0, 0); // add(index, elem): 在index位置插入元素elem
            System.out.println(list);
    
            list.remove(); // remove(): 删除第一个元素，内部调用的是removeFirst()
            list.removeFirst(); // removeFirst(): 删除第一个元素
            list.removeLast(); // removeLast(): 删除最后元素
            list.remove(1); // remove(index): 删除index位置的元素
            System.out.println(list);
    
            // contains(elem): 检测elem元素是否存在，如果存在返回true，否则返回false
            if(!list.contains(1)){
        
                list.add(0, 1);
            }
            list.add(1);
            System.out.println(list);
    
            System.out.println(list.indexOf(1)); // indexOf(elem): 从前往后找到第一个elem的位置
            System.out.println(list.lastIndexOf(1)); // lastIndexOf(elem): 从后往前找第一个1的位置
    
            int elem = list.get(0); // get(index): 获取指定位置元素
            System.out.println(elem);
    
            list.set(0, 100); // set(index, elem): 将index位置的元素设置为elem
            System.out.println(list);
    
            // subList(from, to): 用list中[from, to)之间的元素构造一个新的LinkedList返回
            List<Integer> copy = list.subList(0, 3);
            System.out.println(list);
            System.out.println(copy);
    
            list.clear(); // 将list中元素清空
            System.out.println(list.size());
        }

执行结果:

![img][img 2]

### 3. LinkedList的遍历 ###

*  通过for循环或者foreach遍历

public static void main(String[] args) {
        
            LinkedList<Integer> list = new LinkedList<>();
            list.add(1); // add(elem): 表示尾插
            list.add(2);
            list.add(3);
            list.add(4);
            list.add(5);
            list.add(6);
            list.add(7);
            //通过for循环遍历
            int size = list.size();
            for (int i = 0; i < size; i++) {
        
                System.out.print(list.get(i)+" ");
            }
            System.out.println();
            //通过foreach遍历
            for (int e:list) {
        
                System.out.print(e + " ");
            }
            System.out.println();
        }

![img][img 3]

*  通过迭代器遍历

public static void main(String[] args) {
        
            LinkedList<Integer> list = new LinkedList<>();
            list.add(1); // add(elem): 表示尾插
            list.add(2);
            list.add(3);
            list.add(4);
            list.add(5);
            list.add(6);
            list.add(7);
    
            // 使用迭代器遍历---正向遍历
            ListIterator<Integer> it = list.listIterator();
            while(it.hasNext()){
        
                System.out.print(it.next()+ " ");
            }
            System.out.println();
            // 此时迭代器指向的是链表最后一个元素后面的位置
            // 此时不能再去正向遍历, 因为后面已经没有元素了, 只能去反向遍历
            // 使用反向迭代器---反向遍历
            ListIterator<Integer> rit = list.listIterator(list.size());
            while (rit.hasPrevious()){
        
                System.out.print(rit.previous() +" ");
            }
            System.out.println();
        }

![img][img 4]

## 三. ArrayList和LinkedList的区别 ##

<table> 
 <thead> 
  <tr> 
   <th><strong>不同点</strong></th> 
   <th><strong>ArrayList</strong></th> 
   <th><strong>LinkedList</strong></th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>存储空间上</td> 
   <td>物理上一定连续</td> 
   <td>逻辑上连续 , 但物理上不一定连续</td> 
  </tr> 
  <tr> 
   <td>随机访问</td> 
   <td>支持 : 时O(1)</td> 
   <td>不支持 : 时O(N)</td> 
  </tr> 
  <tr> 
   <td>插入/删除</td> 
   <td>需要搬移元素 , 效率低 , 时O(N)</td> 
   <td>只需要修改引用的指向 , 时O(1)</td> 
  </tr> 
  <tr> 
   <td>插入</td> 
   <td>空间不够时需要扩容</td> 
   <td>没有容量的概念</td> 
  </tr> 
  <tr> 
   <td>应用场景</td> 
   <td>有限元素个数高效存储+频繁访问</td> 
   <td>任意位置插入和删除频繁</td> 
  </tr> 
 </tbody> 
</table>

[078b66f87e3c4e309d7f34d79c5776c4.gif_pic_center]: https://img-blog.csdnimg.cn/078b66f87e3c4e309d7f34d79c5776c4.gif#pic_center
[_XIN-XIANG]: https://blog.csdn.net/Trong_?spm=1000.2115.3001.5343
[Java]: https://blog.csdn.net/trong_/category_11997769.html
[img]: https://img-blog.csdnimg.cn/img_convert/be6d4648e793e9a4d9938538282f77fd.png
[img 1]: https://img-blog.csdnimg.cn/img_convert/28fe3255643f1d1d255dc92eb7c45143.png
[img 2]: https://img-blog.csdnimg.cn/img_convert/193992d909b7c056905c08ef36a47bdb.png
[img 3]: https://img-blog.csdnimg.cn/img_convert/106a0b584e6878f2702fb31e661b804f.png
[img 4]: https://img-blog.csdnimg.cn/img_convert/f5c390073f2ad6a8955250a610fe4417.png