栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

java数据结构03(单向链表)

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

java数据结构03(单向链表)

1.链表

1)链表是以节点的方式来存储,是链式存储

2)每个节点包含data域和next域,data域用来存放数据,next域指向下一个节点

3)链表的各个节点不一定是连续存储的

4)链表分带头节点的链表和没有头节点的链表,根据实际需求确定

2.单向链表

单向链表的节点包括两个元素,分别为数据和指针

(1)定义节点

package datastructure.LinkedList.SingalLinkedList;

public class HeroNode {
    public int no;
    public String name;
    public String nickName;
    HeroNode next;



    public HeroNode(int no, String name, String nickName) {
        this.no = no;
        this.name = name;
        this.nickName = nickName;
    }
    //重写toString方法

    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + ''' +
                ", nickName='" + nickName + ''' +
                '}';
    }
}

 (2)单向链表的实现(增删改查)

package datastructure.LinkedList.SingalLinkedList;

import java.util.Stack;

public class SingalLinkedList {
    //初始化头节点
    private HeroNode head = new HeroNode(0,"","");
    //添加节点到单向链表
    //不需要考虑节点的编号,找到最后一个节点将新节点加入到后面
    //将最后一个节点的next指向新加入的节点
    public void add(HeroNode heroNode){
        //头节点不能动,从头节点开始遍历
        //设定一个临时变量temp
        HeroNode temp = head;
        while (true){
            //找到了链表的末尾
            if (temp.next == null) {
                break;
            }
            //未找到,则后移
            temp = temp.next;
        }
        temp.next = heroNode;

    }
    //根据排名添加节点
    
    public void addByOrder(HeroNode heroNode){
        //头节点不能动,设置临时节点temp
        //设置一个标签flag,默认为false
        HeroNode temp = head;
        boolean flag = false;//flag标签表示添加的编号是否已经存在
        //链表末尾
        while (true) {
            if (temp.next == null) {
                break;
            }
            if (temp.next.no > heroNode.no) {//位置已经找到
                break;
            } else if (temp.next.no == heroNode.no) {
                System.out.println("编号重复!");
                return;
            }
            temp = temp.next;
        }
            heroNode.next = temp.next;
            temp.next = heroNode;
    }

    //修改节点
    //根据no值来修改,即no不能修改
    public void update(HeroNode newHeroNode){
        if (head.next == null){
            System.out.println("链表为空!");
            return;
        }
        HeroNode temp = head.next;
        boolean flag = false;//判断标识符false表示未找到,true表示已经找到
        //遍历
        while (true){
            if (temp == null) {
                break;
            }else if(temp.no == newHeroNode.no){
                flag = true;
                break;
            }
            temp = temp.next;//后移
        }
        if (flag){
            //找到了
            temp.name = newHeroNode.name;
            temp.nickName = newHeroNode.nickName;
        }else{
            //未找到
            System.out.println("没有找到编号为"+newHeroNode.no+"的英雄!");
        }
    }

    //删除节点
    
    public void del(int no){
        //判断是否为空链表
        if (head.next == null){
            System.out.println("链表为空!");
            return ;
        }
        HeroNode temp = head;
        boolean flag = false;//标识符,false表示未找到。true表示已经找到
       while (true){
           if (temp.next == null) {
               break;
           }
           if (temp.next.no == no){
               flag = true;
               break;
           }
           temp = temp.next;//未找到则后移
       }
       if (flag){
           temp.next = temp.next.next;

       }else {
           System.out.println("未找到编号为"+no+"的英雄,无法进行删除");
       }
    }

    //遍历节点
    public void list(){
        //判断链表是否为空
        if (head.next == null) {
            System.out.println("原链表为空!");
            return;
        }
        //头节点不能移动,设置辅助节点temp
        HeroNode temp = head.next;
        while (true){
            //判断是否到了链表末尾
            if (temp == null) {
                break;
            }
            //输出节点信息
            System.out.println(temp);
            //节点后移
            temp = temp.next;
        }
    }
    //求单链表的节点个数
    
    public int getLength(HeroNode head){
        //判断链表是否为空
        if (head.next == null) {
            System.out.println("链表为空!");
            return 0;
        }
        HeroNode temp = head.next;
        int sum = 0;
        while (true){
            if (temp == null) {
                break;
            }
            sum++;
            temp = temp.next;//后移
        }
        return sum;
    }

    public HeroNode getHead() {
        return head;
    }

