【数据结构】认识链表和模拟实现单链表

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

即使骑的小电驴,也要奋力前进

单项链表模拟,Java数据结构,链表,数据结构,java


目录

1.链表

1.1 链表的概念 

1.2 链表的逻辑结构图和物理结构图

1.2.1 链表的逻辑结构图 

1.2.2 链表的物理结构图 

1.3链表结构的分类

1.3.1 链表通过什么进行结构的分类 

1.3.2 不同链表结构的逻辑图

2.模拟实现一个单向链表 

2.1 MyLinkedList类的内部类

2.2 MyLinkedList类的成员属性

2.3 MyLinkedList类的成员方法

2.3.1 在链表开头插入一个新结点

2.3.2 获取链表的最后一个结点

2.3.3 在链表尾部插入一个新的结点 

2.3.4  返回指定位置的前一个结点

2.3.5 在链表指定位置插入一个新结点 

2.3.6  判断是否需要删除第一个结点

2.3.6 删除第一次出现的指定数据的结点

2.3.7 删除所有指定数据的结点

2.3.8 查找链表中是否有指定的数据

2.3.9 获取链表的长度 

2.3.10 打印链表 

 2.3.11 清空链表


1.链表

1.1 链表的概念 

链表是一种物理存储结构上非连续存储结构,数据元素的逻辑顺序是通过链表中的引用链接次序实现的

链表的特点:①空间上,按需给空间  ②不要求物理空间连续,头部和中间的插入删除,不需要挪动数据

1.2 链表的逻辑结构图和物理结构图

1.2.1 链表的逻辑结构图 

单项链表模拟,Java数据结构,链表,数据结构,java通过以上的逻辑结构图,我们可以看出链表是由结点组成,每个结点都包括两部分:数据域指针域,通过指针域指向下一个结点来完成结点与结点之间的相连

  • 数据域:用来存储数据
  • 指针域:用来指向下一个结点 

1.2.2 链表的物理结构图 

单项链表模拟,Java数据结构,链表,数据结构,java

通过以上的物理结构图,我们可以看到除了最后一个结点的指针指向null,其余的指针域都存储下一个结点的地址,所以指针域是用来存储下一个结点的地址来完成链接的 

1.3链表结构的分类

1.3.1 链表通过什么进行结构的分类 

 链表通过以下表格中的六种情况组合起来进行结构的分类:

单向 双向
带头 不带头
循环 非循环

 可以分为以下八种结构:

单向不带头循环链表
单向不带头非循环链表
单向带头循环链表
单向不带头循环链表
双向不带头循环链表
双向不带头非循环链表
双向带头循环链表
双向带头非循环链表

1.3.2 不同链表结构的逻辑图

①单向

单项链表模拟,Java数据结构,链表,数据结构,java

单向:只要一个指针域存储下一个结点的地址 

②双向 

单项链表模拟,Java数据结构,链表,数据结构,java

双向:有两个指针域,前指针域是用来存储前一个结点的地址,后指针域是用来存储后一个结点地址

③带头 

单项链表模拟,Java数据结构,链表,数据结构,java

带头:有一个哨兵位结点(head),数据域一般给一个无效值,当做头结点

④不带头

单项链表模拟,Java数据结构,链表,数据结构,java

不带头:没有哨兵位结点

⑤循环 

单项链表模拟,Java数据结构,链表,数据结构,java

循环:最后一个结点没有指向空而是指向了第一个结点 

⑥非循环 

单项链表模拟,Java数据结构,链表,数据结构,java

非循环:最后一个结点直接指向了空 

2.模拟实现一个单向链表 

现在我们知道了什么是链表,以及链表的分类,那么接下来我们就来模拟实现一个存放整型数据单向不带头非循环链表

我们首先需要创建一个类来实现这样一个链表: 

public class MyLinkedList {

}

接下来我们就需要将这个实现链表的过程全部放在 MyLinkedList 这个类中

