devbox
煮酒与君饮
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

java代码实现链表_设计链表java

作者：煮酒与君饮 | 2024-07-14 04:05:57

赞

踩

设计链表java

文章目录

前言

链表是一种常见的数据结构，用于存储和组织数据。它由一系列节点组成，每个节点包含数据和指向下一个节点的指针。

链表可以分为单向链表和双向链表两种类型。

在单向链表中，每个节点只包含一个指向下一个节点的指针。链表的第一个节点称为头节点，最后一个节点称为尾节点，尾节点的指针指向空值。

在双向链表中，每个节点包含指向前一个节点和后一个节点的指针。这使得在双向链表中可以从前向后或从后向前遍历。

链表相对于数组的优势在于插入和删除操作的效率较高。由于链表中的节点可以在内存中分散存储，所以可以在不移动其他节点的情况下插入或删除节点。这使得链表在需要频繁进行插入和删除操作的场景中更加高效。

然而，链表的缺点是访问任意节点的效率较低。由于链表中的节点不是连续存储的，所以无法像数组一样通过索引直接访问节点，而是需要从头节点开始遍历链表直到找到目标节点。

链表常见的操作包括插入、删除和遍历。插入操作可以在链表的任意位置插入一个新节点。删除操作可以删除链表中的一个节点。遍历操作可以按顺序访问链表中的所有节点。

链表还有一些特殊的变种，如循环链表和跳表。循环链表是一种特殊的链表，其中尾节点的指针指向头节点，形成一个闭环。跳表是一种高效的数据结构，用于在有序链表中快速查找和插入节点。

总的来说，链表是一种灵活且高效的数据结构，适用于需要频繁进行插入和删除操作的场景。

一、单链表

在这里插入图片描述

package exer.linked;

/**
 * 单链表
 */
public class GoodsNode {
    public int id;

    public String name;

    public double price;

    public GoodsNode next;

    public GoodsNode(int id, String name, double price) {
        this.id = id;
        this.name = name;
        this.price = price;
    }

    @Override
    public String toString() {
        return "GoodsNode{" +
                "id=" + id +
                ", name='" + name + '\'' +
                ", price=" + price +
                '}';
    }
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
package exer.linked;


/**
 * 单链表常见操作
 */
public class DLLinkedList {
    //初始化头结点
    private GoodsNode head=new GoodsNode(0,"",0.0);

    /**
     * 无序增加
     */
    public void add(GoodsNode goodsNode){
        //先将头结点赋值给临时节点
        GoodsNode temp=head;
        while (true){
            //如果临时节点的next域为null，说明可以添加节点了，可以跳出循环
            if (temp.next==null){
                break;
            }
            //遍历到下一个节点
            temp=temp.next;
        }
        //将要添加的节点赋给next域
        temp.next=goodsNode;
    }
    /**
     * 有序增加
     */
    public void addOrder(GoodsNode goodsNode){
        //将头结点赋值给临时节点
        GoodsNode temp=head;
        boolean flag=true;
        while (true){
            if (temp.next==null){
                break;
            }
            if (temp.next.id>goodsNode.id){
                break;
            }
            if (temp.next.id==goodsNode.id){
                flag=false;
                break;
            }
            temp=temp.next;
        }
        if (flag){
            goodsNode.next=temp.next;
            temp.next=goodsNode;
        }else{
            System.out.println("不能重复添加节点");
        }
    }

    /**
     * 删除元素
     */
    public void delete(int id){

        //将头结点的next域赋值给temp临时节点
        GoodsNode temp=head;
        boolean flag=false;
        while (true){
            //表明没有找到要删除的节点
            if (temp.next==null){
                break;
            }
            //表明找到了要删除的节点
            if (temp.next.id==id){
                flag=true;
                break;
            }
            temp=temp.next;
        }
        if (flag){
          temp.next=temp.next.next;
        }else{
            System.out.println("没有找到要删除的节点");
        }

    }
    /**
     * 修改元素
     */
    public void update(GoodsNode goodsNode){
        if (head.next==null){
            System.out.println("这是一个空链表");
            return;
        }
        GoodsNode temp=head.next;
        while (true){
            if (temp==null){
                break;
            }
            if (temp.id==goodsNode.id){
                temp.name=goodsNode.name;
                temp.price=goodsNode.price;
                break;
            }
            temp=temp.next;
        }

    }

