Java数据结构与算法--链表(Linked List)

本文主要是介绍Java数据结构与算法--链表(Linked List)，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

1.1 链表(Linked List)介绍

单链表 小结上图：

链表是以节点的方式来存储，是链式存储。
每个节点包含 data 域， next 域：指向下一个节点。
如图：发现链表的各个节点不一定是连续存储。
链表分带头节点的链表和没有头节点的链表，根据实际的需求来确定。

1.2 单链表介绍

单链表(带头结点) 逻辑结构示意图如下：
带头结点单链表 1.2.1 单链表的应用实例
使用带head头的单向链表实现 –水浒英雄排行榜管理完成对英雄人物的增删改查操作。

第一种方法在添加英雄时，直接添加到链表的尾部
思路分析示意图
第二种方式在添加英雄时，根据排名将英雄插入到指定位置。(如果有这个排名，则添加失败，并给出提示)
思路分析示意图：
修改节点功能
思路：
(1) 先找到该节点，通过遍历
(2) temp.name = newHeroNode.name ; temp.nickname= newHeroNode.nickname
删除节点
思路分析的示意图:
完成的代码演示:

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
/**
 * @author zk
 * @version 1.0.0
 * @ClassName SingleLinkedListDemo.java
 * @Description TODO
 * @createTime 2021年09月17日 15:26:00
 */
public class SingleLinkedListDemo {
    public static void main(String[] args) {
        HeroNode heroNode1 = new HeroNode(0, "张三", "san");
        HeroNode heroNode2 = new HeroNode(1, "李四", "si");
        HeroNode heroNode3 = new HeroNode(2, "王五", "wu");
        HeroNode heroNode4 = new HeroNode(3, "赵六", "liu");
        SingleLinkedList singleLinkedList = new SingleLinkedList();
        singleLinkedList.add(heroNode1);
        singleLinkedList.add(heroNode2);
        singleLinkedList.add(heroNode4);
        singleLinkedList.add(heroNode3);
        singleLinkedList.list();
        System.out.println("------清空链表后------");
        singleLinkedList.clear();
        singleLinkedList.list();
        System.out.println("------按照no顺序添加------");
        singleLinkedList.addOrder(heroNode3);
        singleLinkedList.addOrder(heroNode1);
        singleLinkedList.addOrder(heroNode2);
        singleLinkedList.addOrder(heroNode3);
        HeroNode heroNode5 = new HeroNode(2, "赵云", "yun");
        singleLinkedList.list();
        System.out.println("------修改后------");
        singleLinkedList.update(heroNode5);
        singleLinkedList.list();
        System.out.println("------删除后------");
        singleLinkedList.delete(0);
        singleLinkedList.list();
        System.out.println("------获得链表长度------");
        System.out.println(singleLinkedList.getLength());
        System.out.println("------获取倒数第k个节点------");
        HeroNode lastIndexNode = singleLinkedList.findLastIndexNode(3);
        System.out.println(lastIndexNode);
        System.out.println("------单链表反转后------");
        singleLinkedList.reverseLinked();
        singleLinkedList.list();
        System.out.println("------单向链表逆向打印------");
        singleLinkedList.reversePrint();



        // 测试合并两个链表
        System.out.println("------测试合并两个链表------");
        HeroNode heroNode6 = new HeroNode(6, "张三", "san");
        HeroNode heroNode7 = new HeroNode(7, "李四", "si");
        HeroNode heroNode8 = new HeroNode(8, "王五", "wu");
        HeroNode heroNode9 = new HeroNode(9, "赵六", "liu");
        SingleLinkedList singleLinkedList1 = new SingleLinkedList();
        singleLinkedList1.addOrder(heroNode6);
        singleLinkedList1.addOrder(heroNode7);
        singleLinkedList1.addOrder(heroNode8);
        singleLinkedList1.addOrder(heroNode9);


        HeroNode heroNode10 = new HeroNode(10, "张三", "san");
        HeroNode heroNode11 = new HeroNode(11, "李四", "si");
        HeroNode heroNode12 = new HeroNode(12, "王五", "wu");
        HeroNode heroNode13 = new HeroNode(13, "赵六", "liu");
        SingleLinkedList singleLinkedList2 = new SingleLinkedList();
        singleLinkedList1.addOrder(heroNode10);
        singleLinkedList1.addOrder(heroNode11);
        singleLinkedList1.addOrder(heroNode12);
        singleLinkedList1.addOrder(heroNode13);
        merSingleLinkedList(singleLinkedList1,singleLinkedList2);
        singleLinkedList1.list();

    }
    // 合并两个链表
    public static SingleLinkedList merSingleLinkedList(SingleLinkedList sl1,SingleLinkedList sl2){
        HeroNode sl2head = sl2.getHead();
        HeroNode item = sl2head.next;
        while (item != null){
            sl1.addOrder(item);
            item = item.next;
        }
        return sl1;
    }
}

