【数据结构(三)】链表与LinkedList

这篇具有很好参考价值的文章主要介绍了【数据结构(三)】链表与LinkedList。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

❣博主主页: 33的博客❣
▶️文章专栏分类:数据结构◀️
🚚我的代码仓库: 33的代码仓库🚚
🫵🫵🫵关注我带你学更多数据结构知识
【数据结构(三)】链表与LinkedList,数据结构,数据结构,链表,LinkedList,java

1. 前言

在上一篇文章中,我们已经认识了顺序表,通过源码我们知道ArrayList底层是使用数组来存储元素,当在ArrayList任意位置插入或者删除元素时,就需要将后序元素整体往前或者往后搬移,时间复杂度为O(n),效率比较低,因此ArrayList不适合做任意位置插入和删除比较多的场景。因此:java集合中又引入了LinkedList,即链表结构。

2.链表

链表是一种物理存储结构上非连续存储结构,数据元素的逻辑顺序是通过链表中的引用链接次序实现的 。
【数据结构(三)】链表与LinkedList,数据结构,数据结构,链表,LinkedList,java
【数据结构(三)】链表与LinkedList,数据结构,数据结构,链表,LinkedList,java
注意: 链式结构是在逻辑上连续,但在物理上不一定连续。

实际中链表的结构非常多样,以下情况组合起来就有8种链表结构:
1.单向或者双向
【数据结构(三)】链表与LinkedList,数据结构,数据结构,链表,LinkedList,java
2.带头或者不带头
【数据结构(三)】链表与LinkedList,数据结构,数据结构,链表,LinkedList,java
3.循环或者非循环
【数据结构(三)】链表与LinkedList,数据结构,数据结构,链表,LinkedList,java
虽然有这么多的链表的结构,但是我们重点掌握两种:
无头单向非循环链表:结构简单,一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构,如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。

3.链表的实现

3.1 IList接口

public interface IList {
    //头插法
    void addFirst(int data);
    //尾插法
    void addLast(int data);
    //任意位置插入,第一个数据节点为0号下标
    void addIndex(int index,int data);
    //查找是否包含关键字key是否在单链表当中
    boolean contains(int key);
    //删除第一次出现关键字为key的节点
    void remove(int key);
    //删除所有值为key的节点
    void removeAllKey(int key);
    //得到单链表的长度
    int size();
    void clear();
    void display();
}

3.2MyLinkList实现


public class MyLinkList implements IList{
    //内部类
    class Node{
        public int val;
        public Node next;//下一个结点
        public Node head;//头结点
        public Node(int val){
            this.val=val;
        }
    }  
    //自己创造的一个链表
    public void create(){
        Node node1=new Node(1);
        Node node2=new Node(2);
        Node node3=new Node(3);
        node1.next=node2;
        node2.next=node3;
       head= node1;
    }
    //头插法
    @Override
    public void addFirst(int data) {
        Node node=new Node(data);
        node.next=head;
        head=node;
    }
    //尾插法
    @Override
    public void addLast(int data) {
    Node node=new Node(data);
    Node end=head;
    while (end.next!=null){
        end=end.next;
    }
    end.next=node;
    }
    //在某一个位置插入一个元素
    @Override
    public void addIndex(int index, int data) {
    if(index<0||index>size()){
        System.out.println("位置不合法");
        return;
    }
    if(index==0){
        addFirst(data);
        return;
    }
    if(index==size()){
        addLast(data);
        return;
    }
    Node node=new Node(data);
    Node pre=getNode(index);
    node.next=pre.next;
    pre.next=node;
    }
    public Node getNode(int index){
        Node node=head;
        while (index-1!=0){
            node=node.next;
            index--;
        }
        return node;
    }
	//是否包含某一个元素
    @Override
    public boolean contains(int key) {
        Node node=head;
        while (node!=null){
            if(node.val==key){
                return true;
            }
            node=node.next;
        }
        return false;
    }
	//删除第一个为key的元素
    @Override
    public void remove(int key) {
    if(head.val==key){
        head=head.next;
        return;
    }
    int index=getindex(key);
    Node node=head;

    while (index-1!=0){
        node=node.next;
        index--;
    }
    node.next=node.next.next;
    }
    //根据key返回它的前一个坐标
    public int getindex(int key){
        int count=0;
        Node node=head;
        while (node!=null){
            if(node.val==key){
                return count;
            }
            node=node.next;
            count++;
        }
        return -1;
    }
	//删除所有为key的元素
    @Override
    public void removeAllKey(int key) {
    if (head==null){
        return;
    }
    Node node=head;
    Node cur=head.next;
    while (cur!=null){
        if(cur.val==key){
            node.next=cur.next;
            cur=cur.next;
        }else {
            node=node.next;
            cur=cur.next;
        }
    }
    if(head.val==key){
        head=head.next;
    }
    }
	//求链表大小
    @Override
    public int size() {
        Node node=head;
        int count=0;
        while (node!=null){
           count++;
            node=node.next;
        }
        return count;
    }
	//清空链表
    @Override
    public void clear() {
    Node node=head;
    while (node!=null){
        Node next=node.next;
        node.next=null;
        node=next;
    }
    head=null;
    }
	//打印链表
    @Override
    public void display() {
        Node node=head;
        while (node!=null){
            System.out.print(node.val+" ");
            node=node.next;
        }

    }
}

