AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

Java数据结构线性表之链表（一）

2022-05-19 158
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 笔记

（1）链表

链表是一种物理存储单元上非连续、非顺序的存储结构，其物理结构不能只管的表示数据元素的逻辑顺序，数据元 素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列的结点（链表中的每一个元素称为结点）组成， 结点可以在运行时动态生成。

25.png


那我们如何使用链表呢？按照面向对象的思想，我们可以设计一个类，来描述结点这个事物，用一个属性描述这个 结点存储的元素，用来另外一个属性描述这个结点的下一个结点。


结点API设计：26.png

结点类实现：

/**
 * 节点类实现
 */
public static class Node<T>{
    // 存储元素
    public T item;
    // 指向下一个节点
    public Node<T> next;
    public Node(T item,Node<T> next){
        this.item = item;
        this.next = next;
    }
}

生成链表：

public static void main(String[] args) throws Exception { 
  //构建结点 
  Node<Integer> first = new Node<Integer>(11, null); 
  Node<Integer> second = new Node<Integer>(13, null); 
  Node<Integer> third = new Node<Integer>(12, null); 
  Node<Integer> fourth = new Node<Integer>(8, null); 
  Node<Integer> fifth = new Node<Integer>(9, null);
  //生成链表 
  first.next = second; 
  second.next = third; 
  third.next = fourth; 
  fourth.next = fifth;
}


（2）单向链表

单向链表是链表的一种，它由多个结点组成，每个结点都由一个数据域和一个指针域组成，数据域用来存储数据， 指针域用来指向其后继结点。链表的头结点的数据域不存储数据，指针域指向第一个真正存储数据的结点。

30.png

（2.1）单向链表API设计

31.png

（2.2）单向链表代码实现

package cn.itcast.algorithm.linear;
import java.util.Iterator;
/**
 * @author ：caizhengjie
 * @description：单向链表
 * @date ：2021/6/28 10:59 下午
 */
public class LinkList<T> implements Iterable<T>{
    /**
     * 记录头节点
     */
    private Node<T> head;
    /**
     * 记录链表的长度
     */
    private int N;
    /**
     * 节点类实现
     */
    public static class Node<T>{
        // 存储元素
        public T item;
        // 指向下一个节点
        public Node<T> next;
        public Node(T item,Node<T> next){
            this.item = item;
            this.next = next;
        }
    }
    /**
     * 构造方法
     */
    public LinkList() {
        // 初始化头节点
        this.head = new Node<>(null, null);
        // 初始化元素个数
        this.N = 0;
    }
    public LinkList(Node<T> head, int n) {
        this.head = head;
        N = n;
    }
    /**
     * 置空链表
     */
    public void clear(){
        // 让头节点为null
        head.next = null;
        // 让元素个数为0
        this.N = 0;
    }
    /**
     * 判断链表是否为空，是返回true，否则返回false
     */
    public boolean isEmpty(){
        // 只需判断元素个数是否为0，为0就是空，不为0就不是空
        return N == 0;
    }
    /**
     * 获取链表中元素的个数
     */
    public int length(){
        return N;
    }
    /**
     * 读取并返回链表中第i个元素
     */
    public T get(int i){
         // 通过循环从头节点开始往后找，依次找i次，就可以找到对应的元素
        Node<T> n = head.next;
        for (int index = 0;index < i;index++){
            n = n.next;
        }
        return n.item;
    }
    /**
     * 删除并返回链表中第i个元素的个数
     */
    public T remove(int i){
        // 找到i位置的前一个节点
        Node<T> pre = head;
        for (int index = 0;index <= i-1;index++){
            pre = pre.next;
        }
        // 找到i位置的节点
        Node<T> curr = pre.next;
        // 找到i位置的下一个节点
        Node<T> nextNode = curr.next;
        // 前一个节点指向下一个节点
        pre.next = nextNode;
        // 元素个数-1
        N--;
        return curr.item;
    }
    /**
     * 往链表中添加一个元素
     */
    public void insert(T t){
        // 找到当前最后一个节点
        Node<T> n = head;
        while (n.next != null){
            n = n.next;
        }
        // 创建新节点，保存元素t
       Node<T> newNode =  new Node<T>(t,null);
        // 让当前最后一个节点指向新节点
        n.next = newNode;
        // 元素的个数+1
        N++;
    }
    /**
     * 在链表的第i个元素之前插入一个值为t的数据元素
     */
    public void insert(int i,T t){
        // 找到i位置前一个节点
        Node<T> pre = head;
        for (int index = 0;index <= i-1;index++){
            pre = pre.next;
        }
        // 找到i位置的节点
        Node<T> curr = pre.next;
        // 创建新节点，并且新节点需要指向原来i位置的节点
        Node<T> nowNode = new Node<>(t,curr);
        // 原来i位置的前一个节点指向新节点即可
        pre.next = nowNode;
        // 元素个数+1
        N++;
    }
    /**
     * 返回链表中首次出现的指定的数据元素的位序号，若不存在，则 返回-1。
     */
    public int indexOf(T t){
        // 从头节点开始，依次找到每个节点，取出item，和t比较，如果相同，就找到了
        Node<T> n = head;
        for (int i = 0;n.next != null;i++){
            n = n.next;
            if (n.item.equals(t)){
                return i;
            }
        }
        return -1;
    }
    /**
     * 链表反转
     * 反转整个链表
     * @return
     */
    public void reverse(){
        // 判断当前链表是否为空链表，如果是空链表，则结束运行，如果不是，则调用重载的reverse方法完成反转
        if (isEmpty()){
            return;
        }
        reverse(head.next);
    }
    /**
     * 反转指定的节点curr，并把反转后的节点返回
     * @return
     */
    public Node<T> reverse(Node<T> curr){
        if (curr.next == null){
            head.next = curr;
            return curr;
        }
        // 递归的反转当前节点curr的下一个节点；返回值就是链表反转后当前节点的上一个节点
        Node<T> pre = reverse(curr.next);
        // 让返回的节点的下一个节点变为当前节点curr
        pre.next = curr;
        // 把当前节点的下一个节点变为null
        curr.next = null;
        return curr;
    }
    @Override
    public Iterator iterator() {
        return new LTterator();
    }
    private class LTterator implements Iterator{
        private Node<T> n;
        public LTterator() {
            this.n = head;
        }
        @Override
        public boolean hasNext() {
            return n.next != null;
        }
        @Override
        public Object next() {
            n = n.next;
            return n.item;
        }
    }
}

