链表和LinkedList

发布时间：2022-08-18 18:26

目录

1.链表

1.1 链表概念和结构

1.2 链表实现

1.3 力扣-牛客上的一些链表面试题

2.LinkedList

2.1 LinkedList的使用

2.1.1 LinkedList结构

2.1.2 LinkedList实现的List接口

2.1.3 LinkedList的使用 

2.1.4 LinkedList 的遍历 

2.2 LinkedList模拟实现

3. ArrayList和LinkedList的区别

1.链表

1.1 链表概念和结构

链表是一种在物理存储结构上非连续的存储结构，

数据元素的逻辑顺序是通过链表中引用链接的顺序实现的

链表和LinkedList_第1张图片

 注意：（1）链式存储结构在逻辑上是连续的，在物理上不一定连续

            （2）结点从堆中申请

说明，链表结构有8种

链表和LinkedList_第2张图片

常用有两种

（1）单向 不带头 非循环：这个的特点是结构简单，所以实际中用作其他数据结构的子结构

（2）双向 无头 ：在java集合框架中LinkedList底层就是无头双向循环链表实现的 

1.2 链表实现

下面来写一个无头单向非循环链表的实现

先根据单链表结点写一个节点类

    static class Node{
        public int val;
        public Node next;
        public Node(int val) {
            this.val = val;
        }
    }
    public Node head;

（1）打印单链表display()

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

（2）查找是否包含关键字key是否在单链表当中contains()

链表和LinkedList_第3张图片

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

（3）求链表长度size()

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

（4）头插法addFirst()

链表和LinkedList_第4张图片

    public void addFirst(int data) {
        Node node = new Node(data);
        node.next = head;
        head = node;
    }

 （5）尾插法addLast()

链表和LinkedList_第5张图片

    public void addLast(int data) {
        Node node = new Node(data);
        if (head == null) {
            head = node;
        }else {
            Node cur = head;
            while (cur.next != null) {
                cur = cur.next;
            }
            cur.next = node;
        }
    }

（6）任意位置插入，第一个数据节点为0号下标addIndex()

链表和LinkedList_第6张图片

 先写一个checkIndex()来判断index合不合法

    private void checkIndex(int index) {
        if (index < 0 || index > size()) {
            throw new IndexNotLegalException("index位置不合法");
        }
    }

如果不合法写一个异常