3.3 Test

public class Test {
    public static void main(String[] args) {
        MyLinkList myLinkList=new MyLinkList();
        myLinkList.create();
        myLinkList.display();
        System.out.println();
        //头插法
        System.out.println("头插法");
        myLinkList.addFirst(12);
        myLinkList.addFirst(13);
        myLinkList.addFirst(14);
        myLinkList.display();
        System.out.println();
        //尾插法
        System.out.println("尾插法");
        myLinkList.addLast(21);
        myLinkList.addLast(22);
        myLinkList.addLast(23);
        myLinkList.display();
        System.out.println();
        //中间位置插入
        System.out.println("在1位置插入100");
        myLinkList.addIndex(1,100);
        myLinkList.addIndex(1,100);
        myLinkList.addIndex(1,100);
        myLinkList.display();
        System.out.println();
        //查找元素
        Boolean a=myLinkList.contains(100);
        System.out.println(a);
        //删除第一个100元素
        myLinkList.remove(100);
        myLinkList.display();
        System.out.println();
        //删除所有100的元素
        myLinkList.removeAllKey(100);
        myLinkList.display();
        System.out.println();
        //求size
        int Size=myLinkList.size();
        System.out.println(Size);
        //清空链表
        myLinkList.clear();
        myLinkList.display();
    }
}

输出结果如下:
【数据结构(三)】链表与LinkedList,数据结构,数据结构,链表,LinkedList,java

4.LinkedList

LinkedList的底层是双向链表结构,由于链表没有将元素存储在连续的空间中,元素存储在单独的节点中,然后通过引用将节点连接起来了,因此在在任意位置插入或者删除元素时,不需要搬移元素,效率比较高
LinkedList源码:
【数据结构(三)】链表与LinkedList,数据结构,数据结构,链表,LinkedList,java

【说明】
通过上图所示,我们可以知道LinkedList实现了List接口,LinkedList的底层使用了双向链表。

4.1 LinkedList的使用

构造:

方法 解释
LinkedList() 无参构造
public LinkedList(Collection<? extends E> c) 使用其他集合容器中元素构造List
 public static void main(String[] args) {
 // 构造一个空的LinkedList
 List<Integer> list1 = new LinkedList<>();
 List<String> list2 = new java.util.ArrayList<>();
 list2.add("JavaSE");
 list2.add("JavaWeb");
 list2.add("JavaEE");
 // 使用ArrayList构造LinkedList
 List<String> list3 = new LinkedList<>(list2);
 }

其他常用方法:

方法 解释
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

4.2 LinkedList的遍历

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());
    // foreach遍历
    for (int e:list) {
        System.out.print(e + " ");
    }
    System.out.println();
    // 使用迭代器遍历---正向遍历
    ListIterator<Integer> it = list.listIterator();
    while(it.hasNext()){
        System.out.print(it.next()+ " ");
    }
    System.out.println()

4.3ArrayList和LinkedList的区别

【数据结构(三)】链表与LinkedList,数据结构,数据结构,链表,LinkedList,java

本篇文章主要介绍了链表的基础知识,简单介绍了什么是链表以及如何实现一个链表,以及LinkedList的操作方法,在下一篇文章中博主将带领同学们一起学习链表的相关习题。

下期预告:链表经典练习题文章来源地址https://www.toymoban.com/news/detail-849465.html

