开发者社区> 游客2j4akufbroa3m> 正文

《Java小子怒闯数据结构九重天》第五重天——链表

简介: 自古以来数据结构界就分为九重天,据说冲破这九重天之后就可以去进攻算法界最终修炼最后成佬,受万人敬仰,以下是第五重的内容。
+关注继续查看

前言


自古以来数据结构界就分为九重天,据说冲破这九重天之后就可以去进攻算法界最终修炼最后成佬,受万人敬仰。


但是这谈何容易,因为每一重天都有神兽把守,想要冲破每一重天都必须收服守护的神兽才行。


守护九重天的神兽分别是:数组、字符串、栈、队列、链表、树、散列表、堆、图。可见他们的战斗力也是逐层增强的。想只凭靠自身的能力拿下他们谈何容易。


不过大家不必惊慌,我这里有一本上古秘籍《Java小子怒闯数据结构九重天》,里面有每一重天神兽的攻略。只要修炼者仔细钻研里面的每一篇,对九重天了如指掌之后,冲破这九重天也是易如反掌的。


今天为大家带来第五重天的攻略!

image.png

1.🌀链表的基础知识

链表是一种线性表数据结构。它使用一组任意的存储单元(可以是连续的,也可以是不连续的),来存储一组具有相同类型的数据。

简单来说链表是实现线性表的链式存储结构的基础。


链表是一种通过指针串联在一起的线性结构,每一个节点是由两部分组成,一个是数据域一个是指针域(存放指向下一个节点的指针),最后一个节点的指针域指向null(空指针的意思)。


节点情况如下:


数据域 指针域

date next

上面的介绍都是单链表相关的,除了单链表我们还有双向链表,循环链表等。


双链表


双链表顾名思义就是比单链表高级了一点,一个双链表的结点在单链表的基础上又增加了一个指针,这个指针指向它的前一个结点


节点情况如下:


指针域 数据域 指针域

prior date next

循环链表


之前的链表都是条状的,循环链表是头尾相连了,就是将链表的尾部与头部连接起来。有因为条状链表有单链表与双链表之分,所以循环链表也有两种分别是:循环单链表与循环双链表


对于循环单链表我们一般设置尾指针这样操作效率会更高。


对于循环双链表我们头结点的prior结点指向最后一个节点,尾结点的next指针指向头结点,以形成循环双链表。


2.🌀Java实例化链表

想要实例化链表就得先创建一个链表的结构类,这个类代表的是每一个节点结构。


之前提到过每一个节点是由两部分组成,一个是数据域一个是指针域(存放指向下一个节点的指针),最后一个节点的指针域指向null(空指针的意思)。


所以链表节点结构定义为:


class ListNode {
    int val;       // 节点值
    ListNode next; // 后继节点引用
    ListNode(int x) { 
        val = x; 
    }
}



使用定义的这个链表结构我们可以自己构造一个链表如下:


// 实例化节点

ListNode n1 = new ListNode(4); // 节点 head
ListNode n2 = new ListNode(5);
ListNode n3 = new ListNode(1);


// 连接节点使之成为链表

n1.next = n2;
n2.next = n3;
n3.next = null;



我们构造出来的链表如下图:


image.png

3.🌀Java实现单链表

其中实现了Iterable接口,提供了遍历方式。


import java.util.Iterator;
/**
 * 链表的head是不可以动的
 * @param 
 */
public class LinkList implements Iterable{
    private Node head;//头结点,链表的head是不可以动的
    private int N;//结点个数
    //构造方法
    public LinkList() {
        this.head = new Node(null,null);
        N = 0;
    }
   
    //结点内部类
    private class Node{
        //存储数据
        T item;
        //下一个结点
        Node next;
        public Node(T item,Node next) {
            this.item = item;
            this.next = next;
        }
    }
   
    //清空链表
    public void clear(){
        head.item=null;
        head.next=null;// 头节点next为null就是空链表
        this.N=0;
    }
   
    //判断链表是否为空
    public boolean isEmpty(){
        return this.N==0;
    }
   
    //获取链表的长度
    public int length(){
        return this.N;
    }
   
    //读取链表第i位置的元素值并返回
    public T get(int i){
        //非法性检查
        if(i<0 || i > this.N){
            throw new RuntimeException("位置不合法");
        }
        // n也是指向头结点
        Node n = head;
        for(int index=0; index
            n = n.next;
        }
        return n.item;
    }
   
    //往链表中插入数据t
    public void insert(T t){
        // head不可以移动,不然就无法在找到链表
        // 定义一个临时的Node也指向head的指针就可以通过移动该指针就可以
        Node n = head;
        // 获取尾节点
        while(true){
            // 当刚好就一个节点时(头节点)
            if(n.next == null){
                break;
            }
            n = n.next;
        }
        //当为空表时,就可以插入
        Node node = new Node(t, null);
        n.next =node;
        this.N ++;
    }
    //在第i位置上插入数据t
    public void insert(T t,int i){
        // 非法性检查
        if(i < 0 || i > this.N){
            throw  new RuntimeException("插入位置非法");
        }
        Node pre = head;
        for(int index=0;index <= i-1; index++){
            pre = pre.next;
        }
        Node current = pre.next;
        //先链接后面结点
        Node newNode = new Node(t,null);
        pre.next = newNode;
        newNode.next = current;
        this.N++;
    }
   