public class IndexNotLegalException extends RuntimeException{
    public IndexNotLegalException() {

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

然后让cur走到index前一个节点findIndexSubOfOne()

    private Node findIndexSubOfOne(int index) {
        Node cur = head;
        while(index-1 != 0) {
            cur = cur.next;
            index--;
        }
        return cur;
    }

下面写index()

 public void addIndex(int index, int data) {
        checkIndex(index);
        if (index == 0) {//头插法
            addFirst(data);
            return;
        }
        if (index == size()) {//尾插法
            addLast(data);
            return;
        }
        Node node = new Node(data);
        Node cur = findIndexSubOfOne(index);
        node.next = cur.next;
        cur.next = node;
    }

（7）删除第一次出现关键字key的结点remove()

链表和LinkedList_第7张图片

  先找到所要删除结点的前驱searchPrevOfKey()

    private Node searchPrevOfKey(int key) {
        Node cur = this.head;
        while(cur.next != null) {
            if (cur.next.val == key) {
                return cur;
            }
            cur = cur.next;
        }
        return null;
    }

下面写remove()

    public void remove(int key) {
        //如果删除头结点
        if (head.val == key) {
            head = head.next;
            return;
        }
        Node cur = searchPrevOfKey(key);
        if (cur == null) return;
        Node del = cur.next;
        cur.next = del.next;
    }

（8）删除所有值为key的结点removeAllKey()

链表和LinkedList_第8张图片

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

（9）清空链表clear()

    public void clear() {
        this.head = null;
    }

1.3 力扣-牛客上的一些链表面试题

这个是我写的一篇链表的题，感兴趣的可以看一下

http://t.csdn.cn/B2BG2

 

2.LinkedList

2.1 LinkedList的使用

2.1.1 LinkedList结构

LinkedList底层是双向链表的结构，不是单链表

双向链表的节点组成 

链表和LinkedList_第9张图片

 双向链表实现图示

链表和LinkedList_第10张图片

特点：

（1）last记录保存最后一个节点的地址，如果要进行尾插法时，直接last.next就可以了 

（2）双向链表的遍历是双向的

 

2.1.2 LinkedList实现的List接口

链表和LinkedList_第11张图片

 注意：

（1）LinkedList实现了List接口

（2）LinkedList的底层使用了双向链表

（3）LinkedList没有实现RandomAccess接口，所以LinkedList不支持随机访问

（4）LinkedList的任意位置插入和删除元素时效率比较高，时间复杂度为O(1)

2.1.3 LinkedList的使用 

LinkedList构造 （1）无参构造 （2）利用其他集合容器中元素构造List

    public static void main(String[] args) {
        List list = new LinkedList<>();
        
        List list1 = new ArrayList<>();
        list1.add("xawl");
        list1.add("xxgcxy");
        list1.add("rjgc");
        List list2 = new LinkedList<>(list1);
    }

2.1.4 LinkedList 的遍历 

（1）下标+for循环 （2）for-each（3）使用迭代器正向遍历（4）使用反向迭代器反向遍历

 public static void main(String[] args) {
        LinkedList list = new LinkedList<>();
        list.add(12);
        list.add(25);
        list.add(45);
        list.add(67);
        System.out.println("=====1.for+下标=======");
        for (int i = 0; i < list.size(); i++) {
            System.out.print(list.get(i) + " ");
        }
        System.out.println();
        System.out.println("======2.for-each======");
        for (int x : list) {
            System.out.print(x + " ");
        }
        System.out.println();
        System.out.println("=======3.迭代器-正向=====");
        ListIterator it = list.listIterator();
        while(it.hasNext()) {
            System.out.print(it.next() + " ");
        }
        System.out.println();
        System.out.println("=====4.反向迭代器-反向=====");
        ListIterator it2 = list.listIterator(list.size());
        while (it2.hasPrevious()) {
            System.out.print(it2.previous() + " ");
        }
    }

2.2 LinkedList模拟实现

先根据双向链表节点定义一个节点类

    static class ListNode {
        public int val;
        public ListNode prev;
        public ListNode next;
        public ListNode(int val) {
            this.val = val;
        }
        public ListNode head;

（1）链表打印disPlay()

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

（2）查找包含关键字key是否在链表当中contains()

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

（3）求链表长度size()

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

（4）头插法addFirst()

链表和LinkedList_第12张图片

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

（5）尾插法addLast() 

链表和LinkedList_第13张图片

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

 （6）任意位置插入，第一个数据节点为0号下标addIndex()

先获得index下标节点findInde()

        private ListNode findIndex(int index) {
            ListNode cur = head;
            while(index != 0) {
                cur = cur.next;
                index--;
            }
            return cur;
        }

链表和LinkedList_第14张图片

        public void addIndex(int index, int data) {
            //1.检查index合法性
            if (index < 0 || index > size()) {
                throw new IndexNotlegalException("双向链表index不合法");
            }
            if (index == 0) {
                addFirst(data);
                return;
            }
            if (index ==size()) {
                addLast(data);
                return;
            }
            ListNode node = new ListNode(data);
            //2.获取当前的index位置的结点地址
            ListNode cur = findIndex(index);
            node.next = cur;
            cur.prev.next = node;
            node.prev = cur.prev;
            cur.prev = node;
        }

（7）删除第一次出现关键字为key的结点remove()

      public void remove(int key) {
            ListNode cur = head;
            while (cur != null) {
                //找到了删除
                if (cur.val == key) {
                    if (cur == head) {
                        //1.删除头部
                        head = head.next;
                        if (head != null) {
                            //防止只有一个节点
                            head.prev = null;
                        }
                    } else {
                        cur.prev.next = cur.next;
                        if (cur.next != null) {
                            //2.删除中间结点
                            cur.next.prev = cur.prev;
                        } else {
                            //3，删除尾部
                            last = cur.prev;
                        }
                    }
                    return;
                }
                cur = cur.next;
            }
        }

（8）删除所有值为key的结点removeAllkey()

前（7）中删除一个值为key的结点，然后就return返回了

这里删除所有的key，那就不要return了直接全部找出来删除

   public void removeAllKey(int key) {
            ListNode cur = head;
            while (cur != null) {
                //找到了删除
                if (cur.val == key) {
                    if (cur == head) {
                        //1.删除头部
                        head = head.next;
                        if (head != null) {
                            //防止只有一个节点
                            head.prev = null;
                        }
                    } else {
                        cur.prev.next = cur.next;
                        if (cur.next != null) {
                            //2.删除中间结点
                            cur.next.prev = cur.prev;
                        } else {
                            //3，删除尾部
                            last = cur.prev;
                        }
                    }
                }
                cur = cur.next;
            }
        }

（9）清除所有结点clear()

        public void clear() {
            head = null;
            last = null;
        }

3. ArrayList和LinkedList的区别

最直观的我们从二者的 增删查改 的时间复杂度进行比较

链表和LinkedList_第15张图片

下来简单说一下

相同点：

（1）ArrayList和LinkedList都实现了这三个接口 java.util.List（支持泛型，都能用来存放各种类数据类型的对象）、Cloneable（能支持克隆）、java.io.Serializable（能够支持序列化）

（2）ArrayList和LinkedList都不是线程安全的，如果要在多线程情况下调用它们，可以使用Collertions类中的静态方法SynchronizedList（），或者用Vector

不同点

ArrayList LinkedLIst
实现方式 动态数组 双向链表
存储空间 一定连续 逻辑上连续，物理上不一定
随机访问 支持高效的随机访问 不支持
应用场景 高效存储+频繁访问 任意位置频繁插入删除
内存占用 存储数据+结点指向后 消耗小 存储数据+结点指向前+指向后 消耗大
插入 空间不够时需要扩容 没有容量的概念，只需拉链条
非线程安全 基于动态数组实现的非线程安全的集合 基于链表实现的非线程安全的集合

 

相关推荐

超详细一次搞定Eslint + Prettier + husky + lint-staged前端代码工作流

python中撤销_python中撤销

1.Spark大型电商项目-电商用户行为分析简介

1252. 奇数值单元格的数目 : 简单计数模拟题

教育平台的线上课程智能推荐策略-Python

Vue组件间传值的几种方式

Java&C++题解与拓展——leetcode829.连续整数求和【么的新知识】

直面秋招！高级Java开发面试解答，写的太详细了

react antd上拉加载与下拉刷新与虚拟列表使用

Flutter 开发小结 | Tips

教你一招解决vue页面自适应布局

注意防范高温！通过splash爬取高温预警信息

值得一看的智能运维AIOps关键核心技术概览！

AWVS介绍

npm——安装、卸载与更新

小项目：生成随机的测验试卷文件_python

4.Vue3计算属性computed实现原理

【服务器数据恢复】某品牌ProLiant服务器raid瘫痪数据库文件损坏的数据恢复

如何保障移动终端安全？一文详解源自支付宝的全链路安全防护建设

idea2021使用maven创建web项目

ItVuer - 免责声明 - 关于我们 - 联系我们

本网站信息来源于互联网，如有侵权请联系：561261067@qq.com

桂ICP备16001015号