2.1 MyLinkedList类的内部类

我们知道链表是用结点来存储数据的,并且还是用结点来实现结点与结点之间的链接

那我们现在就需要在 MyLinkedList类 中创建一个内部类当做结点类 

private class Node {
    private int data;//数据域
    private Node next;//链接域
    private Node(int data) {
        this.data = data;
    }
}
  • data:用来存放数据
  • next:用来存储下一个结点的地址,从而达到结点与结点之间的链接
  • 构造方法:每实例化一个结点类时,都需要调用构造方法,来把数据放入数据域

2.2 MyLinkedList类的成员属性

我们需要给第一个结点设置为头结点,这样用户才知道链表应该从哪里开始,这样单链表才不会因为没有被指向而被回收

private Node head;//记录第一个结点

注:只要第一个结点没有被回收,其他结点也不会被回收,因为前一个结点的 next 存储着后一个结点的地址,这样前一个结点的指针域就指向了后一个结点 

2.3 MyLinkedList类的成员方法

2.3.1 在链表开头插入一个新结点

在链表开头插入一个结点,首先需要根据 data 数据实例化一个结点。然后让这个新结点的 next 指针域存 head 的地址, 这样就让新的结点与后面的结点链接起来了,最后让 head 等于这个新结点,这样这个新结点就变成了第一个结点

//头插法
public void addFirst(int data) {
    Node nodeTmp = new Node(data);
    nodeTmp.next = this.head;
    this.head = nodeTmp;
}

2.3.2 获取链表的最后一个结点

首先 head 不能移动,如果移动第一个结点就会因没有被指向而回收,那么后面结点也就会因为没有被指向而被回收,所以需要创建一个临时的结点类型的变量 src,将 head 指向的结点赋值给它,这样 head src 同时指向了第一个结点,当src 移动到其他结点,第一个结点还是会被 head 所指向。src 通过循环一直等于下一个结点,当 src 存储的结点的 next null 时就为最后一个结点

//获取链表的最后一个结点
private Node lastNode() {
    Node src = this.head;
    while (src.next != null) {
        src = src.next;
    }
    return src;
}

注:这个方法是private修饰所以只能在 MyLinkedList类 中使用

2.3.3 在链表尾部插入一个新的结点 

在链表尾部插入一个结点,首先需要这个链表是否为空,如果链表为 null ,尾插一个结点就相当于在链表开头插入一个结点。如果链表不为 null ,尾部插入一个结点就需要根据 data 数据实例化一个结点,然后通 lastNode 方法获取最后一个结点,让最后一个结点的 next 存储新结点的地址即可

//尾插法
public void addLast(int data) {
    if (head == null) {
        addFirst(data);
        return;
    }
    Node nodeTmp = new Node(data);
    Node last = lastNode();
    last.next = nodeTmp;
}

2.3.4  返回指定位置的前一个结点

首先判断位置是否合法,如果不合法直接返回 null ,否则用一个临时结点变量等于 head 指向的结点,然后通过循环 index - 1 次而找的指定位置的前一个结点

//返回指定位置的前一个结点
private Node prevNode(int index) {
    if (index > size() || index < 0) {
        return null;
    }
    Node src = this.head;
    while(index != 1) {
        src = src.next;
        index--;
    }
    return src;
}

2.3.5 在链表指定位置插入一个新结点 

第一步判断指定位置是否合法,如果不合法直接返回 false。否则进入第二步判断插入的位置是否为第一个结点位置,如果是就直接采用头插法在链表的开头插入一个结点。否则进入第三步判断插入的位置是否为最后一个结点的下一个位置,如果是就直接采用尾插法在链表的尾部插入一个结点。否则就在实例化一个 data 数据结点,调用 preNode 方法获取指定位置的前一个结点,在用一个临时变量去存储前一个结点的后一个结点,让前一个结点的 next 存储这个新的结点地址,再让这个新的结点的 next 存储后一个结点地址即可

