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

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

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

（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
存储
关键词：
数据结构链表
数据结构线性表
线性表链表
数据结构线性表链表
链表数据结构
游客wkxim4agoo6le
目录
相关文章
老秦包你会
|
14天前
|
存储
数据结构第二课 -----线性表之单向链表
数据结构第二课 -----线性表之单向链表
老秦包你会
21 0
Bigcrab__
|
5天前
|
存储 算法 Java
数据结构与算法 数组和链表
数据结构与算法 数组和链表
Bigcrab__
11 0
菜菜的后端私房菜
|
5天前
|
存储 Java
深入浅出数据结构之链表
深入浅出数据结构之链表
菜菜的后端私房菜
6 0
天玑y
|
5天前
|
C++
数据结构（双链表
数据结构（双链表
天玑y
8 1
小蜗牛~向前冲
|
8天前
|
存储 缓存
[数据结构]~双向+循环链表从(0~1）
[数据结构]~双向+循环链表从(0~1）
小蜗牛~向前冲
15 2
老秦包你会
|
14天前
|
存储
数据结构第五课 -----线性表之树
数据结构第五课 -----线性表之树
老秦包你会
14 0
老秦包你会
|
14天前
数据结构第四课 -----线性表之队列
数据结构第四课 -----线性表之队列
老秦包你会
16 0
老秦包你会
|
14天前
数据结构第四课 -----线性表之栈
数据结构第四课 -----线性表之栈
老秦包你会
17 0
老秦包你会
|
14天前
|
存储
数据结构第三课 -----线性表之双向链表
数据结构第三课 -----线性表之双向链表
老秦包你会
12 0
老秦包你会
|
14天前
|
存储
数据结构第二课 -----线性表之顺序表
数据结构第二课 -----线性表之顺序表
老秦包你会
21 1

热门文章

最新文章

  • 1
    【数据结构算法（二）】链表总结
  • 2
    【堆】数据结构堆的实现（万字详解）
  • 3
    【排序算法】数据结构排序详解
  • 4
    【链式二叉树】数据结构链式二叉树的（万字详解）
  • 5
    数据结构——二叉树的链式结构
  • 6
    数据结构--动态顺序表
  • 7
    数据结构——排序算法之快速排序
  • 8
    【数据结构】排序之插入排序和选择排序
  • 9
    【树和二叉树】数据结构二叉树和树的概念认识
  • 10
    数据结构--算法的时间复杂度和空间复杂度
  • 1
    Java 文件处理完全指南：创建、读取、写入和删除文件详细解析
    289
  • 2
    Java的语法基础
    20
  • 3
    Java的面向对象设计
    20
  • 4
    java的类加载过程
    15
  • 5
    java的常见算法
    18
  • 6
    Java的IO技术和NIO技术
    25
  • 7
    JAVA字符串与其他类型数据的转换
    40
  • 8
    JAVA字符串的基本操作
    26
  • 9
    JAVA一维数组
    31
  • 10
    JAVA跳转控制语句
    24

    • 相关课程

    更多
  • 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面向对象编写网络通信程序应用
  • Elasticsearch Java API Client 开发
  • 手动部署Java Web环境（Alibaba Cloud Linux 2）
  • 搭建Java Web开发环境（Anolis OS）
  • RocketMQ中使用Java客户端发送消息和消费的应用
    • 下一篇
    部署LAMP环境（Alibaba Cloud Linux 3）