当前位置： 首页 > article >正文

数据结构（Java）——链表

article 2025/3/2 4:14:02

1.概念及结构

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

2.分类

链表的结构非常多样，以下情况组合起来就有 8 种链表结构：
（1）单向或者双向
（2）带头或者不带头
（3）循环或者不循环
    即单向带头循环链表、单向不带头循环链表、单向带头不循环链表、单向不带头不循环链表、双向带头循环链表、双向不带头循环链表、双向带头不循环链表和双向不带头不循环链表。
虽然有这么多的链表的结构，但是我们本篇主要讲两种 :
  • 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。
  • 无头双向非循环链表：在Java的集合框架库中LinkedList底层实现就是无头双向非循环链表。

3. 代码实现

3.1 无头单向非循环链表

3.1.1 节点结构

static class ListNode {
        public int val;
        public ListNode next;

        public ListNode(int val) {
            this.val = val;
        }
    }

3.1.2 方法接口

public interface ISingleLinkedList {
//头插法
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的节点
public void removeAllKey(int key)
//得到单链表的长度
public int size()
//清空链表
public void clear() 
//打印链表
public void display()
}

3.1.3 功能实现

public class MySingleLinkedList implements IMySingleLinkedList {
     @Override
    public void addFirst(int data) {
        ListNode node = new ListNode(data);
        node.next = head;
        head = node;
    }
    @Override
    public void addLast(int data) {
        ListNode node = new ListNode(data);
        if(head == null) {
            head = node;
            return;
        }
        ListNode cur = head;
        while (cur.next != null) {
            cur = cur.next;
        }
        cur.next = node;
    }
     @Override
    public void addIndex(int index,int data) {
        //1.判断index的合法性
        try {
            checkIndex(index);
        }catch (IndexNotLegalException e) {
            e.printStackTrace();
        }
        //2.index == 0  || index == size()
        if(index == 0) {
            addFirst(data);
            return;
        }
        if(index == size()) {
            addLast(data);
            return;
        }
        //3. 找到index的前一个位置
        ListNode cur = findIndexSubOne(index);
        //4. 进行连接
        ListNode node = new ListNode(val);
        node.next = cur.next;
        cur.next = node;
    }
    private ListNode findIndexSubOne(int index) {
        int count = 0;
        ListNode cur = head;
        while (count != index-1) {
            cur = cur.next;
            count++;
        }
        return cur;
    }

    private void checkIndex(int index) throws IndexNotLegalException{
        if(index < 0 || index > size()) {
            throw new IndexNotLegalException("index不合法");
        }
    }
    @Override
    public boolean contains(int key) {
        ListNode cur = head;
        while (cur != null) {
            if(cur.val == key) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }
   @Override
    public void remove(int key) {
        if(head == null) {
            return;
        }
        if(head.val == key) {
            head = head.next;
            return;
        }
        ListNode cur = head;
        while (cur.next != null) {
            if(cur.next.val == key) {
                ListNode del = cur.next;
                cur.next = del.next;
                return;
            }
            cur = cur.next;
        }
    }
    @Override
    public void removeAllKey(int key) {
        //1. 判空
        if(this.head == null) {
            return;
        }
        //2. 定义prev 和 cur
        ListNode prev = head;
        ListNode cur = head.next;
        //3.开始判断并且删除
        while(cur != null) {
            if(cur.val == key) {
                prev.next = cur.next;
                
            }else {
                prev = cur;
            }
            cur = cur.next;
        }
        //4.处理头节点
        if(head.val == key) {
            head = head.next;
        }
    }
   @Override
    public int size(){
        int count = 0;
        ListNode cur = head;
        while (cur != null) {
            count++;
            cur = cur.next;
        }
        return count;
    }
    @Override
    public void clear() {
        //head = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode curN = cur.next;
            //cur.val = null;
            cur.next = null;
            cur = curN;
        }
        head = null;
    }
   @Override
   public void display() {
        ListNode cur = head;
        while (cur != null) {
            System.out.print(cur.val+" ");
            cur = cur.next;
        }
        System.out.println();
    }
}