    //查找单链表的倒数第K个节点
    //获取链表的总长度 size=getLength()
    //遍历到size-k即可
    public HeroNode findLastIndexNode(HeroNode head,int index){
        //判断链表是否为空
        if (head.next == null) {
            return null;
        }
        int size = getLength(getHead());
        HeroNode temp = head.next;
        if (index < 0 || index > size){

            return null;
        }
        //
        for (int i = 0;i < size-index;i++){
            temp = temp.next;
        }
        return temp;
    }

    //单链表反转
    
    public void reverseList(HeroNode head){
        //若链表为空或者只有一个节点,则无需反转
        if (head.next == null || head.next.next == null){
            return;
        }
        HeroNode temp = head.next;
        HeroNode next = null;
        HeroNode reverseHead = new HeroNode(0,"","");
        //遍历原来的链表,每遍历一个将该节点取出,并放入新链表reverseHead的最前面
        while (temp != null){
            next = temp.next;//保存当前节点的下一个节点
            temp.next = reverseHead.next;//将当前节点点的下一个节点指向新链表最前端
            reverseHead.next = temp;//将新遍历出来的节点插入到新链表的最前端
            temp = next;//后移

        }
        head.next = reverseHead.next;//将反转的链表放回到原始的链表
    }

    //从尾到头打印单链表
    
    public void reversePrint(HeroNode head){
        //判断链表是否为空
        if (head.next == null){
            return;
        }
        Stack stack = new Stack();
        HeroNode temp = head.next;
        //将链表的节点压入栈中
        while (temp != null){
            stack.push(temp);
            temp = temp.next;
        }
        //弹栈打印
        while (stack.size()>0){
            System.out.println(stack.pop());
        }
    }

    


}
3.关于单向链表的几道面试题

(1)求单链表中有效节点的个数

思路分析:如果链表带有头节点,不需要统计头节点

先判断链表是否为空,为空则返回0

定义一个辅助变量,该辅助变量指向头节点的下一个节点,再进行遍历即可

	//求单链表的节点个数
	
	publicintgetLength(HeroNode head){
	//判断链表是否为空
	if(head.next==null){
	System.out.println("链表为空!");
	Return 0;
	}
	HeroNodetemp=head.next;
	Int sum=0;
	while(true){
	if(temp==null){
	break;
	}
	sum++;
	temp=temp.next;//后移
	}
	Return sum;
	}

(2)查找单链表中的倒数第 k 个结点 【新浪面试题】

思路:1.编写一个方法,接收head节点,同时接收一个index,index表示倒数第index个节点

 2.把链表从头到尾遍历,得到链表的总长度size

 3.判断index的大小,当index<0 或者 index > size 则返回null

 4.从链表的第一个开始遍历(size-index)个,从而得到该节点

	//查找单链表的倒数第K个节点
	//获取链表的总长度size=getLength()
	//遍历到size-k即可
	Public HeroNode findLastIndexNode(HeroNode head,int index){
	//判断链表是否为空
	if(head.next==null){
	Return null;
	}
	Int size=getLength(getHead());
	HeroNode temp=head.next;
	if(index<0||index>size){
	
	Return null;
	}
	//
	for(inti=0;i 

3.单向链表的反转【腾讯面试题】

 

	//单链表反转
	
	Public void reverseList(HeroNode head){
	//若链表为空或者只有一个节点,则无需反转
	if(head.next==null||head.next.next==null){
	return;
	}
	HeroNode temp=head.next;
	HeroNode next=null;
	HeroNode reverseHead=new HeroNode(0,"","");
	//遍历原来的链表,每遍历一个将该节点取出,并放入新链表reverseHead的最前面
	while(temp!=null){
	next=temp.next;//保存当前节点的下一个节点
	temp.next=reverseHead.next;//将当前节点点的下一个节点指向新链表最前端
	reverseHead.next=temp;//将新遍历出来的节点插入到新链表的最前端
	temp=next;//后移
	
	}
	head.next=reverseHead.next;//将反转的链表放回到原始的链表
}

4.从尾到头打印单向链表

	//从尾到头打印单链表
	
	Public void reverse Print(HeroNodehead){
	//判断链表是否为空
	if(head.next==null){
	return;
	}
	Stackstack=new Stack();
	HeroNode temp=head.next;
	//将链表的节点压入栈中
	while(temp!=null){
	stack.push(temp);
	temp=temp.next;
	}
	//弹栈打印
	while(stack.size()>0){
	System.out.println(stack.pop());
	}
}
 4.双向链表
  • 单向链表的缺点分析:

1) 单向链表,查找的方向只能是一个方向,而双向链表可以向前或者向后查找。

2) 单向链表不能自我删除,需要靠辅助节点 ,而双向链表,则可以自我删除,所以前面我们单链表删除时节点,总是找到 temp,temp 是待删除节点的前一个节点

  • 双向链表增删改查思路分析