测试代码：

package cn.itcast.algorithm.test;
import cn.itcast.algorithm.linear.LinkList;
/**
 * @author ：caizhengjie
 * @description：TODO
 * @date ：2021/2/2 12:11 上午
 */
public class LinkListTest {
    public static void main(String[] args) {
        // 创建单向链表对象
        LinkList<String> l1 = new LinkList<>();
        // 测试插入
        l1.insert("alex");
        l1.insert("lili");
        l1.insert("jone");
        l1.insert(1,"jack");
        // 遍历
        for (String s : l1) {
            System.out.println(s);
        }
        // 测试获取
        String getResult = l1.get(1);
        System.out.println("获取索引1处的结果为：" + getResult);
        // 测试删除
        String removeResult = l1.remove(0);
        System.out.println("删除的元素为：" + removeResult);
        // 测试清空
        l1.clear();
        System.out.println("清空后线性表中的元素的个数为：" + l1.length());
    }
}

alex
jack
lili
jone
获取索引1处的结果为：jack
删除的元素为：alex
清空后线性表中的元素的个数为：0


（3）双向链表

双向链表也叫双向表，是链表的一种，它由多个结点组成，每个结点都由一个数据域和两个指针域组成，数据域用 来存储数据，其中一个指针域用来指向其后继结点，另一个指针域用来指向前驱结点。链表的头结点的数据域不存 储数据，指向前驱结点的指针域值为null，指向后继结点的指针域指向第一个真正存储数据的结点。

35.png

按照面向对象的思想，我们需要设计一个类，来描述结点这个事物。由于结点是属于链表的，所以我们把结点类作 为链表类的一个内部类来实现


（3.1）结点API设计

36.png



（3.2）双向链表API设计

37.png


（3.3）双向链表代码实现

package cn.itcast.algorithm.linear;
import java.util.Iterator;
/**
 * @author ：caizhengjie
 * @description：双向链表
 * @date ：2021/7/6 11:44 下午
 */
