手撕Java集合——链表

这篇具有很好参考价值的文章主要介绍了手撕Java集合——链表。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

一、链表概念特性

链表是一种物理存储结构上非连续存储结构,数据元素的逻辑顺序是通过链表中的引用链接次序实现的 。
手撕Java集合——链表,Java数据结构,java,链表,数据结构,经验分享,学习,开发语言

特点:

  1. 上图每个数据块是一个结点,这些结点一般是从堆上申请来的。
  2. 链式结构在逻辑上是连续的,但物理上不一定连续。

链表结构由【单向/双向;循环/非循环;带头/不带头】几种形式进行组合,共有2×2×2=8种不同结构,不过我们常用的主要是 单向不带头非循环链表双向不带头非循环链表 。对于前者来说,结构简单,一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构,如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。对于后者,在Java的集合框架库中LinkedList底层实现就是无头双向非循环链表。

接下来我们就以不带头单向非循环链表和不带头双向循环链表进行展开,分别模拟实现它们的主要功能。

二、不带头单向非循环链表实现

首先给出功能接口(实现时元素类型为int):

//1.打印链表
public void display() {}

//2.递归逆序打印链表
public void displayReverse(SingleLinkedList.ListNode node) {}

//3.头插法
public void addFirst(int data) {}

//4.尾插法
public void addLast(int data) {}

//5.任意位置插入,第一个数据节点为0号下标
public boolean addIndex(int index, int data) {}

//6.查找是否包含关键字key是否在单链表当中
public boolean contains(int key) {}

//7.删除第一次出现关键字为key的节点
public void remove(int key) {}

//8.删除所有值为key的节点
public void removeAllKey(int key) {}

//9.得到单链表的长度
public int size() {}

//10.清空链表
public void clear() {}

🍑1、定义结点

这里是将结点看做单链表SingleLinkedList的一部分,所以将结点定义为链表类-SingleLinkedList的内部类。
注意: 这里的head结点并不表示链表带有单独头结点(不管链表是否为空,均含有一个头结点),而是用来表示该链表的第一个结点。

public class SingleLinkedList {
	static class ListNode {
    	public int val;//存储的数据
    	public ListNode next;//存储下一个节点的地址
		//构造方法
    	public ListNode(int val) {
        	this.val = val;
    	}
	}
	
	public ListNode head;//表示当前链表的头结点
	
	//一些功能接口……
}
	

🍑2、打印链表

思路:从头结点开始向后变历链表,直到结点为空,打印完毕。

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

🍑3、使用递归逆序打印链表

思路:利用递归思想,先递后归,实现倒序打印链表。

    public void displayRecu(ListNode node) {
        if (node == null) {
            return;
        }
        if (node.next == null) {
            System.out.print(node.val+" ");
            return;
        }
        displayRecu(node.next);
        System.out.print(node.val+" ");
    }

🍑4、头插

手撕Java集合——链表,Java数据结构,java,链表,数据结构,经验分享,学习,开发语言

    //头插法【比较简单,整体也没有特殊情况,head=null也没问题!】
    public void addFirst(int data) {
        ListNode newNode = new ListNode(data);
        newNode.next = head;
        head = newNode;
    }

🍑5、尾插

手撕Java集合——链表,Java数据结构,java,链表,数据结构,经验分享,学习,开发语言

    //尾插法【需要考虑头结点为null的情况】
    public void addLast(int data) {
        ListNode newNode = new ListNode(data);
        ListNode cur = head;
        //如果头结点为空,直接赋值
        if (head == null) {
            head = newNode;
            return;
        }
        //找到尾结点
        while (cur.next != null) {
            cur = cur.next;
        }
        cur.next = newNode;

    }

🍑6、指定位置插入

手撕Java集合——链表,Java数据结构,java,链表,数据结构,经验分享,学习,开发语言

	//下标合法性检测
    private void checkIndex(int index) {
    	//这里的size()是自定义函数(后面讲解)
        if (index < 0 || index > size()) {
            throw new IndexOutOfException("下标越界!");
        }
    }

    //找到 index-1位置的节点的地址
    private ListNode findIndexSubOne(int index) {
        ListNode cur = head;
        int count = 0;
        while (count != index - 1) {
            cur = cur.next;
            count++;
        }
        return cur;
    }

    //指定位置插入
    public boolean addIndex(int index, int data) throws IndexOutOfException {
        //判断坐标合法性
        checkIndex(index);

        //index=0这种情况需要特殊处理一下【1.head=null,index=0;2.head!=null,index=0】
        if (index == 0) {
            addFirst(data);
            return true;
        }
        //尾插不用特殊考虑,以下包含了尾插

        //中间插入
        ListNode newNode = new ListNode(data);
        ListNode cur = findIndexSubOne(index);
        newNode.next = cur.next;
        cur.next = newNode;
        return true;
    }

