算法通关村第一关-链表青铜挑战笔记

欢迎来到 : 第一关青铜关

  1. java如何创建链表
  2. 链表怎么增删改查

我们先了解链表

单链表的概念

我们从简单的创建和增删改查开始.

链表的概念

线性表分为顺序表(数组组成)和链表(节点组成) . 

链表又分: 

  • 单向 双向
  • 有哨兵节点 无哨兵节点
  • 循环 不循环

链表是一种物理存储单元上非连续、非顺序的存储结构，单链表就像铁链一样,元素之间互相连接。链表由一系列的结点（链表中的每一个元素称为结点也叫节点）组成， 结点可以在运行时动态生成。

 在链表中每个节点都有数据域和指针域两部分:

  数据域用来存值 , 指针域用来存放地址(下一节点的地址) . 

 举个简单的例子{1,2,3}用链表存储:

思考一下

思考一下面两个图 , 是否满足单链表的要求 , 为什么 ?

图一:

图二:

解析:

第一图是满足单链表的要求 , 因为我们说链表要求环环相扣，核心是一个结点只能有一个后继，但不代表个结点只能有一个被指向。第一个图中，c1被a2和b3同时指向，这是没关系的。这就好比法律倡导一夫一妻，你只能爱一个人，但是可以都多个人爱你。
第二图就不满足要求了，因为c1有两个后继a5和b4.另外在做题的时候要注意比较的是值还是结点，有时可能两个结点的值相等，但并不是同一个结点，例如下图中有两个结点的值都是1，但并不是同一个结点。

链表的相关概念

节点和头节点

每个点都由值和指向下一个结点的地址组成的独立的单元，称为一个结点，有时也称为节点，含义都在链表中，是一样的。
对于单链表，如果知道了第一个元素，就可以通过遍历访问整个链表，因此第一个结点最重要一般称为头结点

虚拟节点(哨兵节点)

在做题以及在工程里经常会看到虚拟结点的概念，其实就是一个结点dummyNode，其next指针指向head，也就是dummyNode.next=head.
因此，如果我们在算法里使用了虚拟结点，则要注意如果要获得head结点，或者从方法(函数)里返回的时候，则应使用dummyNode.next.
另外注意，dummyNode的val不会被使用，初始化为0或者-1等都是可以的。既然值不会使用，那虚拟结点有啥用呢?简单来说，就是为了方便我们处理首部结点，否则我们需要在代码里单独处理首部结点的问题。在链表反转里，我们会看到该方式可以大大降低解题难度

创建链表

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

类名Node
构造方法Node(T t,Node next)：创建Node对象
成员变量T value:存储数据 Node next：指向下一个结点

 举例 : 存储值为int类型

/*** 节点类*/
public class Node {//值int value;//地址Node next;public Node(int value, Node next) {this.value = value;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;}

添加数据 :

    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;//添加数据Node<Integer> six= new Node<Integer>(22, null);six.next = second;first.next = six;}

删除数据: 

    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;//添加数据Node<Integer> six= new Node<Integer>(22, null);six.next = second;first.next = six;//删除数据first.next = second;}

修改数据:

修改值就很简单了找到节点直接修改就可以了:

 first.value = 100;

单向链表

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

单向链表设计 :

类名LinkList
构造方法LinkList()：创建LinkList对象
成员方法

1.public void clear()：空置线性表

2.publicboolean isEmpty()：判断线性表是否为空，是返回true，否返回false

3.public int length():获取线性表中元素的个数

4.public T get(int i):读取并返回线性表中的第i个元素的值

5.public void insert(T t)：往线性表中添加一个元素；

6.public void insert(int i,T t)：在线性表的第i个元素之前插入一个值为t的数据元素。

7.public T remove(int i):删除并返回线性表中第i个数据元素。

8.public int indexOf(T t):返回线性表中首次出现的指定的数据元素的位序号，若不存在，则

返回-11。

成员内部 类private class Node:结点类
成员变量

1.private Node head:记录首结点

2.private int N:记录链表的长度

/*** 单链表 (虚拟节点)* @param <T>*/
public class LinkList<T> {//记录头结点private Node head;//记录链表的长度private int N;public LinkList() {//初始化头结点head = new Node(null, null);N = 0;}//清空链表public void clear() {head.next = null;head.item = null;N = 0;}//获取链表的长度public int length() {return N;}//判断链表是否为空public boolean isEmpty() {return N == 0;}//获取指定位置i出的元素public T get(int i) {if (i < 0 || i >= N) {throw new RuntimeException("位置不合法！");}Node n = head.next;for (int index = 0; index < i; index++) {n = n.next;}return n.item;}//向链表中添加元素tpublic void insert(T t) {//找到最后一个节点Node n = head;while (n.next != null) {n = n.next;}Node newNode = new Node(t, null);n.next = newNode;//链表长度+1N++;}//向指定位置i处，添加元素tpublic void insert(int i, T t) {if (i < 0 || i >= N) {throw new RuntimeException("位置不合法！");}//寻找位置i之前的结点Node pre = head;for (int index = 0; index <= i - 1; index++) {pre = pre.next;}//位置i的结点Node curr = pre.next;Node newNode = new Node(t, curr);//让之前的结点指向新结点pre.next = newNode;//长度+1N++;}//删除指定位置i处的元素，并返回被删除的元素public T remove(int i) {if (i < 0 || i >= N) {throw new RuntimeException("位置不合法");}//寻找i之前的元素Node pre = head;for (int index = 0; index <= i - 1; index++) {pre = pre.next;}//当前i位置的结点Node curr = pre.next;//前一个结点指向下一个结点，删除当前结点pre.next = curr.next;//长度-1N--;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;}//结点类private class Node {//存储数据T item;//下一个结点Node next;public Node(T item, Node next) {this.item = item;this.next = next;}}
}

测试 : 

public class LinkTest {public static void main(String[] args) {LinkList<String> list = new LinkList<>();list.insert("aa");list.insert("bb");list.insert(1,"cc");list.insert("dd");for (int i = 0; i < list.length(); i++) {System.out.println(list.get(i));}list.remove(1);System.out.println(list.length());}
}

只要设计合理 , 都可以!

简化一点的版本 : 


/*** 单向链表*/
public class SinglyLinkedList {//哨兵(头指针)private Node head = null;//节点类private static class Node {int data;Node next;public Node(int data, Node next) {this.data = data;this.next = next;}}/*** 向链表头部插入** @param value*/public void addFirst(int value) {//1.链表为空的情况//head = new Node(value, null);//2.链表非空head = new Node(value, head);}/*** 遍历*/public void foreach(Consumer<Integer> consumer) {Node p = head;while (p != null) {consumer.accept(p.data);p = p.next;}}/*** 找到最后一个节点** @return*/private Node findLast() {if (head == null) {return null;}Node p = head;while (p.next != null) {p = p.next;}return p;}/*** 在链表尾部添加节点** @param value*/public void addLast(int value) {Node last = findLast();if (last == null) {addFirst(value);return;}last.next = new Node(value, null);}/*** 根据索引查找** @param index* @return*/private Node findNode(int index) {int i = 0;for (Node p = head; p != null; p = p.next, i++) {if (i == index) {return p;}}return null;}/*** 根据索引获取值** @param index* @return*/public int get(int index) {Node node = findNode(index);if (node == null) {throw new IllegalArgumentException(String.format("index is error"));}return node.data;}/*** 向索引位置插入数据** @param index* @param value*/public void insert(int index, int value) {if (index == 0) {addFirst(value);return;}Node node = findNode(index - 1);if (node == null) {throw new IllegalArgumentException(String.format("index is error"));}node.next = new Node(value, node.next);}/*** 删除头*/public void removeFirst() {if (head == null) {throw new IllegalArgumentException("Null");} else {head = head.next;}}/*** 按索引删除** @param index*/public void removeIndex(int index) {if (index == 0) {removeFirst();} else {Node node = findNode(index - 1);if (node == null) {throw new IllegalArgumentException("error");}if (node.next == null) {throw new IllegalArgumentException("error");}node.next = node.next.next;}}}

测试大家自己练习一下......

双向链表

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