public class TowWayLinkList<T> implements Iterable<T>{
    /**
     * 记录头节点
     */
    private Node<T> head;
    /**
     * 记录尾节点
     */
    private Node<T> last;
    /**
     * 记录链表的长度
     */
    private int N;
    /**
     * 节点类实现
     */
    public static class Node<T>{
        // 存储元素
        public T item;
        // 指向下一个节点
        public Node<T> next;
        // 指向上一个节点
        public Node<T> pre;
        public Node(T item, Node<T> pre,Node<T> next){
            this.item = item;
            this.pre = pre;
            this.next = next;
        }
    }
    /**
     * 构造方法
     */
    public TowWayLinkList() {
        // 初始化头节点和尾节点
        this.head = new Node<>(null,null,null);
        // 初始化元素个数
        this.N = 0;
    }
    /**
     * 置空链表
     */
    public void clear(){
        // 让头节点和尾节点为null
        this.head.next = null;
        this.head.pre = null;
        this.head.item = null;
        this.last = null;
        // 让元素个数为0
        this.N = 0;
    }
    /**
     * 判断链表是否为空，是返回true，否则返回false
     */
    public boolean isEmpty(){
        // 只需判断元素个数是否为0，为0就是空，不为0就不是空
        return N == 0;
    }
    /**
     * 获取链表中元素的个数
     */
    public int length(){
        return N;
    }
    /**
     * 获取第一个元素
     */
    public T getFirst(){
        if (isEmpty()){
            return null;
        }
        return head.next.item;
    }
    /**
     * 获取最后一个元素
     */
    public T getLast(){
        if (isEmpty()){
            return null;
        }
        return last.item;
    }
    /**
     * 插入元素t
     */
    public void insert(T t){
        // 如果链表为空
        if (isEmpty()){
            // 创建新的节点
            Node<T> newNode = new Node<T>(t,head,null);
            // 让新节点称为尾节点
            last = newNode;
            // 让头节点指向尾节点
            head.next = last;
        }
        // 如果链表不为空
        else {
            // 当前尾节点
            Node<T> oldLast = last;
            // 创建新的节点
            Node<T> newNode = new Node<T>(t,oldLast,null);
            // 让当前的尾节点指向新节点
            oldLast.next = newNode;
            //  让新节点成为尾节点
            last = newNode;
        }
        // 元素个数+1
        N++;
    }
    /**
     * 在链表的第i个元素之前插入一个值为t的数据元素
     */
    public void insert(int i,T t){
        // 找到i位置的前一个节点
        Node<T> pre = head;
        for (int index = 0;index < i; index++){
            pre = pre.next;
        }
        // 找到i位置的节点
        Node<T> curr = pre.next;
        // 创建新节点
        Node<T> newNode = new Node<>(t,pre,curr);
        // 让i位置的前一个节点的下一个节点变为新节点
        pre.next = newNode;
        // 让i位置的前一个节点变为新节点
        curr.pre = newNode;
        // 元素个数+1
        N++;
    }
    /**
     * 读取并返回链表中第i个元素
     */
    public T get(int i){
        // 初始化
        Node<T> n = head.next;
        for (int index = 0;index < i;index++){
            n = n.next;
        }
        return n.item;
    }
    /**
     * 返回链表中首次出现的指定的数据元素的位序号，若不存在，则 返回-1。
     */
    public int indexOf(T t){
        // 初始化
        Node<T> n = head;
        for (int i = 0;n.next != null;i++){
            n = n.next;
            if (n.next.equals(t)){
                return i;
            }
        }
        return -1;
    }
    /**
     * 删除并返回链表中第i个元素的个数
     */
    public T remove(int i){
        // 找到i位置的前一个节点
        Node<T> pre = head;
        for (int index = 0;index < i; index++){
            pre = pre.next;
        }
        // 找到i位置的节点
        Node<T> curr = pre.next;
        // 找到i位置的下一个节点
        Node<T> nextNode = curr.next;
        // 让i位置的前一个节点的下一个节点变为i位置的下一个节点
        pre.next = nextNode;
        // 让i位置的下一个节点的上一个节点变为i位置的前一个节点
        nextNode.pre = pre;
        // 元素个数-1
        N--;
        return curr.item;
    }
    @Override
    public Iterator<T> iterator() {
        return new TTterator();
    }
    private class TTterator implements Iterator<T>{
        private Node<T> n;
        public TTterator(){
            this.n = head;
        }
        @Override
        public boolean hasNext() {
            return n.next != null;
        }
        @Override
        public T next() {
            n = n.next;
            return n.item;
        }
    }
}

测试代码：