🍑7、查找是否包含关键字key是否在单链表当中

思路: 遍历链表,比对value值即可

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

🍑8、删除第一次出现关键字为key的节点

手撕Java集合——链表,Java数据结构,java,链表,数据结构,经验分享,学习,开发语言
手撕Java集合——链表,Java数据结构,java,链表,数据结构,经验分享,学习,开发语言

    //删除第一次出现关键字为key的节点
    public void remove(int key) {
        //链表一个结点都没有
        if (head == null) {
            System.out.println("链表为空!");
            return;
        }
        //判断头结点的val
        if (head.val == key) {
            head = head.next;
            return;
        }
        //找到key的前驱结点
        ListNode cur = head;
        while (cur.next != null) {
            if (cur.next.val == key) {
                cur.next = cur.next.next;
                return;
            }
            cur = cur.next;
        }
        System.out.println("未找到关键字" + key);
    }

🍑9、删除所有值为key的节点

思路: 这个算法相比于“删除第一次出现关键字为key的节点”只需略微调整(划去return;单独判断头结点)
注意:这里头结点的判断放在了最后,因为这里是删除所有值为key的节点,由于head结点的特殊性(head结点的value=key),且head后对key值的删除处理具有同一性,所以这里就先一并处理head后结点,最后单独判断head结点。对于“删除第一次出现关键字为key的节点”,由于此时的场景是处理第一次出现的key值,所以就必须先处理head结点。

    //删除所有值为key的节点
    public void removeAllKey(int key) {
        //为空情况
        if (head == null) {
            return;
        }
        //头结点后存在key值的情况
        ListNode cur = head;
        while (cur.next != null) {
            if (cur.next.val == key) {
                cur.next = cur.next.next;
            } else {
                cur = cur.next;
            }
        }
        //头结点单独判断
        if (head.val == key) {
            head = head.next;
        }
    }

🍑10、得到单链表的长度

思路: 遍历链表,返回count计数值即可。

    //得到单链表的长度
    public int size() {
        int count = 0;
        ListNode cur = head;
        while (cur != null) {
            count++;
            cur = cur.next;
        }
        return count;
    }

🍑11、清空链表

思路: 在Java中,当一个对象没有任何引用指向时,Java自带的垃圾回收机制会自动删除该对象。因此, 只要将链表的头节点赋值为空,链表的所有节点就会被视为不再被引用,可以通过垃圾回收机制来删除它们。

具体来说,当链表的头节点变成了null,链表的所有节点就不再有任何引用指向它们,这意味着这些节点成为Java内存中的"孤儿"节点,也就是不再被外部引用的节点。这时,Java垃圾回收机制会自动触发,将不再被引用的节点删除。

需要注意的是:如果链表中的节点存在其他引用指向它们,那么这些节点就不会被视为垃圾,也不会被自动删除。因此,在清空链表前需要确保没有其它引用指向链表中的任何一个节点,否则这些节点会一直被占用,浪费内存空间。

    //清空链表
    public void clear() {
        head = null;
    }

三、无头双向非循环链表

双向不带头非循环链表,与上述单向不带头非循环链表的主要差别体现在功能接口的实现上,特别是删除和插入操作时,不需要在保存前驱结点,可根据当前结点进行操作。
手撕Java集合——链表,Java数据结构,java,链表,数据结构,经验分享,学习,开发语言

下面是无头双向非循环链表的代码实现,很多功能接口和上述单链表的实现多有雷同,并且下面代码中给出了详细的注释,大家可以参考理解:

// 2、无头双向链表实现
public class MyLinkedList {
    static class Node {
        // 数据
        public int val;
        // 前驱结点
        public Node prev;
        // 后继结点
        public Node next;
        // 结点构造
        public Node(int val) {
            this.val = val;
        }
    }
    // 当前头结点
    public Node head;
    // 当前尾结点
    public Node last;