 简单写了一下 , 伙伴们自己完善和修改吧 : 

/*** 双链表*/public class TwoLinkList {//哨兵节点private Node head = new Node(null, -1, null);//节点private static class Node {Node pre;int value;Node next;public Node(Node pre, int value, Node next) {this.pre = pre;this.value = value;this.next = next;}}/*** 查找尾节点** @return*/private Node findLastNode() {Node node = head;while (node.next != null ) {node = node.next;}return node;}/*** 尾插入** @param value*/public void insert(int value) {Node lastNode = findLastNode();lastNode.next = new Node(lastNode,value,null);}/*** 头插入** @param value*/public void addFist(int value) {//插入Node node = head;node.next=new Node(head,value,head.next);}/*** 遍历*/public void forEach() {if (head.next == null) {System.out.println("null!");}else {Node p = head.next;while (p != null) {System.out.println(p.value);p = p.next;}}}
}

测试 : 

public class TwoLinkListTest {public static void main(String[] args) {TwoLinkList twoLinkList = new TwoLinkList();twoLinkList.addFist(1);twoLinkList.addFist(2);twoLinkList.addFist(3);twoLinkList.addFist(4);twoLinkList.insert(4);twoLinkList.forEach();}
}

这关就到这里了, 朋友们下一关见!

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/159381.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

一文了解 Go fmt 标准库的常用占位符及其简单使用

一文了解 Go fmt 标准库的常用占位符及其简单使用

今天分享的内容是 Go fmt 标准库的常用占位符及其简单使用。如果本文对你有帮助&#xff0c;不妨点个赞&#xff0c;如果你是 Go 语言初学者&#xff0c;不妨点个关注&#xff0c;一起成长一起进步&#xff0c;如果本文有错误的地方&#xff0c;欢迎指出 占位符 通过占位符&a…
阅读更多...
【LeetCode热题100】--121.买卖股票的最佳时机

【LeetCode热题100】--121.买卖股票的最佳时机

121.买卖股票的最佳时机 class Solution {public int maxProfit(int[] prices) {int minprice Integer.MAX_VALUE;int maxprofit 0;for(int i 0;i<prices.length;i){if(prices[i] < minprice){minprice prices[i]; //找到最小值}else if(prices[i] - minprice > ma…
阅读更多...
Unity 3D基础——缓动效果

Unity 3D基础——缓动效果

1.在场景中新建两个 Cube 立方体&#xff0c;在 Scene 视图中将两个 Cude的位置错开。 2.新建 C# 脚本 MoveToTarget.cs&#xff08;写完记得保存&#xff09; using System.Collections; using System.Collections.Generic; using UnityEngine;public class MoveToTarget : M…
阅读更多...
[补题记录] Atcoder Beginner Contest 294（E）

[补题记录] Atcoder Beginner Contest 294（E）

URL&#xff1a;https://atcoder.jp/contests/abc294 目录 E Problem/题意 Thought/思路 Code/代码 E Problem/题意 我们将其当作一个铺路的过程。 给总长度 L&#xff0c;计划 1 有 N 步&#xff0c;计划 2 有 M 步&#xff0c;每一步给出&#xff08;v&#xff0c;l&a…
阅读更多...
stm32备份

stm32备份

存储器的分类&#xff1a; 存储器首先根据断电后存储的数据是否会丢失&#xff0c;可以分为易失存储器和非易失存储器&#xff0c;易失存储器主要应用于内存&#xff0c;非易失存储器主要用于外存。 易失存储器以RAM随机存储器为代表&#xff0c;随机的含义是存储器中的数据读取…
阅读更多...
ARM 10.12

ARM 10.12

设置按键中断&#xff0c;按键1按下&#xff0c;LED亮&#xff0c;再按一次&#xff0c;灭 按键2按下&#xff0c;蜂鸣器响。再按一次&#xff0c;不响 按键3按下&#xff0c;风扇转&#xff0c;再按一次&#xff0c;风扇停 src/key.c #include"key.h"//按键3的配…
阅读更多...
283 移动零

283 移动零

解题思路&#xff1a; \qquad 适用双指针&#xff0c;l&#xff1a;最左边‘0’元素坐标&#xff1b;r&#xff1a;l右边第一个非零元素坐标。 \qquad 最初的思路&#xff1a;将l和r初始化为0&#xff0c;遍历数组nums若任意一个指针到达数组末尾时停止。若当前nums[l] 0则移…
阅读更多...
系统文件IO、文件描述符fd、重定向、文件系统、动态库和静态库

系统文件IO、文件描述符fd、重定向、文件系统、动态库和静态库

目录 C文件接口系统文件I/O系统调用和库函数文件描述符0 & 1 & 2FILE和fd的关系文件描述符的分配规则 重定向重定向的本质输出重定向输入重定向追加重定向 dup2函数 FILE理解文件系统了解磁盘的物理结构逻辑抽象文件系统文件系统的图解和解析通过文件系统来理解ls -al通…
阅读更多...
1、验证1101序列（Moore）

1、验证1101序列（Moore）

题目要求&#xff1a; 用Moore型状态机验证1101序列。 题目描述&#xff1a; 用使用状态机验证1101序列&#xff0c;注意&#xff1a;允许重复子序列。如图 端口描述&#xff1a; module moore_1101(input clk,//时钟信号input clr,//reset复位信号&#xff0c;高电平有效in…
阅读更多...
微信小程序备案流程操作详解

微信小程序备案流程操作详解

1、2023年9月1号小程序开始必须备案了，各位小程序商城只需要按流程自主去微信小程序后台操作即可； 2、对未上架的微信小程序，从2023年9月1号开始需先备案才能上架； 3、对存量已上架的小程序，需在2024年3月31号前完成备案即可。逾期未完成备案，平台将按照备案相关规定于…
阅读更多...
hadoop组成

hadoop组成

在hadoop1.x时代,Hadoop中的MapReduce同时处理业务逻辑运算和资源调度,耦合性较大; 在hadoop2.x时代,新增了yarn,主要负责资源的调度,MapReduce仅负责运算; 在hadoop3.x时代,在组成上没有变化;
阅读更多...
ARM汇编学习录 2 - 编码分析

ARM汇编学习录 2 - 编码分析

本文记录笔者学习对应汇编指令相关编码知识 ARM32 首先阅读基础概念&#xff1a; ARM-instruction-set-encoding A32指令全部是32位且是4字节地址对齐. 位域如下 如何理解4字节地址对齐和指令长度&#xff1f; 0000139c <_start_main>:139c: e92d4800 …
阅读更多...
【Docker】Harbor私有仓库与管理

【Docker】Harbor私有仓库与管理

搭建本地私有仓库 #首先下载 registry 镜像 docker pull registry#在 daemon.json 文件中添加私有镜像仓库地址 vim /etc/docker/daemon.json {"insecure-registries": ["192.168.220.101:5000"], #添加&#xff0c;注意用逗号结尾"registry-mi…
阅读更多...
网络基础2（1）

网络基础2（1）

HTTP 1.应用层协议2.send和recv单独使用不安全3.URL4.urlencode和urldecode5.HTTP协议格式6.HTTP中的常见请求方法POST&&GET7.HTTP的状态码8.HTTP常见Header &#x1f31f;&#x1f31f;hello&#xff0c;各位读者大大们你们好呀&#x1f31f;&#x1f31f; &#x1f6…
阅读更多...
Git Commit Message规范

Git Commit Message规范

概述 Git commit message规范是一种良好的实践&#xff0c;可以帮助开发团队更好地理解和维护代码库的历史记录。它可以提高代码质量、可读性和可维护性。下面是一种常见的Git commit message规范&#xff0c;通常被称为"Conventional Commits"规范&#xff1a; 一…
阅读更多...
Zabbix 使用同一ODBC监控不同版本MySQL

Zabbix 使用同一ODBC监控不同版本MySQL

一、ODBC介绍 ODBC是Open Database Connect 即开发数据库互连的简称&#xff0c;它是一个用于访问数据库的统一界面标准。ODBC引入一个公共接口以解决不同数据库潜在的不一致性&#xff0c;从而很好的保证了基于数据库系统的应用程序的相对独立性。ODBC 概念由 Microsoft 开发&…
阅读更多...
C++指针解读（3）-- 指针变量作为函数参数

C++指针解读（3）-- 指针变量作为函数参数

函数执行是通过系统栈来实现的&#xff0c;系统栈分为若干个栈帧。栈帧就是函数运行的环境&#xff0c;每个函数在被调用时都会在系统栈区形成一个叫栈帧的结构。一次函数调用相关的数据保存在栈帧中&#xff0c;比如函数参数、函数的局部变量、函数执行完后的返回地址等数据。…
阅读更多...
嵌入式C语言自我修养《GNU C编译器扩展语法》学习笔记

嵌入式C语言自我修养《GNU C编译器扩展语法》学习笔记

目录 一、C语言标准和编译器 二、指定初始化 三、宏构造“利器”&#xff1a;语句表达式 四、typeof与container_of宏 五、零长度数组 六、属性声明&#xff1a;section 七、属性声明&#xff1a;aligned 一、C语言标准和编译器 C语言标准的发展过程&#xff1a; ●…
阅读更多...
机器学习笔记 - 使用3D卷积神经网络进行视频分类

机器学习笔记 - 使用3D卷积神经网络进行视频分类

1、导入相应的库 3D CNN 使用三维滤波器来执行卷积。内核能够在三个方向上滑动，而在 2D CNN 中它可以在二维上滑动。 首先安装并导入必要的库，用于处理ZIP文件内容的Remotezip 、用于使用进度条的tqdm 、用于处理视频文件的OpenCV 、用于执行更复杂的张量操作的einop…
阅读更多...
flink教程

flink教程

文章目录 来自于尚硅谷教程1. Flink概述1.1 特点1.2 与SparkStreaming对比 2. Flink部署2.1 集群角色2.2 部署模式2.3 Standalone运行模式2.3.1 本地会话模式部署2.3.2 应用模式 2.4 YARN运行模式2.4.1 会话模式部署2.4.2 应用模式部署 2.5 历史服务 3. 系统架构3.1 并行度3.2 …
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023