//自定义异常类
public class IndexNotLegalException extends RuntimeException{
    public IndexNotLegalException() {

    }

    public IndexNotLegalException(String msg) {
        super(msg);
    }
}

3.2 无头双向非循环链表

3.2.1 节点结构

class ListNode {
        public int val;
        public ListNode prev;//前驱
        public ListNode next;//后继

        public ListNode(int val) {
            this.val = val;
        }
    }

3.2.2 方法接口

public interface IMyLinkedList {
//头插法
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的节点
public void removeAllKey(int key);
//得到单链表的长度
public int size();
public void display();
public void clear();
}

3.2.3 功能实现

public class MyLinkedList implements IMyLinkedList {
    public ListNode head;//标志头节点
    public ListNode last;//标志尾结点
    //头插法
    @Override
    public void addFirst(int data){
        ListNode node = new ListNode(data);
        if(head == null) {
            //是不是第一次插入节点
            head = last = node;
        }else {
            node.next = head;
            head.prev = node;
            head = node;
        }
    }

    //尾插法
    @Override
    public void addLast(int data){
        ListNode node = new ListNode(data);
        if(head == null) {
            //是不是第一次插入节点
            head = last = node;
        }else {
           last.next = node;
           node.prev = last;
           last = last.next;
        }
    }
    //任意位置插入,第一个数据节点为0号下标
    @Override
    public void addIndex(int index,int data){
        try {
            checkIndex(index);
        }catch (IndexNotLegalException e) {
            e.printStackTrace();
        }
        if(index == 0) {
            addFirst(data);
            return;
        }
        if(index == size()) {
            addLast(data);
            return;
        }
        //1. 找到index位置
        ListNode cur = findIndex(index);
        ListNode node = new ListNode(data);
        //2、开始绑定节点
        node.next = cur;
        cur.prev.next = node;
        node.prev = cur.prev;
        cur.prev = node;
    }

    private ListNode findIndex(int index) {
        ListNode cur = head;
        while (index != 0) {
            cur = cur.next;
            index--;
        }
        return cur;
    }
    private void checkIndex(int index) {
        if(index < 0 || index > size()) {
            throw new IndexNotLegalException("双向链表插入index位置不合法: "+index);
        }
    }
    //查找是否包含关键字key是否在单链表当中
    @Override
    public boolean contains(int key){
        ListNode cur = head;
        while (cur != null) {
           if(cur.val == key) {
               return true;
           }
            cur = cur.next;
        }
        return false;
    }
    //删除第一次出现关键字为key的节点
    @Override
    public void remove(int key){
        ListNode cur = head;
        while (cur != null) {
            if(cur.val == key) {
                //开始删除 处理头节点
                if(cur == head) {
                    head = head.next;
                    if(head != null) {
                        head.prev = null;
                    }else {
                        last = null;
                    }
                }else {
                    cur.prev.next = cur.next;
                    if(cur.next == null) {
                        //处理尾巴节点
                        last = last.prev;
                    }else {
                        cur.next.prev = cur.prev;
                    }
                }
                return;//删完一个就走
            }
            cur = cur.next;
        }
    }
    //删除所有值为key的节点
    @Override
    public void removeAllKey(int key){
        ListNode cur = head;
        while (cur != null) {
            if(cur.val == key) {
                //开始删除 处理头节点
                if(cur == head) {
                    head = head.next;
                    if(head != null) {
                        head.prev = null;
                    }else {
                        //head == null 证明只有1个节点
                        last = null;
                    }
                }else {
                    cur.prev.next = cur.next;
                    if(cur.next == null) {
                        //处理尾巴节点
                        last = last.prev;
                    }else {
                        cur.next.prev = cur.prev;
                    }
                }
            }
            cur = cur.next;
        }
    }
    //得到双向链表的长度
    @Override
    public int size(){
        int count = 0;
        ListNode cur = head;
        while (cur != null) {
            count++;
            cur = cur.next;
        }
        return count;
    }
    @Override
    public void display(){
        ListNode cur = head;
        while (cur != null) {
            System.out.print(cur.val+" ");
            cur = cur.next;
        }
        System.out.println();
    }
    @Override
    public void clear(){
        ListNode cur = head;
        while (cur != null) {
            ListNode curN = cur.next;
            //cur.val = null;
            cur.prev = null;
            cur.next = null;
            cur = curN;
        }
        head = last = null;
    }
}
//自定义异常类
public class IndexNotLegalException extends RuntimeException{
    public IndexNotLegalException() {

    }

