IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> Java实现单链表的基本操作 -> 正文阅读

[数据结构与算法]Java实现单链表的基本操作

链表的结构

线性结构的链式存储是用若干地址分散的存储单元存储数据元素,逻辑上相邻的两个数据元素在物理位置上并不一定相邻,必须采用附加信息来表示数据元素之间的顺序关系。因此存储一个数据元素的数据单元至少包含两部分------数据域和地址域
在这里插入图片描述
上述的结构通常称为结点
一个节点表示一个数据元素,通常节点当中的地址会把数据结点连接起来,节点当中的连接关系体现了线性表当中数据元素间的顺序关系,采用这种关系的称为线性链表
在这里插入图片描述
从上图当中,head是线性链表当中的第一个节点,但是这个节点在数据域当中并没有存储数据,这里之所以写这个的目的是我们能够通过头指针去遍历我们整个链表。
最后一个节点的地址域为空,表示其后不再有节点。每个结点只有一个地址域的链表称为单链表

定义链表节点

public class ListNode {
   int val;   //定义当前节点的值
   ListNode next;  //定义下一个节点的值
    //定义一个构造函数
   public ListNode(int value){
       this.val = value;
   }

    @Override
    public String toString() {
        return "ListNode{" +
                "val=" + val +
                ", next=" + next +
                '}';
    }
}

建立单链表

public class Test {
    public static void main(String[] args) {
        //定义一个节点,数据域位1,地址域为null
        ListNode node1=new ListNode(1);
        //定义一个节点,数据域位2,地址域为null
        ListNode node2=new ListNode(2);
        //定义一个节点,数据域位3,地址域为null
        ListNode node3=new ListNode(3);
        ListNode node4=new ListNode(4);
        ListNode node5=new ListNode(5);
        ListNode node6=new ListNode(6);


        node1.next=node2;  //node1的地址域为node2的地址
        node2.next=node3;
        node3.next=node4;
        node4.next=node5;
        node5.next=node6;
        node6.next=null;
        System.out.println(node1);

        //输出链表的值
        LinkList linkList1=new LinkList();
        linkList1.head=node1;
        System.out.println("输出链表的值");
        linkList1.printLink();

        //输出链表的长度
        System.out.println("输出链表的长度");
        System.out.println(linkList1.GetListLength());

        //查找某个元素是否在链表节点上
        System.out.println("查找某个元素是否在链表节点上");
        System.out.println(linkList1.contains(3));;

        //指定位置插入节点
        linkList1.add(0,3);
        System.out.println("指定位置插入节点");
        linkList1.printLink();

        //删除指定位置节点
        linkList1.delete(1);
        System.out.println("删除指定位置节点");
        linkList1.printLink();

    }
}

链表的创建和遍历(头插法和尾插法)

public class LinkList{
    //定义链表的头结点
   ListNode head=null;

   //头插法
    public void headInsert(int val){
        //每次执行这个方法的时候,都要新建一个节点来存储数据
        ListNode listNode = new ListNode(val);
        //判断头指针是否为空,若是那么将头指针指向新节点
        if (head == null){
            head = listNode;
            return;
        }
        listNode.next = listNode;
        head = listNode;
    }

    //尾插法
    public void EndInsert(int val){
        //每次执行这个方法的时候,都要新建一个节点来存储数据
        ListNode listNode = new ListNode(val);
        //判断头指针是否为空,若是那么将头指针指向新节点
        if (head == null) {
            head = listNode;
            return;
        }
        //定义一个临时节点来充当指针,指针最开始指向头结点
        ListNode indexNode = listNode;
        //从头节点开始遍历,到最尾部插入
        while (indexNode != null){
            indexNode=indexNode.next;
        }
        indexNode.next = listNode;
    }

    //链表输出
    public void printLink(){
        //定义一个临时节点充当指针,从头结点开始向后移
        ListNode tempNode=head;
        //将临时节点不断向后移,直到临时节点指向null
        while (tempNode != null) {
            System.out.println(tempNode.val);
            tempNode = tempNode.next;
        }
        System.out.println();
    }
    //链表的长度
    public int GetListLength(){
        //定义一个节点指向该链表
        ListNode tempNode = head;
        int length=0;
        while (tempNode != null) {
            length++;
            tempNode = tempNode.next;
        }
        return length;
    }
}
}

链表中查找某节点

public boolean contains(int val){
        //定义一个节点指向该链表
        ListNode tempNode = head;
        int length = 0;
        while (tempNode != null) {
            if (tempNode.val == val) {
                return true;
            }
            tempNode = tempNode.next;
        }
        return false;
    }

指定位置插入节点

public void add(int val,int index){
        //首先判断index的合法性
        if (index < 0 || index >= GetListLength()){
            throw new IndexOutOfBoundsException("插入位置不合法");
        }
        //如果index=0,那就用头插法
        //如果index等于链表长度,那就用尾插法
        if (index==0){
            headInsert(val);
        } else if (index==GetListLength()){
            EndInsert(val);
        }else {
            //插到某个中间位置
            //每次执行这个方法的时候,都要新建一个节点来存储
            ListNode listNode=new ListNode(val);
            //定义一个节点指向这个链表
            ListNode temp=head;
            //记录前一个节点
            ListNode pre=null;
            //找到相关位置
            int position=0;
            while (temp != null){
                //如果位置正确那就开始交换
                if (position==index){
                    listNode.next=temp;
                    pre.next=listNode;
                    return;
                }
                pre=temp;
                temp=temp.next;
                position++;
            }
        }
    }

指定位置删除节点

public void delete(int index){
        //首先判断index的合法性
        if (index<0&&index>GetListLength()){
            throw new IndexOutOfBoundsException("删除位置不合法");
        }
        //如果删除的是头结点,那么栈内直接指向下一个就可以
        if (index==0){
            head=head.next;
            return;
        }
        //定义一个节点指向链表
        ListNode temp=head;
        ListNode pre=null;  //记录前置节点
        //找到相关位置
        int position=0;
        while (temp != null){
            if (position==index){
                pre.next=temp.next;
                temp.next=null;
                return;
            }
            pre=temp;
            temp=temp.next;
            position++;
        }

    }
  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用:海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题<有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2021-09-05 11:17:27  更:2021-09-05 11:18:46 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年11日历 -2024/11/26 0:50:30-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码