单项链表模拟,Java数据结构,链表,数据结构,java

//任意位置插入,第一个数据结点为0号下标
public boolean addIndex(int index,int data) {
    if (index > size() || index < 0) {
        return false;
    } else if (index == 0) {
        addFirst(data);
    } else if (index == size()) {
        addLast(data);
    } else {
        Node nodeTmp = new Node(data);
        Node prev = prevNode(index);//指定位置前一个结点
        Node tmp = prev.next;//指定位置的结点
        prev.next = nodeTmp;
        nodeTmp.next = tmp;
    }
    return true;
}

注:if...else if...else if...else...这种多判断只会执行其中的一个

2.3.6  判断是否需要删除第一个结点

判断数据 key 是否与第一个结点数据域中的数据相同,如果相同则让head等于head.next,这样head就指向了下一个结点,也就删除了第一个结点

//判断第一个结点是否是指定的结点,如果是则删除第一个结点
private boolean judgeFistNode(int key) {
    if (key == this.head.data) {
        this.head = this.head.next;
        return true;
    }
    return false;
}

2.3.6 删除第一次出现的指定数据的结点

首先判断这个链表是否为 null,否则就判断指定数据的结点是否为链表的第一个结点,否则就通过两个结点变量去找这个数据结点以及它的前一个结点,找到之后让它的前一个结点的 next 存储它后结点的地址然后直接return,因为只删除第一次输出的指定数据的结点。如果遍历完都没有找到这个数据结点则没有这个数据结点 

//删除第一次出现关键字为key的节点
public void remove(int key) {
    if (this.head == null) {
        return;
    }
    boolean judge = judgeFistNode(key);
    if (judge == true) {
        return;
    }
    Node src = this.head;
    Node slow = this.head;
    while (src != null) {
        if (src.data != key) {
            slow = src;
            src = src.next;
        } else {
            slow.next = src.next;
            return;
        }
    }
}

2.3.7 删除所有指定数据的结点

首先判断这个链表是否为 null, 否则就通过两个结点变量去找这个数据结点以及它的前一个结点,找到之后让它的前一个结点的 next 存储它后结点的地址,一直遍历完,因为要删除所有指定数据的结点。遍历完后在判断第一个结点是否为空,也就相当于如果第一个结点是要删除的结点,先不管它,先删后面的在删第一个结点

//删除所有值为key的节点
public void removeAllKey(int key) {
    if (this.head == null) {
        return;
    }
    Node src = this.head;
    Node slow = this.head;
    while (src != null) {
        if (src.data != key) {
            slow = src;
            src = src.next;
        } else {
            slow.next = src.next;
            src = src.next;
        }
    }
    judgeFistNode(key);
}

2.3.8 查找链表中是否有指定的数据

直接将这个链表遍历一遍,如果有直接返回 true,否则返回 false 

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

2.3.9 获取链表的长度 

直接将这个链表遍历一遍用一个整型变量计数即可 

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

2.3.10 打印链表 

首先判断这个链表是否为 null ,如果为空直接打印 null。否则将这个链表遍历一遍,打印每个结点数据域中的数据 

//打印链表
public void display() {
    if (this.head == null) {
        System.out.print("null");
    }
    Node src = head;
    while (src != null) {
        System.out.print(src.data + " ");
        src  = src.next;
    }
    System.out.println();
}

 2.3.11 清空链表

直接让 head 指向 null,这样第一个结点就没有被指向了,会直接被编译器回收。第一个结点被回收了,第二个结点也就没有被指向了也会被回收,依次如此,直到将整个链表全部回收 文章来源地址https://www.toymoban.com/news/detail-623054.html

//清除链表
public void clear() {
    this.head = null;
}

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

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

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