class SingleLinkedList{
    private HeroNode head = new HeroNode(0,"","");
    // 获取头节点(不是链表中的有效数据)
    public HeroNode getHead() {
        return head;
    }
    // 单链表逆向打印
    public void reversePrint(){
        if (head.next==null){
            return;
        }
        Stack<HeroNode> nodeStack = new Stack<>();
        HeroNode current = head.next;
        // 将链表的所有节点入栈
        while (current!=null){
            nodeStack.push(current);
            current = current.next;
        }
        // 将链表的所有节点出栈
        while (nodeStack.size()>0){
            System.out.println(nodeStack.pop());
        }

    }

    // 单链表的反转
    public void reverseLinked(){
        if (head.next==null||head.next.next==null){
            return;
        }
        // 指向链表的第一个节点
        HeroNode current = head.next;
        // 用作备份下一个节点
        HeroNode next = null;
        HeroNode reverseNode = new HeroNode(0, "", "");
        while (current!=null){
            next = current.next;
            current.next = reverseNode.next;
            reverseNode.next=current;
            current = next;
        }
        this.head = reverseNode;
    }

    // 获得链表的第k个节点
    public HeroNode findLastIndexNode(int index){
        if (head.next==null){
            return null;
        }
        int length = getLength();
        // 校验
        if (index>length || index<=0){
            return null;
        }
        HeroNode current = head.next;
        for (int i = 0; i < length - index; i++) {
            current = current.next;
        }
        return current;
    }
    // 获取链表的长度
    public int getLength(){
        if (head.next==null){
            return 0;
        }
        HeroNode current = head.next;
        int length = 0;
        while (current!=null){
            length++;
            current = current.next;
        }
        return length;
    }
    // 根据编号no删除节点
    public void delete(int no){
        // head节点不能动,创建一个备份
        HeroNode temp = head;
        // 定义一个标记
        boolean flag = false;
        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 update(HeroNode newHeroNode){
        // head节点不能动,创建一个备份
        HeroNode temp = head;
        // 定义一个标记
        boolean flag = false;
        while (true){
            if (temp.next==null){
                break;
            }
            if (temp.next.no==newHeroNode.no){
                // 找到节点
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag){
            temp.next.name = newHeroNode.name;
            temp.next.nickName = newHeroNode.nickName;
        }else {
            System.out.println("要修改的节点不存在");
        }

    }

    //添加的时候按照no从小到大排序
    public void addOrder(HeroNode heroNode){
        //因为head节点不能用，所以创建一个辅助
        HeroNode temp = head;
        boolean flag = false;
        while (true){
            if (temp.next==null){
                break;
            }
            if (temp.next.no==heroNode.no){
                flag = true;
                break;
            }
            if (temp.next.no>heroNode.no){
                break;
            }
            temp = temp.next;
        }
        if (flag){
            System.out.println("该数据已存在");
        }else {
            heroNode.next = temp.next;
            temp.next= heroNode;
        }

    }
    // 按顺序依次添加到链表尾部
    public void add(HeroNode heroNode){
        //因为head节点不能用，所以创建一个辅助
        HeroNode temp = head;
        //遍历链表，找到最后一个节点
        while (true){
            if (temp.next==null){
                temp.next = heroNode;
                break;
            }
            temp = temp.next;
        }
    }
    // 打印链表所有数据
    public void list(){
        //因为head节点不能用，所以创建一个辅助
        HeroNode temp = head;
        while (true){
            if (temp.next==null){
                break;
            }
            System.out.println(temp.next);
            temp = temp.next;
        }
    }
    // 清空链表
    public void clear(){
        head.next=null;
    }

}

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

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

这篇关于Java数据结构与算法--链表(Linked List)的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！

Java教程

Java数据结构与算法--链表(Linked List)

1.1 链表(Linked List)介绍

1.2 单链表介绍

前端开发

后端开发

移动端开发

数据库

服务器运维

人工智能

区块链

游戏开发

网站运营

大数据/云计算

软件工程

软件/开发工具使用

资讯