专栏首页JavaJourney数据结构(一)- 链表

数据结构(一)- 链表

锲而舍之,朽木不折;锲而不舍,金石可镂。---荀子《劝学》

1认识链表结构

单向链表

单链表在内存中的表示:

单向链表

可以看到,一个链表的节点包含数据域和指向下一个节点的引用,链表最后一个节点指向null(空区域)。

我们可以根据这一定义,用Java语言表示一下单向链表的结构:

public class Node {
    public int value;
    public Node next;
    
    public Node(int value) {
        this.value = value;
    }
}

在链表的结构中,有数据域value,以及一个指向下一个节点的引用next。

TIP:这里的value还可以定义成泛型的。

双向链表

我们再来看一下双向链表的结构:

双向链表

双向链表中的节点有数值域,和指向它前一个节点的引用以及指向它后一个节点的引用,据此我们可以定义出双向链表的结构:

public class DoubleNode {
    public int value;
    public DoubleNode pre;
    public DoubleNode next;
    
    public DoubleNode(int value) {
        this.value = value;
    }
}

2加深对链表结构的理解

实现单向和双向链表的反转

说明:

对于一个链表如图所示

单链表原始结构

反转的意思是,将原来链表上的节点指针指向反转,原来的指向是:a -> b -> c -> d -> null,变成现在的指向:d -> c -> b -> a -> null,即反转后的结构如图所示:

这个题目不难,我们转换一下指针的指向就行了。

设计这样一个函数,函数的过程是调整链表各节点的指针指向,那么这个函数的要素有:

  • 返回值是链表的新的头结点,这样能保证函数执行完,原链表变成一个有新的头结点的链表
  • 需要传入一个链表,用头结点表示

解题技巧:定义两个Node引用辅助我们反转指针指向。

代码实现:

public static Node reverseNode(Node head) {
    Node pre = null;
    Node next = null;
    //最终让head指向null
    while (head != null) {
        next = head.next;
        head.next = pre;
        pre = head;
        head = next;
    }
    return pre;
}

我们来模拟一下这个函数的执行过程。

链表原始状态:

链表原始状态

方法开始执行,此时 head.next 不为空,所以,执行如下步骤:

  1. next = head.next:让next指向head(当前节点)的下一个节点,即b

next = head.next

  1. head.next = pre:让当前节点的下一个节点指向pre,即null

head.next = pre此时当前节点从原来指向b,改为指向null。

  1. pre = head:让pre指向当前节点
  2. head = next:让当前节点指向next,相当于移动head节点,直到将head节点移动到原来tail节点的位置

image-20210609221728786

第一次循环执行结束,此时 head 为b,不是null,所以继续循环,执行流程:

反转单链表第二次循环

此时 head 为c,不是null,所以继续循环,执行流程如下:

反转单链表第三次循环

同理,此时 head 为d,不是null,继续循环:

完成链表反转

这时就完成了单链表的反转步骤。

有了单链表反转的经验,我们很容易就能实现双向链表的反转,代码如下:

public DoubleNode reverseDoubleNode(DoubleNode head) {
    DoubleNode pre = null;
    DoubleNode next = null;
    while (head != null) {
        next = head.next;
        //操作(移动)当前节点
        head.next = pre;
        head.pre = next;
        
        pre = head;
        head = next;
    }
    return pre;
}

实现把链表中给定的值都删除

题如:给定一个单链表头节点head,以及一个整数,要求把链表中值为给定整数的节点都删除。

删除所有指定值的节点

实现思路:

要实现的函数需要给我传一个头节点以及给定的数值,头节点确定链表。func(Node head, int num)。

函数给不给返回值,返回值是什么?试想,针对链表 3 -> 5 -> 4 -> 3 -> 4 -> 5 ,加入要删除4,那么新链表就是 3 -> 5-> 3 -> 5,头节点仍然是原来的节点3;而如果要删除值为3的节点呢,删除后就是 5 -> 4 -> 4 -> 5 ,头节点变了。因此,我们要设计的这个函数需要返回新链表的头节点。

上述分析得知,需要返回新链表的头节点,因此也就是要返回第一个不是给定值的节点(因为给定值的节点都要被删除掉)。

//head移动到第一个不需要删除的位置:边界条件
while (head != null) {
    if (head.value != num) {
        break;
    }
    //head右移
    head = head.next;
}
//跳出循环之后,head的情况:
//1. head = null,这种情况是链表中的值全部是给定值,全删了
//2. head != null
// 中间操作
//最终返回head:第一个不是给定值的节点
return head;

head移动到第一个不需要删除的位置后,head若为null,表示所有节点都删除了,直接返回就可以了;若head不为null,借助两个辅助变量Node pre和cur,从head处开始往next走,遇到给定值就跳过。

