个人中心
gpt4 book ai didi

一篇文章带你玩转JAVA单链表

转载 作者：qq735679552 更新时间：2022-09-27 22:32:09 27 4
gpt4 key购买 nike

CFSDN坚持开源创造价值，我们致力于搭建一个资源共享平台，让每一个IT人在这里找到属于你的精彩世界.

这篇CFSDN的博客文章一篇文章带你玩转JAVA单链表由作者收集整理，如果你对这篇文章有兴趣，记得点赞哟.

  。

1、链表 

  。

1. 概念

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

上章介绍到顺序表适合用作查询和修改，而不适合用作插入和删除。并且它增容时容易造成空间浪费。而链表则具有以下的特点 。

适合用作插入和删除随用随取，避免了空间的浪费不适合用作查询和修改  。

  。

2. 结构

链表其实可以想象成一条被打了一些结的绳子 。

一篇文章带你玩转JAVA单链表

而实际上，链表就是由一个个节点构成的，只不过每个节点一般有两个域 。

数值域 data： 里面存储数据 。

next 域： 里面存储的是下一个节点的地址（是引用变量） 。

一篇文章带你玩转JAVA单链表

其中 。

尾节点： 当这个节点的 next 域为 null 时，该节点就是尾节点 。

头节点： 整个链表的第一个节点就是头节点 。

实际中的链表结构非常多，通过以下的情况的组合可以有8种链表的结构（比如带头单向循环链表就是一种） 。

单向、双向 。

带头节点、不带头 。

节点循环、非循环 。

而上图所示，就是一个单向不带头非循环链表.

一篇文章带你玩转JAVA单链表

可能有人会疑问，上述图片中不是存在头节点吗？那为啥它又是一个不带头节点的链表呢？我将上述图片实例稍稍改一下就是带头节点的了 。

一篇文章带你玩转JAVA单链表

我在原有的头节点前面又多了一个节点，并且这个节点的数值域里面的数据可有可无，因为对其没有影响。而这里面的头节点只是一个标志，标识这个节点是该链表的头 。

那带头节点的和不带头结点的链表有啥差别呢?

不带头： 这个链表的头节点可能发生改 。

变带头： 这个链表的头节点不会发生改变 。

那循环链表又是啥样的呢？我们可以将上述单向不带头非循环链表稍微修改一下 。

一篇文章带你玩转JAVA单链表

即将尾节点的 next 域存储了头节点的地址 。

我们知道一个节点一般就两个域，但如果是双向链表，则就有三个域了 。

数值域 data： 里面存储数据 。

next 域： 里面存储的是下一个节点的地址（是引用变量） 。

prev 域： 里面存储的是上一个节点的地址（是引用变量） 。

我们画一个不带头双向非循环链表就是这样的 。

一篇文章带你玩转JAVA单链表

接下来我将主要介绍单向不带头非循环链表和双向不带头非循环链表，这两种链表也是经常出现在面试题中的 。

  。

2、单向不带头非循环链表 

  。

1. 概念及结构

上述通过图解，大家应该对单向不带头非循环链表应该有了了解。那么代码中该怎么实现呢?

我们知道，链表应该可以看作一个类，而节点本身其实也可以抽象的看作成一个类 。

首先对于节点类，代码可以写出这样 。

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

先定义了数值域，再定义了 next 域（由于 next 存储的是下一个节点的地址，故写出上述那样）。而我们初始时可以知道 val，所以可以写个构造函数对 val 进行初始化，而该节点的 next 域初始时是不可能知道的，所以不对 next 做初始化 。

如果创造一个 Node 对象就可以写出 。

Node node = new Node(10),

即头节点的数值域为10.

再定义链表类，代码可以写成这样 。

public class MyLinkedList {    public Node head;}

我们定义了一个头节点，这是我们很容易发现的，就比如我要对该链表进行头插，则该链表的头节点一直都在改变。所以写上述的代码就是为了标识单链表的头节点.

  。

2. 链表的实现

接下来我们来实现单向不带头非循环链表的一些操作 。

打印链表 。

public void display(){    Node cur =this.head;    while(cur!=null){        System.out.print(cur.val + " ");        cur=cur.next;    }    System.out.println();}

求链表的长度 。

