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

Java数据结构链表(LinkedList详解)

article 2024/11/19 19:37:19

前言：

        Java数据结构链表部分和顺序表有所相似：

        首先都扩展了接口List，List里面的方法都会在LinkedList中重写。

        其次都可以实现数据的增删查改等基础功能。

        当然ArrayList相较于LinkedList有一定的缺陷，比如果在中间位置插入数据，在中间位置删除数据都比较麻烦，需要移动大量数据！LinkedList可以有效地解决移动数据的难题。

        当然LinkedList也有自我的缺陷(在C语言阶段已经详细研究，大家可以翻看之前的博客)，接下来就一起用Java的目光探究LinkedList。

自我实现MyLinkedList：

        由于之前在C预研阶段已经实现过链表，可以翻看之前的内容仔细了解，接下来直接上代码：

无头单向不循环链表：

Ilist接口：

public interface IList {
    //头插法
    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();
}

MyLinkedList类：

    public void addIndex(int index, int data) throws IndexExpection{
        if(index < 0||index>size()) {
            throw new IndexExpection("非法访问");
        }
        ListNode cur = head;
        if(head == null) {
            head = new ListNode(data);
            return ;
        }
        if(index == 0) {
            addFirst(data);
            return ;
        }
        if(index == size()) {
            addLast(data);
            return ;
        }
        while(index-1 != 0) {
            index--;
            cur = cur.next;
        }
        ListNode node = new ListNode(data);
        node.next = cur.next;
        cur.next = node;
    }

    @Override
    public boolean contains(int key) {
        ListNode cur = head;
        while(cur != null) {
            if(cur.val == key) {
                return true;
            }
        }
        return false;
    }

    @Override
    public void remove(int key) {
        if(head == null) {
            return ;
        }
    ListNode cur = head;
    if(cur.val == key) {
        head = head.next;
    }
    while(cur.next != null) {
        if(cur.next.val == key) {
            cur = cur.next.next;
            return ;
        }
    }
    if(cur.val == key) {
        cur = cur.next;
    }
    }

    @Override
    public void removeAllKey(int key) {
        if(head == null) {
            return ;
        }
        ListNode cur = head;
        if(cur.val == key) {
            head = head.next;
        }
        while(cur.next != null) {
            if(cur.next.val == key) {
                cur = cur.next.next;
            }
        }
        if(cur.val == key) {
            cur = cur.next;
        }
    }

    @Override
    public int size() {
        int num = 0;
        ListNode cur = head;
        while(cur != null) {
            num++;
            cur = cur.next;
        }
        return num;
    }

    @Override
    public void clear() {
    head = null;
    }

    @Override
    public void display() {
    ListNode cur = head;
    while(cur != null) {
        System.out.print(cur.val);
        cur = cur.next;
    }
        System.out.println();
    }
}

但是这里与Java中给的LinkedList有所不同，不在什么地方？

Java中的LinkedList是一个无头双向不循环链表，所以此时我们还需要进行一个改进。

无头双向不循环链表：

直接上代码：

package LinkedDemo;

/**
 * Created with IntelliJ IDEA.
 * Description:无头双向不循环
 * User: 29980
 * Date: 2024-09-29
 * Time: 12:21
 */
public class MyLinkedList implements IList{
    static class ListNode {
        private int val;
        private ListNode prev;
        private ListNode next;
        public ListNode(int data){
            this.val = data;
        }
    }
    private ListNode head;
    private 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) {
            last = head = node;
        }
        //ListNode cur = head;
