Java：数据结构-LinkedList和链表（2）

🕗 发布于 2024-10-17 11:12 java 数据结构 链表

一 LinkedList

LinkedList的方法的实现

1.头插法

public class MyLinkedList implements IList{
    static class ListNode{
        public int val;
        public ListNode next;
        public ListNode prev;

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

    }
    public ListNode head;
    public ListNode last;

    @Override
    public void addFirst(int data) {
        ListNode node=new ListNode(data);
        ListNode cur=head;
        if (head==null) {
            head = last = cur;
        } else{
            node.next=head;
            head.prev=node;
            head=node;
        }
    }
}

2.尾插法

public class MyLinkedList implements IList{
    static class ListNode{
        public int val;
        public ListNode next;
        public ListNode prev;

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

    }
    public ListNode head;
    public ListNode last;
    public void addLast(int data) {
        ListNode node=new ListNode(data);
        ListNode cur=head;
        if (head==null) {
            head = last = cur;
        } else{
            node.prev=last;
            last.next=node;
            last=node;
        }
    }
}

3.任意位置插入,第一个数据节点为0号下标

public class MyLinkedList implements IList{
    static class ListNode{
        public int val;
        public ListNode next;
        public ListNode prev;

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

    }
public void addIndex(int index, int data) {
        ListNode node=new ListNode(data);
        int len=size();
        if(index<0 || index>len){
            return;
        }
        if(index==0){
            addFirst(data);
        }
        if(index==len){
            addLast(data);
        }
        ListNode cur=head;
        node.next=cur;
        node.prev=cur.prev;
        cur.prev.next=node;
        cur.prev=node;
    }

4.查找是否包含关键字key是否在链表当中

public class MyLinkedList implements IList{
    static class ListNode{
        public int val;
        public ListNode next;
        public ListNode prev;

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

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

5.得到链表的长度

public class MyLinkedList implements IList{
    static class ListNode{
        public int val;
        public ListNode next;
        public ListNode prev;

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

    }
    public ListNode head;
    public ListNode last;

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

6.打印链表

public class MyLinkedList implements IList{
    static class ListNode{
        public int val;
        public ListNode next;
        public ListNode prev;

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

    }
    public ListNode head;
    public ListNode last;

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

7.删除第一次出现关键字为key的节点

删除中间部分

删除头

并且考虑只有一项的情况下

删除尾

public class MyLinkedList implements IList{
    static class ListNode{
        public int val;
        public ListNode next;
        public ListNode prev;

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

    }
    public ListNode head;
    public ListNode last;


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

    }
}

8.删除所有值为key的节点

跟remove基本一样，删去return就行了，将整个链表检查一遍，删去全部的key

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

                }else {
                    if(cur.next==null){
                        cur.prev.next=null;
                        last=last.prev;
                    }else {
                        cur.prev.next=cur.next;
                        cur.next.prev=cur.prev;
                    }
                }
            }
            cur=cur.next;
        }
    }

9.清空链表

public class MyLinkedList implements IList{
    static class ListNode{
        public int val;
        public ListNode next;
        public ListNode prev;

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

    }
    public ListNode head;
    public ListNode last;

public void clear() {
        ListNode cur=head;
        while (cur!=null){
            ListNode curN=cur.next;
            cur.prev=null;
            cur.next=null;
            cur=curN;
        }
    }
}

LinkedList方法的使用

