`
uule
  • 浏览: 6351917 次
  • 性别: Icon_minigender_1
  • 来自: 一片神奇的土地
社区版块
存档分类
最新评论

单向链表

 
阅读更多

单向链表

单向循环链表

 

数据结构(一) 单链表的实现-JAVA

数据结构Java实现03----单向链表的插入和删除

单链表头结点的插入java

 

注意:

构造函数名不带泛型

链表 LinkedList

单向链表 SinglyLinkedList

 

get、set、add、remove、length、isEmpty、clear

 

get时可直接返回值,set时返回老值(跟Map的put一样)

add时,记得也前节点关联

add时,若为空链表,则将要添加的节点设为头节点

只add元素时,相当于:

 

add(E element) =  add(Integer.MAX_VALUE, element);  

 

单链表结点类Node声明如下:

  

public class Node<E>  
{  
    public E Data;  
    public Node<E> Next;  
  
    public Node(E data,Node<E> next)  
    {  
        this.Data = data;  
        this.Next = next;  
    }  
  
    public Node(E Data)  
    {  
        this(Data,null);  
    }  
  
    public Node()  
    {  
        this(null,null);  
    }  
}  

 

Node<E>类有两个成员变量,data表示结点的数据域,保存数据元素本身,数据类型是E;next表示结点的地址域,保存后继结点的地址。

Node类中成员变量next的数据类型是Node类自己,Node类是“自引用的类”。所谓自引用的类(self-referential calss),是指一个类声明包含一个引用当前类的对象的成员变量。

 

建立并链接结点的语句如下:

  

public class MainForm  
{  
    public static void main(String args[])  
    {  
        Node<String> CC =new Node<String>("C");  
        Node<String> BB =new Node<String>("B",CC);  
        Node<String> AA =new Node<String>("A",BB);  
          
        System.out.println(AA.Data);  
        System.out.println(AA.Next.Data);  
        System.out.println(AA.Next.Next.Data);  
    }  
}  

 

单链表的头指针head也是一个结点引用,声明如下:

Node<E> head = null;  

 

当head ==null时,表示空单链表。

 

 

实现:

public class SinglyLinkedList<E>            //单链表类  
{  
    protected Node<E> head;                //头指针,指向单链表第一个结点  
      
    public SinglyLinkedList()              //构造空单链表  
    {  
        this.head = null;  
    }  
      
    public SinglyLinkedList(Node<E> head)  //构造指定头指针的单链表  
    {  
        this.head = head;  
    }  
      
      
    //判断单链表是否为空  
    public boolean isEmpty()              
    {  
        return this.head == null;  
    }  
      
     //返回单链表长度,单链表遍历算法  
    public int length()                 
    {  
        int i = 0;  
        Node<E> p = this.head;  
        while(p != null)  
        {  
            i ++;  
            p = p.Next;  
        }  
        return i;  
    }  
      
      
    //返回序号为index的对象,若单链表为空或序号错误则返回null  
    public E get(int index)            
    {  
        if(this.head != null && index >= 0)  
        {  
            int j = 0;  
            Node<E> p = this.head;  
            while(p != null && j < index)  
            {  
                j ++;  
                p = p.Next;  
            }  
            if(p !=null)  
            {  
                return (E)p.Data;  
            }  
        }  
        return null;  
    }  
      
      
    //设置序号为index的对象为element,若操作成功,返回原对象,否则返回null 
    public E set(int index,E element)                           
    {  
        if(this.head != null && index >= 0 && element != null)  
        {  
            int j = 0;  
            Node<E> p = this.head;  
            while(p != null && j < index)  
            {  
                j ++;  
                p = p.Next;  
            }  
            if(p != null)  
            {  
                E old = (E)p.Data;  
                p.Data = element;  
		
		//若操作成功,则返回原对象  
                return old;                                     
            }  
        }  
	
	//操作不成功
        return null;                                              
    }  
      
    //插入element对象,插入后对象序号为index,若操作成功返回true  
    public boolean add(int index,E element)                     
    {  
        if(element ==null)  
        {  
            return false; //不能添加空对象(null)  
        } 
	
        //头插入  
        if(this.head == null || index <= 0)   
        {  
            Node<E> q = new Node<E>(element);  
            q.Next = this.head;  
            this.head = q;  
            //this.head = new Node(element,this.head); //头插入,相当于上述3句  
        }  
	//单链表不空且index>=1  
        else  
        {  
            int j = 0;  
            Node<E> p = this.head;  
            while(p.Next != null && j < index - 1)               //寻找插入位置  
            {  
                j ++;  
                p = p.Next;  
            }  
            Node<E> q = new Node<E>(element);                   //中间/尾插入  
            q.Next = p.Next;                                    //q插入在p结点之后  
            p.Next = q;  
            //p.Next = new Node(element,p.Next);                //中间/尾插入,相当于上述3句  
        }  
        return true;  
    }  
      
    //在单链表最后插入对象    
    public boolean add(E element)                               
    {  
        return add(Integer.MAX_VALUE,element);  
    }  
      
      
    //移去序号为index的对象,若操作成功则返回被移去的对象,否则返回null    
    public E remove(int index)                                  
    {  
        E old = null;  
        if(this.head != null && index >= 0)  
        {  
            if(index == 0)                                      //头删除  
            {  
                old = (E)this.head.Data;  
                this.head = this.head.Next;  
            }  
            else                                                //中间/尾删除  
            {  
                int j = 0;  
                Node<E> p = this.head;  
                while(p.Next != null && j < index - 1)           //定位到待删除结点的前驱结点  
                {  
                    j ++;  
                    p = p.Next;  
                }  
                if(p.Next != null)  
                {  
                    old = (E)p.Next.Data;                       //若操作成功,返回被移去对象  
                    p.Next = (p.Next).Next;                     //删除p的后继结点  
                }  
            }  
        }  
        return old;  
    }  
      
     //清空单链表  
    public void clear()                                        
    {  
        this.head = null;  
    }  
    

    //返回所有元素值对应的字符串      
    public String toString()                                    
    {  
        String str = "(";  
        Node<E> p = this.head;  
        while(p != null)  
        {  
            str += p.Data.toString();  
            p = p.Next;  
            if(p != null)  
            {  
                str += ",";  
            }  
        }  
        return str + ")";  
    }  
}  

 =====================================================================================

链表反转:

Java单链表反转 详细过程

使用递归和非递归方式反转单向链表

 

public class Node<E> {
	public E Data;    
    public Node<E> Next;    
    
    public Node(E data,Node<E> next)    
    {    
        this.Data = data;    
        this.Next = next;    
    }    
    
    public Node(E Data)    
    {    
        this(Data,null);    
    }    
    
    public Node()    
    {    
        this(null,null);    
    }   
    
    

    /**
     * 递归逆序
     */
	@SuppressWarnings({ "null", "unchecked" })
	public static Node reverse(Node current){
		
		if(current == null || current.Next == null){
			return current;
		}
		
		/*
		 * 方法1:
		 * 递归,在反转当前节点之前先反转后续节点 
		Node nextNode = current.Next;
		Node newNode = reverse(nextNode);	
		
		current.Next = null;
		nextNode.Next = current;*/
		
		//法2:
		Node newNode = reverse(current.Next);	
		current.Next.Next = current;
		current.Next = null;
		
		return newNode;
	}
	
	
	/**
	 * 遍历逆序
	 * 
	 *  pre ->  cur  ->  tmp
	 * 
	 * 将当前节点的下一个节点缓存后更改当前节点指针 
	 * @param current
	 * @return
	 */
	public static Node reverse2(Node current) {  
        if (current == null)  
            return current;  
        
        Node pre = current;// 上一结点  
        Node cur = current.Next;// 当前结点  
        Node tmp;// 临时结点,用于保存当前结点的指针域(即下一结点)  
        while (cur != null) {// 当前结点为null,说明位于尾结点  
            tmp = cur.Next;  
            cur.Next = pre;// 反转指针域的指向  
  
            // 指针往下移动  
            pre = cur;  
            cur = tmp;  
        }  
        // 最后将原链表的头节点的指针域置为null,还回新链表的头结点,即原链表的尾结点  
        current.Next = null;  
          
        return pre;  
    }  
	
    public static void main(String[] args) throws Exception {
		Node<String> CC = new Node<String>("C");
		Node<String> BB = new Node<String>("B", CC);
		Node<String> AA = new Node<String>("A", BB);

		
		Node h = AA;  
        while (null != h) {  
            System.out.print(h.Data + " ");  
            h = h.Next;  
        }  
  
        System.out.println("\n**************************");  
        Node<String> dd = reverse2(AA);
        
        // 打印反转后的结果  
        while (null != dd) {  
        	System.out.print(dd.Data + " ");  
        	dd = dd.Next;  
        }        
	}
}

 结果:

A B C 

**************************

C B A 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

分享到:
评论

相关推荐

    基于springboot教育资源共享平台源码数据库文档.zip

    基于springboot教育资源共享平台源码数据库文档.zip

    视频笔记linux开发篇

    linux开发篇,配套视频:https://www.bilibili.com/list/474327672?sid=4493702&spm_id_from=333.999.0.0&desc=1

    readera-24-09-08plus2020.apk

    ReadEra 这个阅读应用能够打开下列任何格式的文档: EPUB, PDF, DOC, RTF, TXT, DJVU, FB2, MOBI, 和 CHM. 基本上来说,你可以用它阅读你的设备内存中的任何书籍或者文本文档。 这个应用与划分成章节的文档兼。,有一个书签功能,可以在你阅读的时候,自动保存你的进度。另外,它让你更改页面模式,从几种不同的主题中进行挑选(夜间,白天,棕黑色调,还有控制台)。

    STM32单片机控制舵机旋转

    软件环境:KEIL4 硬件环境:STM32单片机+舵机 控制原理:通过控制输出信号的占空比调节舵机旋转的角度

    基于springboot仓库管理系统源码数据库文档.zip

    基于springboot仓库管理系统源码数据库文档.zip

    酒店管理系统源码C++实现的毕业设计项目源码.zip

    酒店管理系统源码C++实现的毕业设计项目源码.zip,个人大四的毕业设计、经导师指导并认可通过的高分设计项目,评审分98.5分。主要针对计算机相关专业的正在做毕设的学生和需要项目实战练习的学习者,也可作为课程设计、期末大作业。 酒店管理系统源码C++实现的毕业设计项目源码.zip,酒店管理系统源码C++实现的毕业设计项目源码.zip个人大四的毕业设计、经导师指导并认可通过的高分设计项目,评审分98.5分。主要针对计算机相关专业的正在做毕设的学生和需要项目实战练习的学习者,也可作为课程设计、期末大作业。酒店管理系统源码C++实现的毕业设计项目源码.zip酒店管理系统源码C++实现的毕业设计项目源码.zip酒店管理系统源码C++实现的毕业设计项目源码.zip,个人大四的毕业设计、经导师指导并认可通过的高分设计项目,评审分98.5分。主要针对计算机相关专业的正在做毕设的学生和需要项目实战练习的学习者,也可作为课程设计、期末大作业。酒店管理系统源码C++实现的毕业设计项目源码.zip,个人大四的毕业设计、经导师指导并认可通过的高分设计项目,评审分98.5分。主要针对计算机相关专业的正在做毕

    58商铺全新UI试客试用平台网站源码

    58商铺全新UI试客试用平台网站源码

    基于SpringBoot+Vue的轻量级定时任务管理系统.zip

    springboot vue3前后端分离 基于SpringBoot+Vue的轻量级定时任务管理系统.zip

    毕业设计&课设_微博情感分析,用 flask 构建 restful api,含相关算法及数据文件.zip

    该资源内项目源码是个人的课程设计、毕业设计,代码都测试ok,都是运行成功后才上传资源,答辩评审平均分达到96分,放心下载使用! ## 项目备注 1、该资源内项目代码都经过严格测试运行成功才上传的,请放心下载使用! 2、本项目适合计算机相关专业(如计科、人工智能、通信工程、自动化、电子信息等)的在校学生、老师或者企业员工下载学习,也适合小白学习进阶,当然也可作为毕设项目、课程设计、作业、项目初期立项演示等。 3、如果基础还行,也可在此代码基础上进行修改,以实现其他功能,也可用于毕设、课设、作业等。 下载后请首先打开README.md文件(如有),仅供学习参考, 切勿用于商业用途。

    4D毫米波雷达点云数据处理方法研究.caj

    4D毫米波雷达点云数据处理方法研究.caj

    S M 2 2 5 8 X T量产工具

    S M 2 2 5 8 X T 量产工具供大家下载使用

    基于springboot的文物管理系统源码数据库文档.zip

    基于springboot的文物管理系统源码数据库文档.zip

    基于springboot的电影院售票管理系统源码数据库文档.zip

    基于springboot的电影院售票管理系统源码数据库文档.zip

    Javaweb仓库管理系统项目源码.zip

    基于Java web 实现的仓库管理系统源码,适用于初学者了解Java web的开发过程以及仓库管理系统的实现。

    美容美发项目,使用django框架,前后端一体化项目

    美容美发项目,使用django框架,前后端一体化项目

    2023年中国在线票务行业市场规模约为24.99亿元,挖掘市场新机遇

    在线票务:2023年中国在线票务行业市场规模约为24.99亿元,挖掘市场蓝海新机遇 在数字浪潮的席卷下,传统的票务销售模式正经历着前所未有的变革。纸质门票逐渐淡出人们的视野,取而代之的是便捷、高效的数字和移动票务。这一转变不仅为消费者带来了前所未有的购票体验,更为在线票务平台开辟了广阔的发展空间和市场机遇。随着国民经济的持续增长和文体娱乐行业的蓬勃发展,中国在线票务行业正站在时代的风口浪尖,等待着每一位有志之士的加入。那么,这片蓝海市场究竟蕴藏着怎样的潜力?又该如何把握机遇,实现突破?让我们一同探索。 市场概况: 近年来,中国在线票务行业市场规模持续扩大,展现出强劲的增长势头。据QYResearch数据显示,2023年中国在线票务行业市场规模约为24.99亿元,尽管受到宏观经济的影响,市场规模增速放缓,但整体趋势依然向好。这一增长主要得益于国民人均收入的不断提高、电影及演出行业的快速发展以及政府政策的支持。例如,2023年财政部、国家电影局发布的《关于阶段性免征国家电影事业发展专项资金政策的公告》,为电影行业注入了强劲动力,进而推动了在线票务市场规模的扩大。 技术创新与趋势: 技术进步

    基于SpringBoot的养老院管理系统源码数据库文档.zip

    基于SpringBoot的养老院管理系统源码数据库文档.zip

    毕业设计&课设_含构建设置及相关操作,基于特定技术,具体功能未详细说明.zip

    该资源内项目源码是个人的课程设计、毕业设计,代码都测试ok,都是运行成功后才上传资源,答辩评审平均分达到96分,放心下载使用! ## 项目备注 1、该资源内项目代码都经过严格测试运行成功才上传的,请放心下载使用! 2、本项目适合计算机相关专业(如计科、人工智能、通信工程、自动化、电子信息等)的在校学生、老师或者企业员工下载学习,也适合小白学习进阶,当然也可作为毕设项目、课程设计、作业、项目初期立项演示等。 3、如果基础还行,也可在此代码基础上进行修改,以实现其他功能,也可用于毕设、课设、作业等。 下载后请首先打开README.md文件(如有),仅供学习参考, 切勿用于商业用途。

    Go语言入门指南:基础语法、并发编程详解

    内容概要:本文档是一份详细的Go语言教程,从基础概念介绍到高级主题均有覆盖。主要内容包括Go语言的基础语法、数据类型、控制结构、函数、结构体、接口和并发编程等方面。通过具体示例介绍了如何使用Go语言进行开发。 适合人群:初学者和有一定经验的程序员都可以从这篇教程中受益,特别是那些想要快速掌握Go语言并应用于实际项目的开发者。 使用场景及目标:适用于初学者系统学习Go语言的基础知识和常用功能;也可以作为已有开发经验者的参考资料,帮助他们解决具体的编程问题,提高开发效率。 其他说明:本教程不仅包含了Go语言的基本知识点,还重点讲解了其独特的并发编程模型。读者在学习过程中应该注重理论与实践相结合,通过实际编写代码来加深理解和记忆。

    基于springboot计算机基础网上考试系统源码数据库文档.zip

    基于springboot计算机基础网上考试系统源码数据库文档.zip

Global site tag (gtag.js) - Google Analytics