//        while(cur.next != null) {
//            cur = cur.next;
//        }
//        cur.next = node;
//        node.prev = cur;
       node.prev = last.prev;
        last = node;
    }

    @Override
    public void addIndex(int index, int data) {
        ListNode node = new ListNode(data);
        if(head == null) {
            head = node;
            return ;
        }
        if(index == 0) {
            addFirst(data);
            return ;
        }
        if(index == size()) {
            addLast(data);
            return ;
        }
        ListNode cur = head;
        while(index != 0) {
            cur = cur.next;
            index--;
        }
        node.next = cur;
        node.prev = cur.prev;
        cur.prev = node;
    }

    @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) {
        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.next.prev = cur.prev;
                    if(cur.next != null) {
                        cur.prev = cur.next;
                    }else {
                        last = last.prev;
                    }
                }
                return;
            }
            cur = cur.next;
        }
    }

    @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  {
                        last = null;
                    }
                }else {
                    cur.next.prev = cur.prev;
                    if(cur.next != null) {
                        cur.prev = cur.next;
                    }else {
                        last = last.prev;
                    }
                }
            }
            cur = cur.next;
        }
    }

    @Override
    public int size() {
        ListNode cur = head;
        int num = 0;
        while(cur != null) {
            num++;
            cur = cur.next;
        }
        return num;
    }

    @Override
    public void display() {
        ListNode cur = head;
    for(int i = 0;i<size();i++) {
        System.out.print(cur.val+" ");
        cur = cur.next;
    }
    }

    @Override
       public void clear() {
    ListNode cur = head;
    while(cur != null) {
        ListNode tmp = cur.next;
        cur.next = null;
        cur.prev = null;
        cur = tmp;
    }
    head = last = null;
    }
}

LinkedList的使用：

        当然我们的核心还是在如何使用Java给定的LinkedList，首先我们再根据一下图片分析一次：

       

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

LinkedList的构造方法：

LinkedList的构造方法有以下两种：

一个是无参构造，另一个大家应该很少见是有参数，这个参数是Collection<?extends E> c ,是什么意思呢？

第一：两个类必须都是实现了Collection接口的。

第二：两个类<>里面的参数必须满足继承关系。

例如：
 

 public static void main(String[] args) {
        List<Integer> list = new LinkedList<>();
        List<Integer> list1 = new ArrayList<>();
        list1.add(1);
        list1.add(2);
        list1.add(3);
        list1.add(4);
        list1.add(5);
        List<Object> list2 = new LinkedList<>(list1);
        System.out.println(list2);
    }

LinkedList遍历的方式：

        遍历LinkedLisst的方式有三种：

 方式一：foreach打印

//第一种foreach遍历
        for (int x:list) {
            System.out.print(x+" ");
        }
        System.out.println();

方式二：利用迭代器正向打印

       ListIterator<Integer> it = list.listIterator();
        while(it.hasNext()) {
            System.out.print(it.next()+" ");
        }
        System.out.println();

方式三：利用反向迭代器打印：

        ListIterator<Integer> it1 = list.listIterator(list.size());
        while(it1.hasPrevious()) {
            System.out.print(it1.previous()+" ");
        }

打印结果如下：


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

相关文章：

  • 京东 2025届秋招 自然语言处理
  • RabbitMQ的基本概念和入门
  • 理解 Python 中的 __getitem__ 方法：在自定义类中启用索引和切片操作
  • Vue实现响应式导航菜单：桌面端导航栏 + 移动端抽屉式菜单
  • 脑机接口、嵌入式 AI 、工业级 MR、空间视频和下一代 XR 浏览器丨RTE2024 空间计算和新硬件专场回顾
  • 深入理解 SQL_MODE 之 ANSI_QUOTES
  • Vue3 Typescript 前端页面5min后无操作自动退出至登录页面
  • Windows上面搭建Flutter Android运行环境
  • cmd下的管理员权限闪退 原理分析
  • 【Rockchip系列】官方函数：drm_buf_alloc
  • 【Kotlin基于selenium实现自动化测试】初识selenium以及搭建项目基本骨架(1)
  • 华为OD机试 - 超级玛丽通过吊桥的走法 - 动态规划（Python/JS/C/C++ 2024 E卷 200分）
  • 数据结构——计数、桶、基数排序
  • 深入探索 PyTorch 在机器学习中的应用
  • 观测云对接 SkyWalking 最佳实践
  • Springboot中yml文件不生效原因分析及解决
  • 【C++篇】启航——初识C++（下篇）
  • 滚雪球学Oracle[7.1讲]：Oracle云数据库
  • 如何从 Windows 11/10/8.1/8/7 中恢复已删除的视频
  • 前端导出页面PDF
  • rust的nutyp验证和validator验证数据的方法
  • MySQL | group by 用法
  • 牛客周赛 Round 62
  • 828华为云征文｜部署个人文档管理系统 Docspell
  • Kali Linux安全工具
  • 实战OpenCV之形态学操作