public int size(){    Node cur=this.head;    int count=0;    while(cur!=null){        count++;        cur=cur.next;    }    return count;}

查找值 key 是否在单链表中 。

public boolean contains(int key){    Node cur=this.head;    while(cur!=null){        if(key==cur.val){            return true;        }        cur=cur.next;    }    return false;}

清除单链表 。

public void clear(){    this.head.val=0;    this.head.next=null;}

头插法 。

public void addFirst(int data){    Node node=new Node(data);    if(head==null){        this.head=node;    }else {        node.next = this.head;        this.head = node;    }}

尾插法 。

public void addLast(int data){    Node node = new Node(data);    if(this.head==null){        this.head=node;    }else {        Node cur = this.head;        while (cur.next != null) {            cur = cur.next;        }        cur.next = node;    }}

通过下标找到前驱节点（第一个节点下标为0） 。

public Node searchPrev(int index){    Node cur = this.head;    int count=0;    while(count!=index-1){        cur=cur.next;        count++;    }    return cur;}

任意位置插入 。

public void addIndex(int index, int data){    if(index<0 || index>size()){        throw new RuntimeException("index 不合法");    }    if(index==0){        addFirst(data);        return;    }    if(index==size()) {        addLast(data);        return;    }    Node node =new Node(data);    Node cur =searchPrev(index);    node.next=cur.next;    cur.next=node;}

通过值 key 找到前驱节点（第一个节点下标为0） 。

public Node searchPrevNode(int key){    Node cur = this.head;    while(cur.next!=null){        if(cur.next.val==key) {            return cur;        }        cur=cur.next;    }    return null;}

删除第一次出现的值为 key 的节点 。

public void remove(int key){    if(this.head==null){        return;    }    if(key==this.head.val){        this.head=this.head.next;        return;    }    Node node = searchPrevNode(key);    if(node==null){        System.out.println("链表中无要删除的元素");    }else {        node.next = node.next.next;    }}

删除所有出现的值为 key 的节点 。

public void removeAllKey(int key){    if(this.head==null){        return;    }    Node prev=this.head;    Node cur=this.head.next;    while(cur!=null){        if(cur.val==key){            cur=cur.next;            prev.next=cur;        }else{            prev=cur;            cur=cur.next;        }    }    if(this.head.val==key){        this.head=this.head.next;    }}

呼，写的我人傻了 。

一篇文章带你玩转JAVA单链表

你以为结束了吗？NO！下面还有一大波链表面试题等着我和你，冲吧，牛牛！ 。

  。

3、链表面试题

删除链表中等于给定值 val 的所有节点 OJ 链接 。

反转一个单链表 OJ 链接 。

给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点 OJ 链接 。

输入一个链表，输出该链表中倒数第k个结点 OJ 链接 。

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的 OJ 链接 。

编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前 OJ 链接 。

在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针 OJ 链接 。

链表的回文结构 OJ 链接 。

输入两个链表，找出它们的第一个公共结点 OJ 链接 。

给定一个链表，判断链表中是否有环 OJ 链接 。

给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null OJ 链接 。

如果你已经可以轻松应对上述题目了，可以继续去下面的链接中做题 Leetcode OJ 链接 和 牛客 OJ 链接 。

  。

4、总结

今天简单了解了链表，以及对单向不带头非循环链表做了一些基操的实现。下章将包含个人的上述前11道 OJ 题的题解，以及了解双向不带头非循环链表 。

本篇文章就到这里了，希望能够给你带来帮助，也希望您能够多多关注我的更多内容！ 。

原文链接：https://blog.csdn.net/weixin_51367845/article/details/120019451 。

最后此篇关于一篇文章带你玩转JAVA单链表的文章就讲到这里了,如果你想了解更多关于一篇文章带你玩转JAVA单链表的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。

27 4 0
文章推荐： 详解mysql三值逻辑与NULL
文章推荐： Golang 五种原子性操作的用法详解
文章推荐： MySQL时间盲注的五种延时方法实现
文章推荐： Go Fiber 框架系列之一: 和 Express 对比学习
qq735679552
个人简介

我是一名优秀的程序员,十分优秀！

滴滴打车优惠券免费领取
滴滴打车优惠券
全站热门文章
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com