public class Test {
    public static void main(String[] args) {
        LinkedList<Integer> linkedList=new LinkedList<>();
        List<Integer> list=new LinkedList();
        linkedList.add(1);
        linkedList.addFirst(3);
        linkedList.addLast(6);
        ArrayList<Integer> list1=new ArrayList<>();
        list1.add(1);
        list1.add(2);
        list1.add(3);
        list1.add(4);
        linkedList.addAll(list1);
        System.out.println(linkedList);
        linkedList.remove(2);
        linkedList.get(3);
        linkedList.set(2,6);
        linkedList.contains(5);
        linkedList.size();
        linkedList.clear();
    }

LinkedList的遍历

1.for循环遍历

public class Test {
    public static void main(String[] args) {
        LinkedList<Integer> linkedList=new LinkedList<>();
        linkedList.add(1);
        linkedList.addFirst(3);
        linkedList.addLast(6);
        for (int i = 0; i < linkedList.size(); i++) {
            System.out.println(linkedList.get(i)+" ");
        }
    }

2.foreach遍历

public class Test {
    public static void main(String[] args) {
        LinkedList<Integer> linkedList=new LinkedList<>();
        linkedList.add(1);
        linkedList.addFirst(3);
        linkedList.addLast(6);
for (Integer x:linkedList) {
            System.out.print(x+" ");
        }
    }
}

3.迭代器

Iterator

public class Test {
    public static void main(String[] args) {
        LinkedList<Integer> linkedList=new LinkedList<>();
        linkedList.add(1);
        linkedList.addFirst(3);
        linkedList.addLast(6);
        Iterator<Integer> iterator=linkedList.iterator();
        while (iterator.hasNext()){
            System.out.print(iterator.next());
        }

ListIterator

1.按顺序打印

public class Test {
    public static void main(String[] args) {
        LinkedList<Integer> linkedList=new LinkedList<>();
        linkedList.add(1);
        linkedList.addFirst(3);
        linkedList.addLast(6);
        ListIterator<Integer> it=linkedList.listIterator();
        while (it.hasNext()){
            System.out.println(it.next()+" ");
        }

2.逆序打印

public class Test {
    public static void main(String[] args) {
        LinkedList<Integer> linkedList=new LinkedList<>();
        linkedList.add(1);
        linkedList.addFirst(3);
        linkedList.addLast(6);
        ListIterator<Integer> it1=linkedList.listIterator();
        while (it1.hasPrevious()){
            System.out.println(it1.previous()+" ");
        }
}

注: ListIterator可以当作迭代器的原因是，它是Iterator的子类，专门用来打印List类的。

ArrayList和LinkedList的区别

当你进行查找时，我建议你选择ArrayList，因为LinkedList访问任意元素需要从头或尾遍历链表，时间复杂度为 O(n)，ArrayList可以通过索引直接访问任意元素，时间复杂度是 O(1)。

当我们经常使用插入等功能，可以使用LinkedList，如果在末尾插入或删除元素，效率较高（时间复杂度 O(1)），ArrayList需要移动大量元素，因此效率较低（时间复杂度 O(n)）。

希望能对大家有所帮助！！！！

原文地址：https://blog.csdn.net/blamep/article/details/142884134

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：Vulhub Bob: 1.0.1靶机详解
下一篇：1882B - Sets and Union

一次性入门三款分布式定时任务调度框架：Quartz、ElasticJob3.0、xxl-job
三款分布式任务调度框架，一篇文章全部入门
阅读更多2024-10-19
Python OpenCV精讲系列 - 目标检测与识别深入理解（二十）
Haar特征是一种简单的图像特征，用于检测局部图像结构的变化。它由一组简单的黑色和白色矩形组成，用于计算图像中不同区域之间的平均像素强度差异。HOG（Histogram of Oriented Gra
阅读更多2024-10-19
OpenMediaVault安装插件以及重置web控制台密码
需要安装好openmediavault-md插件。
阅读更多2024-10-19
快速了解kubernetes中的存储管理
Secret 对象类型用来保存敏感信息，例如密码、OAuth 令牌和 ssh key。- 敏感信息放在 secret 中比放在 Pod 的定义或者容器镜像中来说更加安全和灵活- Pod 可以用两种方式
阅读更多2024-10-19
代理 IP：促进在线教育资源普及与公平的新助力
当某个地区的网络拥堵时，学生可以通过代理 IP 选择其他网络较为畅通的线路，确保学习的顺畅进行。对于一些教育资源匮乏的地区，代理 IP 可以帮助学生访问其他地区的在线教育平台，获取更多的学习资料、课程
阅读更多2024-10-19
代码训练营 day38|LeetCode 62，LeetCode 63
今天主要学习了dp的一系列操作，今天难度不大，有点dp那味儿了加油，坚持打卡的第38天。
阅读更多2024-10-19
Dynamic 3D Gaussians: Tracking by Persistent Dynamic View Synthesis 阅读
Dynamic 3D Gaussians:Tracking by Persistent Dynamic View Synthesis 论文阅读
阅读更多2024-10-19
JS模块化及import、export
本文探讨了模块化编程的背景与目的，强调了通过降低代码重复、提高可读性和便于维护等优势来改善软件开发过程。文章还介绍了五大模块化原则，包括单一职责原则和依赖倒置原则，以确保代码的灵活性和可扩展性。此外，
阅读更多2024-10-19
css 如何根据子元素给他的父元素设置样式
'active' : 'unactive' }">子元素啊根据一个变量来加样式</div>其中能马上想到的就是：这个class的判断可以加在parent后面，但是如果不改变
阅读更多2024-10-19
前端学习---(2)CSS基础
关于文字样式的属性，都具有继承性。这些属性包括：color、 text-开头的、line-开头的、font-开头的。CSS 是用来指定文档如何展示给用户的一门语言——如网页的样式、布局、等等。css语
阅读更多2024-10-19