小怡分享之数据结构LinkedList与链表

前言：

🌈✨前面小怡给大家介绍了ArrayList，今天小怡给大家介绍一下链表。

1.ArrayList的缺陷

当在ArrayList任意位置插入或者删除元素时，就需要后续元素整体往前或者往后搬移，时间复杂度为O（n），效率比较低，因此ArrayList不适合做任意位置插入和删除比较多的场景。因此：Java集合中又引入了LinkedList，即链表结构。

2.链表

2.1 链表的概念和结构

链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的引用连接次序实现的。

实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：

1.单向或者双向

2.带头或者不带头

3.循环或者非循环

虽然有很多的链表结构，但是我们重点掌握两种：

无头单向非循环链表：结构简单，一般不会单独用来存数据。实际上更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。

无头双向链表：在Java的集合框架库中LinkedList底层实现就是无头双向循环链表。

2.2 链表的实现

public class SingleList {
    //头插法
    public void addFirst(int data){
        }
    //尾插法
    public void addLast(int data){
    }
    //任意位置插入，，第一个数据节点为0号下标
    public void addIndex(int index,int data){
    }
    //查找是否包含关键字key是否在单链表当中
    public boolean contains(int key){
        return false;
    }
    //删除第一次出现关键字为key的节点
    public void remove(int key){
    }
    //删除所有值为key的节点
    public void removeAllKey(int key){
    }
    //得到单链表的长度
    public int size(){
        return -1;
    }
    public void clear(){
    }
    public void display(){
    }
}

3.LinkedList的模拟实现

//2.无头双向链表实现
public class MyLinkedList{
   //头插法
   public void addFirst(int data){}
   //尾插法
   public void addLast(int data){}
   //任意位置插入，第一个数据节点为0号下标
   public void addIndex(int index,int data){}
   //查找是否包含关键字key是否在单链表当中
   public boolean contains(int key){}
   //删除第一次出现关键字为key的节点
   public void remove(int key){}
   //删除所有值为key的节点
   puvlic void removeAllKey(int key){}
   //得到单链表的长度
   public int size(){}
   public void displaay(){}
   public void clear(){}
}

4.LinkedList的使用

4.1 什么是LinkedList

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

【说明】

LinkedList 实现了List接口；
LinkedList 的底层使用了双向链表；
LinkedList 没有实现RandomAccess接口，因此LinkedList不支持随机访问。
LinkedList 的任意位置插入和删除元素时效率比较高，时间复杂度为O（1）；
LinkedList 比较适合任意位置插入的场景。

4.2 LinkedList的使用

1.LinkedList的构造

方法	解释
LinkedList（）	无参构造
public LinkedList(Collection<?extends E>c)	使用其他集合容器中元素构造List

public class Main {
 public static void main(String[] args) {
    List<Integer> list1=new LinkedList<>();
    List<Integer> list2=new java.util.ArrayList<>();
    list2.add("JavaSE");
    List<String> list3=new LinkedList<>(list2);
    }
}

2.LinkedList的其他常用方法介绍

方法	解释
boolean add(E e)	尾插e
void add(int index,E element)	将e插入到index位置
boolean addAll(Collection<?extends E>c)	尾插c中的元素
E remove (int index)	删除index位置元素
boolean remove (Object o)	删除遇到的第一个o
E get(int index)	获取下标index位置元素
E set(int index,E element)	将下标index位置元素设置为element
void clear()	清空
boolean contains(Object o)	判断o是否在线性表中
int indexOf(Object o)	返回第一个o所在下标
int lstIndexOf(Object o)	返回最后一个o的下标
List<E>subList(int fromIndex,int toIndex)	截取部分list

3LinkedList的遍历

5.ArrayList和LinkedList的区别

不同点	ArrayList	LinkedList
存储空间上	物理上一定连续	逻辑上连续，但物理上不一定连续
随机访问	支持O（1）	不支持：O（N）
头插	需要搬移元素，效率低O（N）	只需修改引用的指向，时间复杂度为O（1）
插入	空间不够时需要扩容	没有容量的概念
应用场景	元素高效存储+频繁访问	任意位置插入和删除频繁