    //移除并返回第i位置的元素值
    public  T remove(int i){
        // 非法性检查
        if(i < 0 || i >this.N){
            throw  new RuntimeException("删除位置有误");
        }
        Node n =head;
        for(int index=0;index <= i-1;index ++){
             n = n.next;
        }
        //要删除的节点
        Node curr = n.next;
        n.next = curr.next;
        this.N--;//结点个数减一
        return curr.item;
    }
   
    //查找元素t在链表中第一次出现的位置
    public int indexof(T t){
        Node n = head;
        for(int i = 0; n.next != null;i++){
            n =n.next;
            if(n.item.equals(t)){
                return i;
            }
        }
        return -1;
    }
    @Override
    public Iterator iterator() {
        return new Iterator() {
            Node n =head;
            @Override
            public boolean hasNext() {
                return n.next !=null;
            }
            @Override
            public Object next() {
                //下移一个指针
                n = n.next;
                return n.item;
            }
        };
    }
}


补充一点:链表的赋值给新的链表后,两个链表是会相会影响的,说白了就是把地址赋值给它了,他们操作是同一块内存的同一个对象。


Node n = head;


把head赋值给n,现在对n操作也是会影响head的。


4.🌀链表进阶练习

Leetcode 206. 反转链表

微信图片_20220523230415.png

题解:


我们可以申请两个指针,第一个指针叫 pre,最初是指向 null 的。

第二个指针 cur 指向 head,然后不断遍历 cur。

每次迭代到 cur,都将 cur 的 next 指向 pre,然后 pre 和 cur 前进一位。

都迭代完了(cur 变成 null 了),pre 就是最后一个节点了。


代码如下:

class Solution {
    public ListNode reverseList(ListNode head) {
  //申请节点,pre和 cur,pre指向null
  ListNode pre = null;
  ListNode cur = head;
  ListNode tmp = null;
  while(cur!=null) {
    //记录当前节点的下一个节点
    tmp = cur.next;
    //然后将当前节点指向pre
    cur.next = pre;
    //pre和cur节点都前进一位
    pre = cur;
    cur = tmp;
  }
  return pre;
    }
}


结语

恭喜你修炼到这里,你已经基本有了收服神兽链表的能力。神兽链表是我们到进攻算法界最重要的能力之一。大家不可懈怠。



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

相关文章
腾讯云服务器 设置ngxin + fastdfs +tomcat 开机自启动
在tomcat中新建一个可以启动的 .sh 脚本文件 /usr/local/tomcat7/bin/ export JAVA_HOME=/usr/local/java/jdk7 export PATH=$JAVA_HOME/bin/:$PATH export CLASSPATH=.
14852 0
阿里云服务器ECS登录用户名是什么?系统不同默认账号也不同
阿里云服务器Windows系统默认用户名administrator,Linux镜像服务器用户名root
15291 0
如何设置阿里云服务器安全组?阿里云安全组规则详细解说
阿里云安全组设置详细图文教程(收藏起来) 阿里云服务器安全组设置规则分享,阿里云服务器安全组如何放行端口设置教程。阿里云会要求客户设置安全组,如果不设置,阿里云会指定默认的安全组。那么,这个安全组是什么呢?顾名思义,就是为了服务器安全设置的。安全组其实就是一个虚拟的防火墙,可以让用户从端口、IP的维度来筛选对应服务器的访问者,从而形成一个云上的安全域。
18581 0
阿里云服务器如何登录?阿里云服务器的三种登录方法
购买阿里云ECS云服务器后如何登录?场景不同,云吞铺子总结大概有三种登录方式: 登录到ECS云服务器控制台 在ECS云服务器控制台用户可以更改密码、更换系统盘、创建快照、配置安全组等操作如何登录ECS云服务器控制台? 1、先登录到阿里云ECS服务器控制台 2、点击顶部的“控制台” 3、通过左侧栏,切换到“云服务器ECS”即可,如下图所示 通过ECS控制台的远程连接来登录到云服务器 阿里云ECS云服务器自带远程连接功能,使用该功能可以登录到云服务器,简单且方便,如下图:点击“远程连接”,第一次连接会自动生成6位数字密码,输入密码即可登录到云服务器上。
36339 0
阿里云服务器端口号设置
阿里云服务器初级使用者可能面临的问题之一. 使用tomcat或者其他服务器软件设置端口号后,比如 一些不是默认的, mysql的 3306, mssql的1433,有时候打不开网页, 原因是没有在ecs安全组去设置这个端口号. 解决: 点击ecs下网络和安全下的安全组 在弹出的安全组中,如果没有就新建安全组,然后点击配置规则 最后如上图点击添加...或快速创建.   have fun!  将编程看作是一门艺术,而不单单是个技术。
19980 0
阿里云服务器如何登录?阿里云服务器的三种登录方法
购买阿里云ECS云服务器后如何登录?场景不同,阿里云优惠总结大概有三种登录方式: 登录到ECS云服务器控制台 在ECS云服务器控制台用户可以更改密码、更换系.
27727 0
阿里云ECS云服务器初始化设置教程方法
阿里云ECS云服务器初始化是指将云服务器系统恢复到最初状态的过程,阿里云的服务器初始化是通过更换系统盘来实现的,是免费的,阿里云百科网分享服务器初始化教程: 服务器初始化教程方法 本文的服务器初始化是指将ECS云服务器系统恢复到最初状态,服务器中的数据也会被清空,所以初始化之前一定要先备份好。
16589 0
72
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
JS零基础入门教程(上册)
立即下载
性能优化方法论
立即下载
手把手学习日志服务SLS,云启实验室实战指南
立即下载