到了这里,关于【数据结构(三)】链表与LinkedList的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 【数据结构】LinkedList与链表

    上节课已经熟悉了ArrayList的使用,并且进行了简单模拟实现。通过源码知道,ArrayList底层使用数组来存储元素: 由于其底层是一段连续空间,当 在ArrayList任意位置插入或者删除元素时,就需要将后序元素整体往前或者往后搬移,时间复杂度为O(n),效率比较低 ,因此A rrayLi

    2024年02月07日
    浏览(45)
  • 数据结构—LinkedList与链表

    目录 一、链表 1. 链表的概念及结构 1. 单向或者双向 2. 带头或者不带头 3. 循环或者非循环 二.LinkedList的使用  1.LinkedList概念及结构 2. LinkedList的构造 3. LinkedList的方法 三. ArrayList和LinkedList的区别           链表是一种 物理存储结构上非连续 存储结构,数据元素的 逻辑

    2024年02月04日
    浏览(52)
  • LinkedList数据结构链表

    LinkedList 在Java中是一个实现了 List 和 Deque 接口的双向链表。它允许我们在列表的两端添加或删除元素,同时也支持在列表中间插入或移除元素。在分析 LinkedList 之前,需要理解链表这种数据结构: 链表 :链表是一种动态数据结构,由一系列节点组成,每个节点包含数据部分

    2024年02月20日
    浏览(44)
  • 【C/C++数据结构】链表与快慢指针

    目录 一、单链表 二、双向循环链表 三、判断链表是否带环 四、链表的回文结构判断 五、复制带随机指针的链表 优点 :头部增删效率高,动态存储无空间浪费 缺点 :尾部增删、遍历效率低,不支持随机访问节点 头结点 :单链表头结点可有可无,带头结点更方便进行初始

    2024年02月16日
    浏览(90)
  • 【数据结构二】链表和LinkedList详解

    目录 链表和LinkedList  1.链表的实现 2.LinkedList的使用 3.ArrayList和LinkedList的区别 4.链表OJ题训练         当 在 ArrayList 任意位置插入或者删除元素时,就需要将后序元素整体往前或者往后 搬移,时间复杂度为 O(n) ,效率比较低,因此 ArrayList 不适合做任意位置插入和删除比较多

    2024年01月20日
    浏览(46)
  • 【数据结构】链表(单链表与双链表实现+原理+源码)

    博主介绍:✌全网粉丝喜爱+、前后端领域优质创作者、本质互联网精神、坚持优质作品共享、掘金/腾讯云/阿里云等平台优质作者、擅长前后端项目开发和毕业项目实战✌有需要可以联系作者我哦! 🍅附上相关C语言版源码讲解🍅 👇🏻 精彩专栏推荐订阅👇🏻 不然下次找

    2024年01月24日
    浏览(142)
  • 【数据结构 | 入门】线性表与链表 (问题引入&实现&算法优化)

    🤵‍♂️ 个人主页: @计算机魔术师 👨‍💻 作者简介:CSDN内容合伙人,全栈领域优质创作者。 本文是浙大数据结构学习笔记专栏 这里我们引入一个问题,最常见的多项式,我们如何使用编程将多项式表示出来呢? 我们可以使用数组来表示,但是会随着一个问题,如下图底

    2024年01月21日
    浏览(71)
  • 【数据结构与算法分析】反转链表与顺序表(内含源码,思路清晰)

      顺序表和链表都是数据结构中常见的线性表。它们的主要区别在于 内存管理方式不同 。   顺序表(Array)是由一系列元素按照一定顺序依次排列而成,它使用连续的内存空间存储数据。顺序表使用一个数组来存储数据,数组中的每个元素都可以通过下标来访问。顺序

    2024年02月07日
    浏览(105)
  • 【数据结构】_4.List接口实现类LinkedList与链表

    目录 1.链表的结构与特点 1.1 链表的结构: 1.2 链表的特点: 2. 不带头单链表的模拟实现 3. 单链表OJ 3.1 题目1:移除链表元素:  3.2 题目2:反转一个单链表 3.3 题目3:返回链表的中间结点 3.4 题目4:链表的倒数第k个结点 3.5 题目5:合并两个有序链表 3.6 题目6:链表的回文结构

    2024年02月15日
    浏览(45)
  • 数据结构三叉链表与线索二叉树的思路与实现详解

    ❤️作者主页:微凉秋意 ✅作者简介:后端领域优质创作者🏆,CSDN内容合伙人🏆,阿里云专家博主🏆 我们知道最常见的链式存储二叉树的结构体中有数据域、左孩子指针以及右孩子指针,通过递归来创建二叉树。显而易见的是,想找到二叉树中任意一个结点的 前驱 或 后

    2024年02月02日
    浏览(61)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包