Node pre = head;
Node cur = head;
while (cur != null) {
    if (cur.value == num) {
        pre.next = cur.next;
    } else {
        pre = cur;
    }
    cur = cur.next;
}

这一执行过程图解如下:

删除指定节点的过程

通过上述分析,写出完整实现代码:

public static Node remove (Node head, int num) {
    while (head != null) {
        if (head.value != num) {
            break;
        }
        head = head.next;
    }

    Node pre = head;
    Node cur = head;

    while (cur != null) {
        if (cur.value == num) {
            pre.next = cur.next;
        } else {
            pre = cur;
        }
        cur = cur.next;
    }
    return head;
}

3小结

今天主要针对链表这种数据结构进行了一些简单的分析,通过两个例子熟悉了链表的结构。

针对链表的操作,需要注意的就是指针指向以及边界问题,后续关于链表的算法还会遇到。

文章分享自微信公众号:
行百里er

本文参与 腾讯云自媒体分享计划 ,欢迎热爱写作的你一起参与!

作者:行百里er
原始发表时间:2021-06-10
如有侵权,请联系 cloudcommunity@tencent.com 删除。
登录 后参与评论
0 条评论

相关文章

  • 数据结构笔记(一):数组、链表

    数组(Array)是一种线性表数据结构。它用一组连续的内存空间,来存储一组具有相同类型的数据。

    free赖权华
  • [PHP] 链表数据结构(单链表)

    链表:是一个有序的列表,但是它在内存中是分散存储的,使用链表可以解决类似约瑟夫问题,排序问题,搜索问题,广义表

    大灰狼2
  • 数据结构——链表

    ruochen
  • 数据结构——链表

    用户7631864
  • 数据结构:链表

    链表(Linked List)是一种常见的基础数据结构,是一种线性表,但是并不会按线性的顺序存储数据,而是在每一个节点里存到下一个节点的指针(Pointer)。

    灰子学技术
  • 数据结构-链表

    链表结构五花八门,今天我重点给你介绍三种最常见的链表结构,它们分别是:单链表、双向链表和循环链表。我们首先来看最简单、最常用的单链表。

    花落花相惜
  • 数据结构-链表

    链表结构五花八门,今天我重点给你介绍三种最常见的链表结构,它们分别是:单链表、双向链表和循环链表。我们首先来看最简单、最常用的单链表。

    acc8226
  • 数据结构 - 链表

    顺序表的构建需要预先知道数据大小来申请连续的存储空间,而在进行扩充(插入、删除)时又需要进行数据的搬迁,所以使用起来并不是很灵活。

    忆想不到的晖
  • 数据结构-链表

    Head=(Node *)malloc(sizeof(Node)); //Head

    Wilbur-L
  • 数据结构:链表

    工程代码 Github: Data_Structures_C_Implemention -- Link List

    半纸渊
  • 数据结构-链表

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

    张小驰出没
  • 数据结构-链表

    链表是一种常见的重要的数据结构,他的特点是动态地进行存储分配。 1.链表有哪些优势? 举个栗子:如果事先不知道不知道要存放的数据的长度,就要把数组定的足...

    chaibubble
  • 【数据结构】链表[通俗易懂]

    发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/115596.html原文链接:https://javaforall.cn

    全栈程序员站长
  • 数据结构笔记一:数组和链表

    ​ 链表也是线性的顺序存储数据。只是在内存地址上不是连续的,每一个节点里存到下一个节点的指针(Pointer)

    Java头子
  • 数据结构|实现一个链表[4]

    如上面的代码,就是构建了链表在内存中的存储结构,int data是需要存储的int数据。struct JD *prior则是定义指向前面一个链表结构体的指针。s...

    rare0502
  • java链表数据结构是什么_java 链表数据结构

    首先,单链表相对于队列的优势在于存储地址不是连续的,这样的意义在于,操作其中的某一个位置的元素时不需要对之前的其他元素都进行内存操作,大大的为我们的计算机减压了...

    全栈程序员站长
  • 数据结构之链表

    数据结构是一种分析、存储、组织数据的方法与逻辑,它考虑了数据之间的特性与相互关系,简单地说,数据结构就是对数据与算法的研究。数据结构分为8类有:数组、...

    MeteoAI
  • 数据结构之链表

    在写这篇文章的时候我想到的第一个词就是,什么是链表? (不只这篇文章,好想其他的都是)

    袁新栋-jeff.yuan
  • 怒肝 JavaScript 数据结构 — 链表篇(一)

    前面几篇我们已经学过了数组,栈,队列与双端队列等数据结构,今天我们再遇见新朋友,一个动态的数据结构 —— 链表。

    杨成功

扫码关注腾讯云开发者

领取腾讯云代金券