相关文章

  • 数据结构2:顺序表和链表

    目录 1.线性表 2.顺序表 2.1概念及结构 2.2接口实现 2.3数据相关面试题 2.4顺序表的问题及思考 3.链表 3.1链表的概念及结构 3.2链表的分类 3.3链表的实现 3.4链表面试题 3.5双向链表的实现 4.顺序表和链表的区别 线性表(linear list)是具有相同特征的数据元素的有限序列。线性表是

    2023年04月17日
    浏览(30)
  • 【数据结构二】链表和LinkedList详解

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

    2024年01月20日
    浏览(34)
  • 数据结构顺序表和链表(超详细)

    线性表 ( linear list ) 是 n 个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使 用的数据结构, 常见的线性表:顺序表、链表、栈、队列、字符串 ... 线性表在逻辑上是线性结构,也就说是连续的一条直线。但是在物理结构上并不一定是连续的, 线性表在

    2024年02月13日
    浏览(31)
  • 数据结构:2_顺序表和链表

    线性表(linear list)是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构, 常见的线性表:顺序表、链表、栈、队列、字符串… 线性表在逻辑上是线性结构,也就说是连续的一条直线。但是在物理结构上并不一定是连续的 ,线性表在物理上

    2024年01月18日
    浏览(35)
  • 【数据结构初阶】顺序表和链表(1)

    线性表(linear list) 是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使 用的数据结构,常见的线性表:顺序表、链表、栈、队列、字符串… 线性表在逻辑上是线性结构,也就说是连续的一条直线。但是在物理结构上并不一定是连续的,线性表在物理上

    2024年02月08日
    浏览(34)
  • 数据结构奇妙旅程之顺序表和链表

    ꒰˃͈꒵˂͈꒱ write in front ꒰˃͈꒵˂͈꒱ ʕ̯•͡˔•̯᷅ʔ大家好,我是xiaoxie.希望你看完之后,有不足之处请多多谅解,让我们一起共同进步૮₍❀ᴗ͈ . ᴗ͈ აxiaoxieʕ̯•͡˔•̯᷅ʔ—CSDN博客 本文由xiaoxieʕ̯•͡˔•̯᷅ʔ 原创 CSDN 如需转载还请通知˶⍤⃝˶ 个人主页:xiaoxieʕ̯

    2024年02月05日
    浏览(42)
  • 【手撕数据结构】(三)顺序表和链表

    🎗️线性表是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构,常见的线性表:顺序表、链表、栈、队列、字符串… 🎗️线性表在逻辑上是线性结构,也就说是一条连续的直线。但是在物理结构上并不一定是连续的,线性表在物理上存储

    2024年02月05日
    浏览(31)
  • 数据结构修炼第二篇:顺序表和链表

    第一章 时间复杂度和空间复杂度 第二章 顺序表,列表 第三章 栈和队列 第四章 二叉树 第五章 排序 作者:🎈乐言🎈 简介:🎈大一学生,目前在致力于c/c++/python,高数的学习,有问题尽管问我,关注后私聊! 持续更新专栏:《c进阶》,《数据结构修炼》 🚀 (优质好文持

    2024年02月02日
    浏览(36)
  • 数据结构----链表介绍、模拟实现链表、链表的使用

    ArrayList底层使用连续的空间,任意位置插入或删除元素时,需要将该位置后序元素整体往前或者往后搬移,故时间复杂度为O(N) 增容需要申请新空间,拷贝数据,释放旧空间。会有不小的消耗。 增容一般是呈2倍的增长,势必会有一定的空间浪费。例如当前容量为100,满了以后

    2024年02月21日
    浏览(35)
  • 初阶数据结构之---顺序表和链表(C语言)

    线性表: 线性表(linear list)是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构。线性表在逻辑上是线性结构,也就是说是连续的一条直线。但在物理上并不一定是连续的。线性表在物理上存储时,通常以 数组 和 链式结构 的形式存储。

    2024年02月22日
    浏览(42)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包