不良人系列--复兴数据结构（链表篇）

！

晴曛398

1759人浏览 · 2024-12-11 08:00:00

晴曛398 · 2024-12-11 08:00:00 发布

个人主页：爱编程的小新

不良人经典语录：”群雄侠隐仗剑，红颜相许半生”

3.1 LinkedList的常见方法和使用

3.2 LinkedList的遍历

3.3 LinkedList的优缺点

四. ArrayList和LinkedList的区别

结语

在上期我们讲述了顺序表的概念和用法，但是顺序表的底层实际上是由数组实现的，当进行插入和删除元素的时候，时间复杂度为O(n)，效率是很低的，所以为了提升效率，那么就引入了链表的概念。

一. 链表的概念

链表与顺序表都是线性表中的一种，链表和顺序表在逻辑上都是连续的，但是链表是一种物理存储结构上非连续的存储结构，链表就像火车是由一个一个节点通过引用链接实现的：

链表的分类：有头链表和无头链表

有头链表：即头结点不存储实际数据，其指针指向第一个存储数据的节点；
无头链表：即没有头节点的链表，第一个节点直接存储数据，链表的头指针直接指向的就是第一个实际存储数据的节点；

二. 链表的结构特点

我们知道链表是由一系列节点组成的，每个节点又分为两个部分：数据域和指针域；那么我们来看一下几个链表结构。

2.1 单向链表和双向链表

单向链表：

1.节点结构：

数据域：用来存放数据元素
指针域：用来存放下一个节点的地址

2.特点：

单链表的节点只能通过指针指向下一个节点。形成一个单向的链状结构
只能从前往后的顺序的访问链表，无法从当前节点访问到前一个节点

双向链表：

1.节点结构：

数据域：与单链表一样，用来存放数据元素
指针域：拥有两个指针，一个指向前驱节点，一个指向后继节点

2.特点：

双链表可以从当前节点向前或者向后遍历链表，增加了操作的灵活性
在删除节点时，双链表比单链表更加方便，可以直接通过前驱结点找到前一个节点

2.2循环链表和非循环链表

循环链表：

1. 定义：

循环链表是一种特殊的链表结构，在单向循环链表中，最后一个节点的指针域指向的不是null，而是该链表的头结点，从而形成一个环
在双向链表中，不仅最后一个节点的后继指针指向头结点，头结点的前驱节点也指向最后一个节点，形成双向的循环结构

非循环链表：

1.定义：

单向非循环链表每个节点只有指向下一个节点的指针，并且最后一个节点的指针域指向null
双向非循环链表每个节点有两个指针，分别指向前驱节点和后继节点，头指针的前驱指针为null，尾结点的后继指针为null

三.LinkedList

在Java中LinkedList是Java集合框架中的一个类，它实现了List接口，因此具有List的基本特征，LinkedList的底层是双向链表结构，使得它可以高效的在链表的任何位置进行插入和删除操作

LinkList的查阅文档

3.1 LinkedList的常见方法和使用

LinkedList的常见方法：

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

LinkedList中方法的使用：

 public static void main(String[] args) {
        //实例化链表
        LinkedList<Integer>list=new LinkedList<>();
        LinkedList<Integer>list2=new LinkedList<>();
        //尾插
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        list.add(5);
        list2.add(1);
        list2.add(2);
        list2.add(3);
        System.out.println("list中元素："+list);//打印链表1中的元素
        System.out.println("list2中的元素："+list2);//打印链表2中的元素
        list.add(0,0);//将0插入下标为0的位置
        list.addAll(list2);//将list2中的元素从尾部插入到list中、
        System.out.println("================");
        System.out.println("添加元素后的list中的元素："+list);//打印当前list中的元素
        list.remove(0);//删除0位置的元素
        list.remove((Object)1);//删除链表中遇到的第一个1
        System.out.println("================");
        System.out.println("删除元素后的list中的元素："+list);//打印当前list中的元素
        System.out.println("获得下标为5的元素："+list.get(5));
        list.set(5,10);//将下标5位置的元素改成10;
        System.out.println("将下标5位置的元素改变后的元素："+list.get(5));
        System.out.println("判断10是否在链表中："+list.contains(10));
        System.out.println("返回第一个1所在的下标"+list.indexOf(1));
        System.out.println("返回最后一个1所在的下标："+list.indexOf(1));
        System.out.println("================");
        System.out.println("list中的元素："+list);
        System.out.println("截取从下标2到下标5为止的元素(注意区间是前闭后开)："+list.subList(2,5));//前闭后开
    }

3.2 LinkedList的遍历

for循环遍历：

 public static void main(String[] args) {
        LinkedList<Integer>list=new LinkedList<>();
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        list.add(5);
        for(int i=0;i<list.size();i++){
            System.out.print(list.get(i)+" ");
        }
    }

foreach(增强for循环遍历)：

    public static void main(String[] args) {
        LinkedList<Integer>list=new LinkedList<>();
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        list.add(5);
        for(Integer count:list){
            System.out.print(count+" ");
        }
    }
}

迭代器遍历：

    public static void main(String[] args) {
        LinkedList<Integer>list=new LinkedList<>();
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        list.add(5);
        //迭代器正向遍历
        ListIterator<Integer> ret=list.listIterator();
        while(ret.hasNext()){
            System.out.print(ret.next()+" ");
        }
        //迭代器反向遍历
        ListIterator<Integer> set=list.listIterator(list.size());
        while(set.hasPrevious()){
            System.out.print(set.previous()+" ");
        }
    }
}

3.3 LinkedList的优缺点

（1）LinkedList的优点：

动态大小：链表的大小可以灵活的增加或者减小，在插入或者删除元素的时候，不需要像数组那样移动大量元素；
高效的插入和删除：在链表中间插入或者删除一个节点，只需要修改相邻节点的指针即可；时间复杂度为O(1)；

（2） LinkedList的缺点：

随机访问效率低：当访问链表中第n个元素时，需要从链表头结点开始遍历每个节点，不像数组可以直接通过索引进行访问；
额外的内存开销：每个节点除了存储数据，还要存储指向下一个节点（在单链表中）或前后节点（在双链表中）的指针，这会占用额外的内存空间；
遍历相对复杂：因为节点在内存中不是连续存储的，所以遍历操作比数组复杂，并且缓存性能不如数组好;

四. ArrayList和LinkedList的区别

不同点	ArrayList	LinkedList
在存储空间上	逻辑和物理上都是连续的	逻辑上连续，但是物理上不一定连续
随机访问	时间复杂度为O(1)	时间复杂度为O(n)
头插	需要往后搬运元素，时间复杂度为	只需要修改引用指向，时间复杂度为O(1)
插入	空间不够需要扩容	没有扩容的概念
应用场景	元素高效存储和频繁访问	在任意位置插入和频繁删除元素