栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

简单使用java创建出单向链表类

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

简单使用java创建出单向链表类

1、链表的概述

虽然顺序表的查询快,时间复杂度为O(1),但是增删的效率是比较低的,因为每一次增删操作都伴随着大量的数据元素移动。

链表是一种物理存储单元上非连续,非顺序的存储结构,其物理结构不能只管的表示数据元素的逻辑顺序,数据元素的逻辑顺序是通过链表中的指针连接次序实现的。

链表由一系列的节点(链表中的每一个元素称为节点)组成,节点可以在运行时动态生成。

线性表的数据存储可以是顺序存储也可以是链式存储,按照存储方式的不同,可以把线性表分为顺序表和链表。

2、单向链表

单向链表是链表的一种,它由多个节点组成,每个节点都由一个数据与和一个指针域组成;数据域存储数据,指针域用来指向其他后继节点。

链表的头结点的数据域不存储数据,指针域指向第一个真正存储数据的节点

如下图所示:

3、API设计
类名LinkList
构造方法LinkList():创建LinkList对象
成员方法1. public void clear():空置线性表
2. public boolean isEmpty():判断线性表是否为空,是返回true,否则反之
3. public int length():返回线性表中的元素个数
4. public T get(int i):读取并返回线性表中的第i个元素
5. public void insert(T t):往线性表中添加一个元素
6. public void insert(int i,T t):在线性表的第i个元素之前插入一个值为t的数据元素
7. public T remove(int i):删除并返回线性表中第i个数据元素
8. public int indexOf(T t):返回线性表中首次出现的指定的数据元素的位序号,若不存在,则返回-1
成员内部类private class Node:节点类
成员变量1. private Node head:记录首节点
2. private int N:记录链表的长度
4、代码实现 4.1 创建成员变量与节点类

成员变量和节点类需要先进行创建,因为这两个东西是在链表中不可或缺的。

成员变量直接声明即可。

private Node head;// 记录头节点
private int N;// 元素个数
4.1.1 节点类

节点类可以用private修饰。毕竟只是在内部使用。

每个节点都需要有一个存储内容的变量,所以这里声明一个T泛型的item变量。
而每个节点都需要有指针,因为每个节点所指向的就是节点,所以这里声明一个Node节点类的next变量。
最后给这个类配置好构造方法即可。

private class Node {
    public T item;// 存储元素
    public Node next;// 指向下一个节点

    public Node(T item, Node next) {
        this.item = item;
        this.next = next;
    }
}
4.2 初始化构造和基础信息获取 4.2.1 构造方法

我们的链表,需要在声明时就进行头结点和元素个数的初始化,意味着这需要一个构造方法

这里直接用this指向head和N进行初始化,节点为一个null节点,毕竟存储的内容不知道,也不知道指向谁。N为0

// 实现构造,初始化头结点和元素个数
public LinkListDemo(){
    this.head = new Node(null,null);
    this.N = 0;
}
4.2.2 清除链表

我们如何清除链表呢?我们知道链表由头节点开始,那么将头结点的指针清空不就清空链表了?

说着就做,将head头结点的指针改为null值,让它的指向为null。
同时,N记录元素个数的变量也改为0,都没内容了个数也要清空。

// 清除链表
public void clear(){
    head.next = null;
    this.N = 0;
}
4.2.3 获得元素个数

获取链表中的元素个数,直接返回N就好,因为N就是记录着链表中的元素个数的变量。

// 获得链表的元素总个数
public int length(){
    return N;
}
4.2.4 判断链表是否为空

如何判断链表为空?我们只需要判断N变量是否为0就好了,如果链表元素个数为0,那么就会自动返回true

// 判断元素链表是否为空
public boolean isEmpty(){
    return N==0;
}
4.3 获得元素或元素所在位置 4.3.1 根据索引获得元素

方法中,由于传进来的是int类型也就是索引,那么我们可以根据该索引使用for循环进行遍历链表,但链表的遍历如何遍历?我们知道链表由头节点开始,那么我们也可以从头结点开始对下一个元素进行获取,当循环结束时,那么元素就找到了。

这里需要用辅助节点来记录循环得到的节点。
经过循环,o.next 赋值 o,最后返回o的内容即可。

// 根据索引得到元素
public T get(int i){
    // 通过循环,从头节点开始往后找,依次找i次,既可找到对应的元素
    Node o = head.next;
    for (int index = 0;index
        o = o.next;
    }
    return (T) o.item;
}
4.3.2 获得元素首次出现在链表中的位置