    public IndexNotLegalException(String msg) {
        super(msg);
    }
}

4.LinkedList

4.1 概念

   LinkedList 的底层是双向链表结构 ( 链表后面介绍 ) ，由于链表没有将元素存储在连续的空间中，元素存储在单独的节点中，然后通过引用将节点连接起来了，因此在在任意位置插入或者删除元素时，不需要搬移元素，效率比较高。
注意：
1. LinkedList 实现了 List 接口
2. LinkedList 的底层使用了双向链表
3. LinkedList 没有实现 RandomAccess 接口，因此 LinkedList 不支持随机访问
4. LinkedList 的任意位置插入和删除元素时效率比较高，时间复杂度为 O(1)
5. LinkedList 比较适合任意位置插入的场景

4.2 使用

4.2.1 构造方法

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

代码示例：

public static void main(String[] args) {
      // 构造一个空的LinkedList
        List<String> list1 = new LinkedList<>();
        list1.add("sas");
        list1.add("asd");
        list1.add("Jsd");
        System.out.print("list1: ");
        for(int i = 0; i < list1.size();i++){
            System.out.print(list1.get(i)+" ");
        }
        System.out.println();
        System.out.print("list2: ");
        List<String> list2 = new LinkedList<>(list1);
        for(int i = 0; i < list2.size();i++){
            System.out.print(list2.get(i)+" ");
        }
    }

运行结果如下：

4.2.2 其他常用方法

方法解释
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 lastIndexOf(Object o)
返回最后一个 o 的下标
List<E> subList(int fromIndex, int toIndex)截取部分list

代码示例：

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): 获取指定位置元素
    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());
}

运行结果如下：

4.3 遍历

我们之前常用的遍历方式有for循环、foreach循环和while循环等来进行遍历，LinkedList除了使用这些外， 还可以使用迭代器进行遍历。

代码示例：

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();
}

运行结果如下：

5.ArrayList和LinkedList的区别

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

本文是作者学习后的总结，如果有什么不恰当的地方，欢迎大佬指正！！！


http://www.kler.cn/a/459324.html

相关文章：

  • gala-gopher
  • 在Windows10下安装Docker WSL 2 桌面版
  • 基于python大数据的图书销售系统
  • Flutter：打包apk，详细图文介绍
  • QT-----------GUI程序设计基础
  • 基于Arduino的音乐喷泉设计（论文+源码）
  • echarts：5、树状图
  • C++类与对象（三）-- 再谈构造函数(细嗦初始化列表)、static成员
  • 多进程并发执行，多线程并发服务器
  • Redis中的数据类型
  • 数据结构与算法学习笔记----约数
  • 群落生态学研究进展▌Hmsc包对于群落生态学假说的解读、Hmsc包开展单物种和多物种分析的技术细节及Hmsc包的实际应用
  • CPO-CNN-GRU-Attention、CNN-GRU-Attention、CPO-CNN-GRU、CNN-GRU四模型多变量时序预测对比
  • 基于Golang的博客系统的设计与实现
  • 【最新】17个一站式数据集成平台案例PPT下载（Apache SeaTunnel ）
  • 简易CPU设计入门：本系统中的通用寄存器（三）
  • 实景三维点云处理专业软件ArcGIS根据DSM生成地表点云集
  • IS-2T2R存储器：AWS精度下降问题的解决方案
  • js单例模式
  • Java网络编程之UDP协议介绍及示例代码