【数据结构】—— Java实现单链表
创始人
2024-05-09 07:28:17
0

Java实现单链表

  • 一、一链表的概念及结构
  • 二、头节点与头指针的异同
  • 三、代码实现

一、一链表的概念及结构

链表是一种物理存储结构上非连续存储结构,数据元素的逻辑顺序是通过链表中的引用链接次序实现的 。
在这里插入图片描述
注意:

  • 从上图可以看出,链式结构在逻辑上是连续的,但是在物理上不一定连续
  • 现实中结点一般是从堆上申请出来的。
  • 从堆上申请出来的空间,是按照一定策略来分配的,两次申请可能是连续,也可能是不连续的

二、头节点与头指针的异同

  • 头指针
    1.头指针是指链表指向第一个结点的指针,若链表有头节点,则是指向头节点的指针。
    2.头指针是具有标识作用,所以常用头指针冠以链表的命名
    3.无论链表是否为空,头指针均不为空。头指针是链表的必要元素
    若头指针为空,则链表不存在。
  • 头节点
    1.头结点是为了操作的统一和方便而设立的,放在第一元素的结点之前,其数据域一般无意义(也可存放链表的长度)
    2.有了头结点,对在第一元素结点前插入结点和删除第一节点,其操作与其他结点的操作就统一了
    3.头节点不一定是链表的必须元素

三、代码实现

里面包含常用的一些操作:
1.头插法
2.尾插法
3.遍历
4.元素的删除

public class LinkedList {//创建结点类,结点脱离类一般无意义,所以设定为静态类static class Node {//数据域int val;//引用后继指针地址Node next;public Node(int val) {this.val = val;}}//定义头节点Node head;public void addFirst(int val) {Node node = new Node(val);if (head == null) {head = node;return ;}node.next = head;head = node;}//尾插法public void addLast(int val) {Node node = new Node(val);if (head == null) {head = node;return ;}//此时要定义一个临时头节点,以便我们找到链表的尾部//并且我们是不希望改动链表的头节点,所以临时结点很重要Node temp = head;while (temp.next != null) {temp = temp.next;}temp.next = node;}//任意位置插入,第一个数据节点为0号下标public boolean addIndex(int index,int val) {if (head == null) {return false;}//判断所给的索引合法性if (index < 0 || index > size()) {throw new RuntimeException("the index is not illegal!");}//第一个位置插入的时候,此时就是头插法if (index == 0) {addFirst(val);return true;}//最后一个位置插入则为尾插法if (index == size()) {addLast(val);return true;}//最后考虑中间位置的插入即可//1.定义临时头结点,先走到待插入位置的前一个位置Node temp = head;while (index > 1) {temp = temp.next;index--;}//2.对元素进行插入Node node = new Node(val);node.next = temp.next;temp.next = node;return true;}//查找是否包含关键字key是否在单链表当中public boolean contains(int key) {if (head == null) {return false;}//只要在链表找到我们就返回false就行Node temp = head;while (temp != null) {if (temp.val == key) {return true;}temp = temp.next;}return false;}//删除第一次出现关键字为key的节点public void remove(int key) {if (head == null) {return ;}//只要存在我们才可以去删除if (!contains(key)) {throw new RuntimeException("the key is not exist !");}//如果是头节点的情况就直接删除if (head.val == key) {head  = head.next;return ;}//1.找到第一次出现的关键字key的前一个位置Node temp = head;while (temp != null && temp.next != null) {if (temp.next.val == key) {temp.next = temp.next.next;return;}temp = temp.next;}}//删除所有值为key的节点public void removeAllKey(int key) {if (head == null) {return ;}while (contains(key)) {remove(key);}}//得到单链表的长度public int size() {if (head == null) {return 0;}Node temp = head;int size = 0;while (temp != null) {size++;temp = temp.next;}return size;}public void display() {//遍历链表,这个是一定要掌握的,也不难if (head == null) {return ;}Node temp = head;while (temp != null) {System.out.print(temp.val + " ");temp = temp.next;}}//清空链表public void clear() {//这个我们枪打出头鸟就行head =null;}}

相关内容

热门资讯

监控摄像头接入GB28181平... 流程简介将监控摄像头的视频在网站和APP中直播,要解决的几个问题是:1&...
Windows10添加群晖磁盘... 在使用群晖NAS时,我们需要通过本地映射的方式把NAS映射成本地的一块磁盘使用。 通过...
protocol buffer... 目录 目录 什么是protocol buffer 1.protobuf 1.1安装  1.2使用...
在Word、WPS中插入AxM... 引言 我最近需要写一些文章,在排版时发现AxMath插入的公式竟然会导致行间距异常&#...
Fluent中创建监测点 1 概述某些仿真问题,需要创建监测点,用于获取空间定点的数据࿰...
educoder数据结构与算法...                                                   ...
MySQL下载和安装(Wind... 前言:刚换了一台电脑,里面所有东西都需要重新配置,习惯了所...
MFC文件操作  MFC提供了一个文件操作的基类CFile,这个类提供了一个没有缓存的二进制格式的磁盘...
有效的括号 一、题目 给定一个只包括 '(',')','{','}'...
【Ctfer训练计划】——(三... 作者名:Demo不是emo  主页面链接:主页传送门 创作初心ÿ...