package cn.itcast.algorithm.test;
import cn.itcast.algorithm.linear.TowWayLinkList;
/**
 * @author ：caizhengjie
 * @description：TODO
 * @date ：2021/2/2 12:11 上午
 */
public class TwoWayLinkListTest {
    public static void main(String[] args) {
        // 创建单向链表对象
        TowWayLinkList<String> l1 = new TowWayLinkList<>();
        // 测试插入
        l1.insert("alex");
        l1.insert("lili");
        l1.insert("jone");
        l1.insert(1,"jack");
        // 遍历
        for (String s : l1) {
            System.out.println(s);
        }
        System.out.println("---------------------------------------");
        System.out.println("第一个元素是：" + l1.getFirst());
        System.out.println("最后一个元素是：" + l1.getLast());
        System.out.println("---------------------------------------");
        // 测试获取
        String getResult = l1.get(1);
        System.out.println("获取索引1处的结果为：" + getResult);
        // 测试删除
        String removeResult = l1.remove(0);
        System.out.println("删除的元素为：" + removeResult);
        // 测试清空
        l1.clear();
        System.out.println("清空后线性表中的元素的个数为：" + l1.length());
    }
}

运行结果：

alex
jack
lili
jone
---------------------------------------
第一个元素是：alex
最后一个元素是：jone
---------------------------------------
获取索引1处的结果为：jack
删除的元素为：alex
清空后线性表中的元素的个数为：0
文章标签：
Java
API
存储
关键词：
Java数据结构
数据结构链表
数据结构线性表
数据结构java
Java线性表
游客wkxim4agoo6le
目录
相关文章
龙大吉
|
1月前
|
存储 Java
Java中的HashMap和TreeMap，通过具体示例展示了它们在处理复杂数据结构问题时的应用。
【10月更文挑战第19天】本文详细介绍了Java中的HashMap和TreeMap，通过具体示例展示了它们在处理复杂数据结构问题时的应用。HashMap以其高效的插入、查找和删除操作著称，而TreeMap则擅长于保持元素的自然排序或自定义排序，两者各具优势，适用于不同的开发场景。
龙大吉
44 1
东方睿赢
|
1月前
|
存储 Java
告别混乱！用Java Map优雅管理你的数据结构
【10月更文挑战第17天】在软件开发中，随着项目复杂度增加，数据结构的组织和管理至关重要。Java中的Map接口提供了一种优雅的解决方案，帮助我们高效、清晰地管理数据。本文通过在线购物平台的案例，展示了Map在商品管理、用户管理和订单管理中的具体应用，有效提升了代码质量和维护性。
东方睿赢
82 2
众所周知
|
16天前
|
缓存 算法 Java
本文聚焦于Java内存管理与调优，介绍Java内存模型、内存泄漏检测与预防、高效字符串拼接、数据结构优化及垃圾回收机制
在现代软件开发中，性能优化至关重要。本文聚焦于Java内存管理与调优，介绍Java内存模型、内存泄漏检测与预防、高效字符串拼接、数据结构优化及垃圾回收机制。通过调整垃圾回收器参数、优化堆大小与布局、使用对象池和缓存技术，开发者可显著提升应用性能和稳定性。
众所周知
36 6
肥猪肥猪-17824
|
22天前
|
存储 Java 索引
Java中的数据结构：ArrayList和LinkedList的比较
【10月更文挑战第28天】在Java编程世界中，数据结构是构建复杂程序的基石。本文将深入探讨两种常用的数据结构：ArrayList和LinkedList，通过直观的比喻和实例分析，揭示它们各自的优势与局限，帮助你在面对不同的编程挑战时做出明智的选择。
肥猪肥猪-17824
32 7
ephemerals__
|
24天前
|
存储 C语言
【数据结构】手把手教你单链表（c语言）（附源码）
本文介绍了单链表的基本概念、结构定义及其实现方法。单链表是一种内存地址不连续但逻辑顺序连续的数据结构，每个节点包含数据域和指针域。文章详细讲解了单链表的常见操作，如头插、尾插、头删、尾删、查找、指定位置插入和删除等，并提供了完整的C语言代码示例。通过学习单链表，可以更好地理解数据结构的底层逻辑，提高编程能力。
ephemerals__
50 4
肾透侧视攻城狮
|
25天前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之单双链表精题详解（9）【无论是王道考研人还是IKUN都能包会的；不然别给我家鸽鸽丢脸好嘛？】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子；这都学不会；能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛？！！！
肾透侧视攻城狮
22 2
肾透侧视攻城狮
|
25天前
|
存储 Web App开发 算法
2024重生之回溯数据结构与算法系列学习之单双链表【无论是王道考研人还是IKUN都能包会的；不然别给我家鸽鸽丢脸好嘛？】
数据结构之单双链表按位、值查找；[前后]插入；删除指定节点；求表长、静态链表等代码及具体思路详解步骤；举例说明、注意点及常见报错问题所对应的解决方法
肾透侧视攻城狮
30 2
那年春天
|
30天前
|
存储 算法 Java
Java 中常用的数据结构
【10月更文挑战第20天】这些数据结构在 Java 编程中都有着广泛的应用，掌握它们的特点和用法对于提高编程能力和解决实际问题非常重要。
那年春天
30 6
东方睿赢
|
1月前
|
存储 Java 开发者
Java中的Map接口提供了一种优雅的方式来管理数据结构，使代码更加清晰、高效
【10月更文挑战第19天】在软件开发中，随着项目复杂度的增加，数据结构的组织和管理变得至关重要。Java中的Map接口提供了一种优雅的方式来管理数据结构，使代码更加清晰、高效。本文通过在线购物平台的案例，展示了Map在商品管理、用户管理和订单管理中的具体应用，帮助开发者告别混乱，提升代码质量。
东方睿赢
29 1
ephemerals__
|
24天前
|
C语言
【数据结构】双向带头循环链表（c语言）（附源码）
本文介绍了双向带头循环链表的概念和实现。双向带头循环链表具有三个关键点：双向、带头和循环。与单链表相比，它的头插、尾插、头删、尾删等操作的时间复杂度均为O(1)，提高了运行效率。文章详细讲解了链表的结构定义、方法声明和实现，包括创建新节点、初始化、打印、判断是否为空、插入和删除节点等操作。最后提供了完整的代码示例。
ephemerals__
40 0