与查找元素类似,但在循环中要操作的步骤变多了,我们需要判断方法传入的内容与当前遍历元素的内容是否一致,如果一致那么元素就找到了。找到元素返回当前遍历的索引即可。

这里与查找元素不一样的是,在声明辅助节点变量时,不需要head.next,因为我们的索引是从0开始的,当然如果加上head.next把索引改为1即可。
在for循环内部判断内容元素是否一致,一致则返回当前循环的索引值

// 获得元素首次出现在链表中的位置
public int indexOf(T t){
    // 从头节点开始,依次找到每一个节点和t比较
    Node n = head;
    for (int index = 0; n.next != null; index++) {
        n = n.next;
        if (n.item.equals(t)){
            return index;
        }
    }
    return -1;
}
4.4 插入元素 4.4.1 向链表中插入一个元素

如何插入一个元素呢?1. 我们需要找到当前链表的最后一个元素 2. 创建新节点 3. 让最后一个节点指向我们创建好的新节点即可 4. 元素个数+1

由于没有索引,所以用while循环从头开始遍历链表。当节点的下一个节点为空就停止遍历。
创建新节点,内容就是方法中传入的内容,指针为null毕竟是添加到链表末尾的元素。
老末尾元素的指针指向新节点进行赋值。
元素个数N++即可。

// 向链表中插入数据
public void insert(T t){
    // 找到当前最后一个节点
    Node n = head;
    while (n.next != null){
        n = n.next;
    }
    // 创建新节点,保存元素t
    Node newNode = new Node(t, null);
    // 让当前最后一个节点指向新节点
    n.next = newNode;
    // 元素的个数+1
    N++;
}
4.4.2 向表中指定元素前插入一个元素

由于方法中传入了i索引,所以我们可以根据i索引获得到对应的元素,步骤与在末尾插入元素是一致的,同时查找get方法的遍历也是一致的,所以这里直接套用。

// 向表中的第i处元素前插入t元素
public void insert(int i,T t){
    // 找到i位置的前一个节点
    Node pre = head;
    for (int index = 0; index <= i-1; index++) {
        pre = pre.next;
    }
    // 找到i位置的节点
    Node curr = pre.next;
    // 创建新节点,并且新节点要指向原来i位置的节点
    Node tNode = new Node(t, curr);
    // 原来i位置的前一个节点指向新节点
    pre.next = tNode;
    // 元素的个数+1
    N++;
}
4.5 删除指定索引处的元素

删除有以下步骤:
1.找到索引处的前一个元素
2.找到索引处的元素
3.找到元素的下一个元素
4.索引处的元素前一个元素指向元素的下一个元素
5.元素个数-1
6.返回元素

第一步的我们需要对链表进行遍历,与get方法的遍历不一样,由于获得的是前一个元素,所以辅助节点直接等于head头结点即可然后由它开始遍历。
第二步,找到前一个元素了直接.next就拿到了索引处的元素
第三步,找到索引处的元素直接.next就拿到了索引处元素的下一个元素
第四步,前一个元素指向下一个元素即可。
第五步,元素个数N–即可。
第六步,返回索引处的元素内容

// 删除指定i处的元素
public T remove(int i){
    // 找到i位置的前一个节点
    Node pre = head;
    for (int index = 0; index <= i-1; index++) {
        pre = pre.next;
    }
    // 找到i位置的节点
    Node curr = pre.next;
    // 找到i位置的下一个节点
    Node curr2 = curr.next;
    // 前一个节点指向下一个节点
    pre.next = curr2;
    // 元素个数-1
    N--;
    return (T) curr.item;
}
5.总结:

每一次查询,都需要从链表的头部开始,依次向后查找,随着数据元素N的增多,比较的元素越多,时间复杂度为:O(n)
每一次插入,需要先找到位置的前一个元素,然后完成插入操作,随着数据元素N的增多,查找的元素越多,时间复杂度为:O(n)
每一次移除,需要先找到位置的前一个元素,然后完成移除操作,随着数据元素N的增多,查找的元素越多,时间复杂度为:O(n)

相比较顺序表,链表的插入和移除的时间复杂度虽然一样,但是仍有很大的优势,因为链表的物理地址是不连续的,它不需要预先指定存储空间大小,或者在存储过程中设计到扩容等操作,同时它并没有涉及到元素的交换。
链表的查询操作性能会比较低,因此,如果我们的程序中查询操作比较多,建议使用顺序表;如果增删操作比较多,建议使用链表

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/959066.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号