    //打印双向链表(同单向链表)
    public void display() {
        Node cur = head;
        while (cur != null) {
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
        System.out.println();
    }

    //头插法(思路同单向链表)
    public void addFirst(int data) {
        Node newnode = new Node(data);
        if (head == null) {
            head = newnode;
            last = newnode;
        } else {
            newnode.next = head;
            head.prev = newnode;
            head = newnode;
        }
    }

    //尾插法(思路同单向链表)
    public void addLast(int data) {
        Node newnode = new Node(data);
        if (head == null) {
            head = newnode;
            last = newnode;
        } else {
            last.next = newnode;
            newnode.prev = last;
            last = newnode;
        }
    }

    //得到双向链表的长度(同单链表)
    public int size() {
        int count = 0;
        Node cur = head;
        while (cur != null) {
            count++;
            cur = cur.next;
        }
        return count;
    }
    
    //任意位置插入(注:第一个数据节点为0号下标)
    public void addIndex(int index, int data) {
        // 判断坐标合法性
        if (index<0 || index>size()) {
            throw new IndexOutOfException("坐标非法!");
        }
        // 构建新节点
        Node newnode = new Node(data);
        // 处理头插尾插特殊情况
        if (index==0) {
            addFirst(data);
            return;
        }
        if (index==size()) {
            addLast(data);
            return;
        }
        // 处理在中间插入情况(这里体现了双向链表的优势)
        // 将cur结点指向当前坐标
        Node cur = head;
        while (index!=0) {
            cur = cur.next;
            index--;
        }
        // 修改新节点的 next 域
        newnode.next = cur;
        // 修改 cur 结点的前驱结点的 next 域
        cur.prev.next = newnode;
        // 修改新节点的 prev 域
        newnode.prev = cur.prev;
        // 修改 cur 结点的 prev 域
        cur.prev = newnode;
    }

    //查找是否包含关键字key是否在单链表当中(同单链表)
    public boolean contains(int key) {
        Node cur = head;
        while (cur!=null) {
            if (cur.val==key) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    //删除第一次出现关键字为key的节点(体现双向链表优势)
    public void remove(int key) {
        Node cur = head;
        while (cur!=null) {
            if (cur.val==key) {
                //如果只有一个结点(单链表不存在last所以不存在这一步)
                if (head == last) {
                    head = null;
                    last = null;
                    return;
                }
                //如果cur是头结点
                if (cur == head) {
                    head = head.next;
                    head.prev = null;
                    return;
                }
                //如果cur是尾结点
                if (cur == last) {
                    last = last.prev;
                    last.next = null;
                    return;
                }
                // 如果cur是中间结点
                cur.prev.next = cur.next;
                cur.next.prev = cur.prev;
                return;
            }
            cur = cur.next;
        }
    }

    //删除所有值为key的节点[对上面代码进行改进]
    public void removeAllKey(int key) {
        Node cur = head;
        while (cur!=null) {
            //满足条件开始删除
            if (cur.val==key) {
                if (head == last) {
                    // 如果只有1个结点
                    head = null;
                    last = null;
                    return;
                } else if (cur == head) {
                    // 如果cur是头结点,并且节点数必定大于等于2
                    head = head.next;
                    if (head!=null) {
                        head.prev = null;
                    }
                } else if (cur == last){
                    // 如果是尾巴结点
                    last = last.prev;
                    last.next = null;
                } else {
                    // 如果是中间结点
                    cur.prev.next = cur.next;
                    cur.next.prev = cur.prev;
                }
            }
            cur = cur.next;
        }
    }

    //双向链表的清空操作
    public void clear() {
        Node cur = head;
        while (cur!=null) {
            Node curNext = cur.next;
            cur.prev=null;
            cur.next=null;
            cur = curNext;
        }
        head=null;
        last=null;
    }
}

四、Java集合中的 LInkedList

java.util包下为我们提供了LinkedList集合类,它的底层就是一个无头双向非循环链表结构。并且这里的 LinkedList是以泛型方式实现的,使用时必须要先实例化,同时,它也实现了 List 接口,可以通过 List 接口接收LinkedList对象,并使用List方法操作LinkedList对象:
手撕Java集合——链表,Java数据结构,java,链表,数据结构,经验分享,学习,开发语言

🍑1、LinkedList构造方法

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

🍑2、LinkedList常用方法

方法 描述
boolean add(E e) 在链表尾部插入元素 e
void add(int index, E element) 将元素 element 插入到指定的 index 位置。
void addFirst(E e) 在该列表开头插入指定的元素。
boolean addAll(Collection<? extends E> c) 将集合 c 中的所有元素尾部插入链表。
E remove(int index) 删除指定 index 位置的元素,并返回被删除的元素。
boolean remove(Object o) 删除遇到的第一个等于 o 的元素,若删除成功则返回 true
E get(int index) 获取指定 index 位置的元素。
E set(int index, E element) 将指定 index 位置的元素替换为新的元素 element,并返回原元素。
void clear() 清空链表中的所有元素。
boolean contains(Object o) 判断链表中是否包含元素 o,如果存在则返回 true
int indexOf(Object o) 返回第一个出现的元素 o 的索引,如果不存在则返回 -1
int lastIndexOf(Object o) 返回最后一个出现的元素 o 的索引,如果不存在则返回 -1
List subList(int fromIndex, int toIndex) 截取链表部分元素,并返回一个新的 List 对象。

五、线性表总结:LinkedList和ArrayList区别

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

说明: ArrayList支持随机访问,LinkedList不支持随机访问"的意思是指在数据结构中,ArrayList可以通过索引直接访问和获取元素,而LinkedList不能通过索引进行直接访问和获取。文章来源地址https://www.toymoban.com/news/detail-648044.html

到了这里,关于手撕Java集合——链表的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 第14章_集合与数据结构拓展练习(前序、中序、后序遍历,线性结构,单向链表构建,单向链表及其反转,字符串压缩)

    1、前序、中序、后序遍历 分析: 完全二叉树: 叶结点只能出现在最底层的两层,且最底层叶结点均处于次底层叶结点的左侧 2、线性结构 3、其它 4、单向链表构建 (1)定义一个单向链表SingleLinked类 包含私有的静态内部类Node 包含Object类型的data属性和Node类型的next属性 包含

    2024年01月23日
    浏览(48)
  • Java 数据结构集合

    详细请转到@pdai的博客 1.1 数组 (Array) 数组的优点: 存取速度快 数组的缺点: 事先必须知道数组的长度 插入删除元素很慢 空间通常是有限制的 需要大块连续的内存块 插入删除元素的效率很低 源码分析: 1、底层数据结构是Object 2、构造函数包括无参构造和有参数构造,有参构

    2024年01月24日
    浏览(41)
  • 探索Java集合框架—数据结构、ArrayList集合

    Java集合的使用相信大家都已经非常得心应手,但是我们怎么做到知其然,更知其所以然这种出神入化的境界呢?我们揭开集合框架底层神秘面纱来一探究竟 目录 一、背景介绍 二、思路方案 数据结构是什么? 数据结构可以分为线性和非线性两种数据结构 线性数据结构: 非

    2024年02月10日
    浏览(39)
  • 数据结构——链表(java)

    1.1 定义 链表是一种物理存储结构上非连续存储结构,数据元素的逻辑顺序是通过链表中的引用链接次序实现的。 如图所示: 1.2 链表分类 单向、双向;带头、不带头;循环、非循环 重点 :单向不带头非循环、双向不带头非循环(集合类底层) 如图:单项带头非循环链表结

    2024年02月09日
    浏览(42)
  • 【数据结构一】初始Java集合框架(前置知识)

           Java语言在设计之初有一个非常重要的理念便是:write once,run anywhere!所以Java中的数据结构是已经被设计者封装好的了,我们只需要实例化出想使用的对象,便可以操作相应的数据结构了,本篇文章中我会向大家简单 介绍一下什么是数据结构 ,以及 对Java中常用的数

    2024年02月04日
    浏览(46)
  • java八股文面试[数据结构]——集合框架

    Java集合类主要由两个根接口Collection和Map派生出来的。 Collection派生出了三个子接口: Map接口派生: Map代表的是存储key-value对的集合,可根据元素的key来访问value。  因此Java集合大致也可分成 List、Set、Queue、Map四种接口体系 。 List代表了有序可重复集合,可直接根据元素的索

    2024年02月11日
    浏览(40)
  • JAVA数据结构篇--13线程安全的Set 集合

    前言:java 中用于存放不重复元素的set 集合,其中无序的HashSet,以及有序的LinkedHashSet和TreeSet 都是非线程安全的,那么多线程环境下,我们要存放不重复的元素,需要使用哪种集合进行数据存取; 1 使用: 2 过程: 2.1 放入获取元素: Collections.synchronizedSet:通过使用synchron

    2024年02月16日
    浏览(40)
  • 数据结构——链表的实现(Java版)

    目录 一、链表 二、代码实现 1.创建结点 2.构造函数 3.链表的相关属性 4.添加虚拟节点 5.判断链表是否为空 6.添加方法 (1)在头部添加 (2)在尾部添加 (3)在索引位置添加 (4)对头插法和尾插法代码进行简化(调用任意位置添加的方法) 7.打印链表(遍历,重写toString方

    2024年01月23日
    浏览(46)
  • 数据结构(Java实现)-集合与时间和空间复杂度

    什么是集合框架 Java 集合框架 Java Collection Framework ,又被称为容器 container ,是定义在 java.util 包下的一组接口 interfaces 和其实现类 classes 。 什么是数据结构 数据结构(Data Structure)是计算机存储、组织数据的方式,指相互之间存在一种或多种特定关系的数据元素的 集合。 容器

    2024年02月12日
    浏览(42)
  • 数据结构(Java实现)LinkedList与链表(下)

    ** ** 结论 让一个指针从链表起始位置开始遍历链表,同时让一个指针从判环时相遇点的位置开始绕环运行,两个指针都是每次均走一步,最终肯定会在入口点的位置相遇。 LinkedList的模拟实现 单个节点的实现 尾插 运行结果如下: 也可以暴力使用 全部代码 MyLinkedList IndexOut

    2024年02月11日
    浏览(45)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包