    /**
     * 获取所有元素
     */
    public void getAll(){
        GoodsNode temp=head;
        while (true){
            if (temp.next==null){
                break;
            }
            System.out.println(temp.next);
            temp=temp.next;
        }

    }
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
/**
测试
*/
package exer.linked;

public class DLLinkedListTest {
    public static void main(String[] args) {
        DLLinkedList dlLinkedList=new DLLinkedList();
        GoodsNode goodsNode1 = new GoodsNode(1, "耐克帽子", 100);
        GoodsNode goodsNode2 = new GoodsNode(2, "耐克上衣", 200);
        GoodsNode goodsNode3 = new GoodsNode(3, "耐克鞋子", 300);
        GoodsNode goodsNode4 = new GoodsNode(4, "耐克裤子", 400);


        GoodsNode goodsNode5 = new GoodsNode(4, "耐克帽子", 100);
        GoodsNode goodsNode6 = new GoodsNode(8, "耐克上衣", 200);
        GoodsNode goodsNode7 = new GoodsNode(1, "耐克鞋子", 300);
        GoodsNode goodsNode8 = new GoodsNode(3, "耐克裤子", 400);
//        dlLinkedList.add(goodsNode1);
//        dlLinkedList.add(goodsNode2);
//        dlLinkedList.add(goodsNode3);
//        dlLinkedList.add(goodsNode4);

        dlLinkedList.addOrder(goodsNode5);
        dlLinkedList.addOrder(goodsNode6);
        dlLinkedList.addOrder(goodsNode7);
        dlLinkedList.addOrder(goodsNode8);
        //dlLinkedList.delete(18);
        dlLinkedList.update(new GoodsNode(4,"耐克太阳帽",8888));
        dlLinkedList.getAll();
    }
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33

二、双链表

在这里插入图片描述

package exer.linked;

/**
 * 双链表
 */
public class BookNode {
    public int id;

    public String name;

    public double price;

    public BookNode pre;

    public BookNode next;

    public BookNode(int id, String name, double price) {
        this.id = id;
        this.name = name;
        this.price = price;
    }

    @Override
    public String toString() {
        return "BookNode{" +
                "id=" + id +
                ", name='" + name + '\'' +
                ", price=" + price +
                '}';
    }
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
package exer.linked;

import javax.xml.stream.FactoryConfigurationError;
import java.sql.SQLOutput;

/**
 * 双链表常见操作
 */
public class DualLinkedList {
    //初始化一个头结点不存放数据
    private BookNode head=new BookNode(0,"",0.0);

    /**
     * 无序添加
     */
    public void add(BookNode bookNode){
        BookNode temp=head;
        while (true){
            if (temp.next==null){
                break;
            }
            temp=temp.next;
        }
        temp.next=bookNode;
        //bookNode.pre=temp;
        temp.next.pre=temp;
    }

    /**
     * 有序添加
     */
    public void addOrder(BookNode bookNode){
        BookNode temp=head;
        int flag=0;
        while (true){
            if (temp.next==null){
                flag=1;
                break;
            }
            if (temp.next.id==bookNode.id){
                flag=0;
                break;
            }
            if (temp.next.id> bookNode.id){
                flag=2;
                break;
            }
            temp=temp.next;
        }
        if (flag==2){
            bookNode.next=temp.next;
            temp.next=bookNode;

                temp.next.pre = bookNode;

            bookNode.pre=temp;
        }else if (flag==0){
            System.out.println("不能重复添加节点");
        }else{
            temp.next=bookNode;
            bookNode.pre=temp;
        }
    }

    /**
     * 修改
     */
    public void update(BookNode bookNode){
        if (head.next==null){
            System.out.println("这是一个空链表");
            return;
        }
        BookNode temp=head.next;
        boolean flag=false;
        while (true){
            if (temp==null){
                break;
            }
            if (temp.id== bookNode.id){
                flag=true;
                break;
            }
            temp=temp.next;
        }
        if (flag){
            temp.name=bookNode.name;
            temp.price=bookNode.price;
        }else{
            System.out.println("没有找到节点");
        }
    }

    /**
     * 删除
     */
    public void delete(int id){
        BookNode temp=head;
        boolean flag=false;
        while (true){
            if (temp.next==null){
                break;
            }
            if (temp.next.id==id){
                flag=true;
                break;
            }
            temp=temp.next;
        }
        if (flag){
            if (temp.next.next!=null){
            temp.next.next.pre=temp;
            }
            temp.next=temp.next.next;
        }else{
            System.out.println("没有找到节点");
        }
    }