(1)遍历

方式与单链表一样,不过可以向前也可以向后

(2)添加(默认添加到双向链表最后)

1.找到双向链表的最厚一个节点·

2.temp.next = newHeroNode

3.newHeroNode.pre = temp;

(3)  修改

思路与单向链表一样

(4)删除

(1) 因为是双向链表,因此,我们可以实现自我删除某个节点

(2) 直接找到要删除的这个节点,比如 temp

(3) temp.pre.next = temp.next

(4) temp.next.pre = temp.pre;

双向链表节点:

package datastructure.LinkedList.DoubleLinkedList;

public class HeroNode1 {
    public int no;
    public String name;
    public String nickName;
    HeroNode1 next;//指向下一个节点
    HeroNode1 pre;//指向上一个节点

    public HeroNode1(int no, String name, String nickName) {
        this.no = no;
        this.name = name;
        this.nickName = nickName;
    }

    @Override
    public String toString() {
        return "HeroNode1{" +
                "no=" + no +
                ", name='" + name + ''' +
                ", nickName='" + nickName + ''' +
                '}';
    }
}

双向链表

package datastructure.LinkedList.DoubleLinkedList;

public class DoubleLinkedList {
    //初始化头节点
    private HeroNode1 head = new HeroNode1(0,"","");
    //添加节点到双向链表
    public void add(HeroNode1 heroNode){
        HeroNode1 temp = head;
        while (true){
            //找链表的末尾
            if (temp.next == null) {
                break;
            }
            temp = temp.next;//后移
        }
        //形成一个双向链表节点
        temp.next = heroNode;
        heroNode.pre = temp;
    }
    //遍历
    public void list(){
        //判断链表是否为空
        if (head.next == null){
            System.out.println("链表为空");
            return;
        }
        //设置辅助节点temp
        HeroNode1 temp = head.next;
        while (temp != null){
            System.out.println(temp);
            temp = temp.next;
        }
    }
    //修改节点
    public void update(HeroNode1 newHeroNode){
        //判断链表是否为空
        if (head.next == null){
            System.out.println("链表为空!");
            return;
        }
        HeroNode1 temp = head.next;
        boolean flag = false;//标签,默认为false没有找到,true表示找到该节点
        while (true){
            if (temp.next == null) {
                break;
            }
            if (temp.no == newHeroNode.no){
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag){
            temp.name = newHeroNode.name;
            temp.nickName = newHeroNode.nickName;
        }else{
            System.out.println("没有找到编号为"+newHeroNode.no+"的节点");
        }
    }

    public HeroNode1 getHead() {
        return head;
    }

    //删除节点
    public void del(int index){
        //判断链表是否为空
        if(head.next == null){
            System.out.println("链表为空!");
            return;
        }
        //设置辅助节点temp
        HeroNode1 temp = head.next;
        boolean flag = false;//标识符false表示没有找到该节点,true表示找到了该节点
        while (true){
            if (temp == null){
                break;
            }
            if (temp.no == index){
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag){
            if (temp.next == null) {
                //最后一个节点
                temp.pre.next = temp.next;
            }else {
                temp.pre.next = temp.next;//删除节点temp
                temp.next.pre = temp.pre;//若为最后一个节点,则不需要执行这个
            }
        }else{
            System.out.printf("链表中没有编号为%d的英雄",index);
        }

    }
    //按照编号顺序添加
    public void addByOrder(HeroNode1 heroNode1){
        HeroNode1 temp = head;
        boolean flag = false;//标识符,判断是否具有重复
        while (true){
            if (temp.next == null){
                break;
            }
            if (temp.next.no > heroNode1.no){
                break;
            }else if(temp.next.no == heroNode1.no){
                flag = true;
                break;
            }
            temp = temp.next;

        }
        if (flag ){
            System.out.println("加入的节点"+heroNode1.no+"编号重复");
        }else{
            heroNode1.next = temp.next;
            if (temp.next != null){
                temp.next.pre = heroNode1;
            }
            temp.next = heroNode1;
            heroNode1.pre = temp;

        }

    }


}

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/936952.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号