热门文章

最新文章

  • 1
    LeetCode 82 Remove Duplicates from Sorted List II（从已排序链表中移除重复元素）（Linked List）（*）
  • 2
    《C语言及程序设计》实践参考——改造链表
  • 3
    [剑指offer] 复杂链表的复制
  • 4
    [LeetCode] Rotate List 旋转链表
  • 5
    LeetCode 21：合并两个有序链表 Merge Two Sorted Lists
  • 6
    线性表概述及单链表的Java实现
  • 7
    从尾到头打印链表
  • 8
    IAM页，IAM链表，分配单元
  • 9
    【转】数据结构链表操作之双链表的基本操作
  • 10
    [LintCode] Swap Two Nodes in Linked List 交换链表中的两个结点
  • 1
    数据结构~缓存淘汰算法--LRU算法（Java的俩种实现方式，万字解析
    101
  • 2
    数据结构（五）----特殊矩阵的压缩存储
    260
  • 3
    数据结构（九）---并查集
    79
  • 4
    【数据结构与算法 11，高并发系统基础篇
    42
  • 5
    JavaScript 中实现常见数据结构：栈、队列与树
    78
  • 6
    数据结构链表详解(不仅顺序表可以，我链表也可以)
    43
  • 7
    顺序表的实现（迈入数据结构的大门）（2）
    41
  • 8
    顺序表的实现（迈入数据结构的大门）（1）
    32
  • 9
    每个程序员都必须掌握的8种数据结构，retrofit教程
    35
  • 10
    scala中常见数据结构的用法
    48

    • 相关课程

    更多
  • Java面试疑难点解析 - 面试技巧及语言基础
  • Java面试疑难点解析 - Java Web开发
  • Java面试疑难点解析 - 系统架构及项目设计
  • Java编程入门
  • Java面向对象编程
  • Java高级编程

    • 相关电子书

    更多
  • Spring Cloud Alibaba - 重新定义 Java Cloud-Native
  • The Reactive Cloud Native Arch
  • JAVA开发手册1.5.0

    • 相关实验场景

    更多
  • 阿里云平台上进行Java程序的编译与运行
  • 使用Java面向对象编写网络通信程序应用
  • 手动部署Java Web环境（Alibaba Cloud Linux 2）
  • 搭建Java Web开发环境（Anolis OS）
  • RocketMQ中使用Java客户端发送消息和消费的应用
  • 部署基于Dragonwell的Java运行环境
    • 下一篇
    无影云桌面