    /**
     * 遍历
     */
    public void list(){
        BookNode temp=head;
        while (true){
            if (temp.next==null){
                break;
            }
            System.out.println(temp.next);
            temp=temp.next;
        }
    }


}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125
  • 126
  • 127
  • 128
  • 129
  • 130
  • 131
  • 132
  • 133
  • 134
  • 135
  • 136
package exer.linked;

/**
 * 测试
 */
public class DualLinkedListTest {
    public static void main(String[] args) {
        DualLinkedList dualLinkedList=new DualLinkedList();
        BookNode bookNode1=new BookNode(8,"西游记",100);
        BookNode bookNode2=new BookNode(3,"三国演义",200);
        BookNode bookNode3=new BookNode(4,"水浒传",300);
        BookNode bookNode4=new BookNode(5,"红楼梦",400);
//        dualLinkedList.add(bookNode1);
//        dualLinkedList.add(bookNode2);
//        dualLinkedList.add(bookNode3);
//        dualLinkedList.add(bookNode4);
        dualLinkedList.addOrder(bookNode1);
        dualLinkedList.addOrder(bookNode2);
        dualLinkedList.addOrder(bookNode3);
        dualLinkedList.addOrder(bookNode4);
        //dualLinkedList.update(new BookNode(8,"计算机",8888.0));
        //dualLinkedList.delete(2);
        dualLinkedList.list();
    }
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26

三、单向环形链表

在这里插入图片描述
由约瑟夫问题引入：
设编号为1,2…，n的n个人围坐一圈，约定编号为k(1<=k<=n)的人从1开始报数，数到m的那个人出列，它的下一位又从1开始报数，数到m的那个人出列，它的下一位又从1开始报数，数到m的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列。

/**
 * 单向环形链表
 */
public class Boy {
    public  int id;
    public Boy next;

    public Boy(int id) {
        this.id = id;
    }

}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12

/**
 * 单项环形链表相关操作
 */
public class CircleSingleLinkedList {
    //创建头结点
    public Boy first=new Boy(-1);

    /**
     * 创建环形链表
     */
    public void create(int n){
        if (n<1){
            throw new RuntimeException("传入参数不正确");
        }
        //创建一个临时节点
        Boy temp=null;
        for (int i = 1; i <= n; i++) {
            Boy boy=new Boy(i);
            if (i==1){
                first=boy;
                first.next=first;
                temp=first;
            }else{
                temp.next=boy;
                boy.next=first;
                temp=boy;
            }

        }
    }
    /**
     * 遍历环形链表
     */
    public void show(){
        if (first==null||first.id==-1){
            System.out.println("当前环形链表为空");
            return;
        }
        Boy temp=first;
        while (true){
            System.out.println(temp.id);

            if (temp.next==first){
                break;
            }
            temp=temp.next;

        }
    }
    /**
     * 约瑟夫问题
     * 根据用户输入计算小孩出圈的顺序
     * startNo 为k（开始的位置）
     * countNum为数的数（m）
     * nums为总人数
     */
    public void getOrder(int startNo,int countNum,int nums){
        if (first==null||startNo<1||startNo>nums){
            System.out.println("参数输入有误，请重新输入");
            return;
        }
        //创建一个辅助指针，指向最后的节点
        Boy tail=first;
        while (true){
            if (tail.next==first){
                break;
            }
            tail=tail.next;
        }
        //让头部指针和尾部指针根据startNo进行移动
        for (int i = 0; i < startNo-1; i++) {
            first=first.next;
            tail=tail.next;
        }

        while (true){
            if (tail==first){
                break;
            }
            //根据countNum进行移动，然后将节点出圈
            for (int i = 0; i < countNum-1; i++) {
                first=first.next;
                tail=tail.next;
            }
            System.out.printf("小号%d出圈\n",first.id);
            //这是需要将first指针指向出圈节点的下一个
            first=first.next;
            tail.next=first;
        }
        System.out.printf("最后一个为%d\n",first.id);
    }
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
/**
 * 单向环形链表测试
 */
public class CircleSingleLinkedListTest {
    public static void main(String[] args) {
        CircleSingleLinkedList circleSingleLinkedList=new CircleSingleLinkedList();
        circleSingleLinkedList.create(5);
        //circleSingleLinkedList.show();
        circleSingleLinkedList.getOrder(1,3,5);
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/煮酒与君饮/article/detail/823059
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号