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

发布于:2024-09-19 ⋅ 阅读:(123) ⋅ 点赞:(0)

前言:

        🌈✨前面小怡给大家介绍了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的底层是双向链表结构,由于链表没有将元素存储在连续的空间中,元素存储在单独的节点中,然后通过引用将节点连接起来了,因此在任意位置插入或者删除元素时,不需要搬移元素,效率比较高。

【说明】

  1. LinkedList 实现了List接口;
  2. LinkedList 的底层使用了双向链表;
  3. LinkedList 没有实现RandomAccess接口,因此LinkedList不支持随机访问。
  4. LinkedList 的任意位置插入和删除元素时效率比较高,时间复杂度为O(1);
  5. 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)
插入 空间不够时需要扩容 没有容量的概念
应用场景 元素高效存储+频繁访问 任意位置插入和删除频繁

 

 

 

 🌈✨ “逆境给人宝贵的磨炼机会。只有经得起环境考验的人,才能算是真正的强者。自古以来的伟人,大多是抱着不屈不挠的精神,从逆境中挣扎奋斗过来的”。