Java数据结构之链表

清疚 2024-04-01 10:12 62阅读 0赞

**目录**

一.单链表

1.单链表的介绍和内存布局

2.单链表的添加和遍历

3.单链表的插入

4.单链表的删除

二.双向链表

1.添加节点

2.遍历节点

3.插入节点

4.删除结点

5.测试

三.单向环形链表

1.问题的引出

编辑

2.构建环形链表

1.创建结点

3.测试

3.约瑟夫问题代码的实现

--------------------

## 一.单链表 ##

### 1.单链表的介绍和内存布局 ###

![2f3aca997e14421bb4aced7b44bc651e.png][]

![063cc141661b4c83b0a7df68c6b40da9.png][]

小结:  
1)链表是以节点的方式来存储  
2)每个节点包含data域, next域:指向下一个节点.  
3)如图:发现链表的各个节点不一定是连续存储.  
4)链表分带头节点的链表和没有头节点的链表，根据实际的需求来确定

### 2.单链表的添加和遍历 ###

添加包括头插法和尾插法:头插法十分的方便

public class LinkListDemo {
        public static void main(String[] args) {
            SingleLinkedList list = new SingleLinkedList();
            list.addByHead(new DataNode(1));
            list.addByHead(new DataNode(4));
            list.addByHead(new DataNode(6));
            list.addByHead(new DataNode(9));
            list.list();
    
    
        }
    }
    
    class SingleLinkedList {
        private DataNode head = new DataNode(0);
    
        //添加链表(尾插法)
        public void add(DataNode newNode) {
            DataNode temp = head;
            while (temp.next != null) {
                temp = temp.next;
            }
            temp.next = newNode;
            head.id++;
    
        }
        //添加链表(头插法)
        public void addByHead(DataNode newNode){
            newNode.next=head.next;
            head.next=newNode;
            head.id++;
    
        }
    
    
        //遍历节点
        public void list() {
            if (head.next == null) {
                System.out.println("链表为空");
                return;
            }
            System.out.println("此链表共有"+head.id+"个结点");
            DataNode temp = head;
            while (temp.next != null) {
                temp = temp.next;
                System.out.println(temp);
            }
    
    
        }
    
    
    
    }
    
    class DataNode {
        public Integer id;
        public DataNode next;
    
        public DataNode(Integer id) {
            this.id = id;
        }
    
        @Override
        public String toString() {
            return "DataNode{" +
                    "id=" + id +
                    '}';
        }
    }

### 3.单链表的插入 ###

从单链表插入一个结点的思路:  
1.首先找到新添加的节点的位置,是通过辅助变量(指针),通过遍历来搞定

2.新的节点.next=temp.next

3.将temp.next=新的节点

//插入一个新节点
        public void insert(DataNode newNode, int place) {
            DataNode temp = head;
            if(place>head.id||place<1){
                System.out.println("插入的位置过大或过小");
                return;
            }
            for (int i = 1; i < place; i++) {
                temp = temp.next;
            }
            newNode.next = temp.next;
            temp.next = newNode;
            head.id++;
    
    
        }

### 4.单链表的删除 ###

从单链表中删除一个节点的思路  
1.我们先找到需要删除的这个节点的前一个节点temp

2. temp.next =temp.next.next

3.被删除的节点，将不会有其它引用指向，会被垃圾回收机制回收

public void delete(int place){
            DataNode temp=head;
            if(place>head.id||place<1){
                System.out.println("插入的位置过大或过小");
                return;
            }
            for (int i=1;i<place;i++){
                temp=temp.next;
            }
            temp.next=temp.next.next;
            head.id--;
    
        }

## 二.双向链表 ##

**双向链表的示意图:**

![d45f3f03883b46308367a69cd6c8821b.png][]

分析双向链表的遍历，添加，修改，删除的操作思路

代码实现

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;

### 1.添加节点 ###

class DoubleLinkList {
        private DataNode head = new DataNode(0);
    
    
        public DataNode getHead() {
            return head;
        }
       //尾插法
        public void addNode(DataNode node) {
            DataNode temp = head;
            while (temp.next != null) {
                temp = temp.next;
    
            }
            temp.next = node;
            node.pre = temp;
            head.data++;
    
        }
        //头插法
        public void addNodeByHead(DataNode node) {
            node.next = head.next;
            node.pre = head;
            head.next = node;
            head.data++;
    
        }
    }

头插法与尾插法打印结点的顺序不一样,尾插法是添加顺序打印,头插法是逆序打印

### 2.遍历节点 ###

public void list() {
            DataNode temp = head;
            if (head.next == null) {
                System.out.println("链表为空");
                return;
            }
            System.out.println("总共含有" + head.data + "个结点");
            while (temp.next != null) {
                temp = temp.next;
                System.out.println(temp.data);
            }
        }

### 3.插入节点 ###

//插入一个新节点
        public void insert(DataNode newNode, int place) {
            DataNode temp = head;
            if (place > head.data || place < 1) {
                System.out.println("插入的位置过大或过小");
                return;
            }
            for (int i = 1; i < place; i++) {
                temp = temp.next;
            }
            newNode.next = temp.next;
            newNode.next.pre = newNode;
            temp.next = newNode;
            newNode.pre = temp;
    
            head.data++;
    
        }

### 4.删除结点 ###

//删除指定位置的结点
        public void delete(int place) {
            DataNode temp = head;
            if (place > head.data || place < 1) {
                System.out.println("插入的位置过大或过小");
                return;
            }
            for (int i = 0; i < place; i++) {
                temp = temp.next;
            }
            temp.pre.next = temp.next;
            temp.next.pre = temp.pre;
            head.data--;
    
        }

### 5.测试 ###

public class DoubleLinkListDemo {
        public static void main(String[] args) {
            DoubleLinkList doubleLinkList = new DoubleLinkList();
            doubleLinkList.addNode(new DataNode(1));
            doubleLinkList.addNode(new DataNode(2));
            doubleLinkList.addNode(new DataNode(3));
            doubleLinkList.list();
            doubleLinkList.insert(new DataNode(4), 2);
            doubleLinkList.list();
            doubleLinkList.delete(2);
            doubleLinkList.list();
            System.out.println("------------------");
            DoubleLinkList doubleLinkList2 = new DoubleLinkList();
            doubleLinkList2.addNodeByHead(new DataNode(1));
            doubleLinkList2.addNodeByHead(new DataNode(2));
            doubleLinkList2.addNodeByHead(new DataNode(3));
            doubleLinkList2.list();
    
    
        }
    }

**打印结果**

> 总共含有3个结点  
> 1  
> 2  
> 3  
> 总共含有4个结点  
> 1  
> 4  
> 2  
> 3  
> 总共含有3个结点  
> 1  
> 2  
> 3  
> \------------------  
> 总共含有3个结点  
> 3  
> 2  
> 1

## 三.单向环形链表 ##

### 1.问题的引出 ###

**约瑟夫问题:**

Josephu(约瑟夫、约瑟夫环)问题  
Josephu问题为:设编号为1，2，… n的n个人围坐一圈，约定编号为k(1<=k<=n)的人从1开始报数，数到m的那个人出列，它的下一位又从1开始报数，数到m的那个人又出列，以此类推，直到所有人出列为止，由此产生一个出队编号的序列。

提示:用一个不带头结点的循环链表来处理Josephu问题:先构成一个有n个结点的单循环链表，然后由k结点起从1开始计数，计到m时，对应结点从链表中删除，然后再从被删除结点的下一个结点又从1开始计数，直到最后一个结点从链表中删除算法结束。

### ![841f38012c834ba8ab90101e5f1b0168.png][] ###

### 2.构建环形链表 ###

构建一个单向的环形链表思路  
1.先创建第一个节点,让first指向该节点，并形成环形  
2.后面当我们每创建一个新的节点，就把该节点，加入到已有的环形链表中即可.

遍历环形链表  
1.先让一个辅助指针(变量)curBoy，指向first节点  
2.然后通过一个while循环遍历该环形链表即可curBoy.next == first结束

#### 1.创建结点 ####

//创建结点
    class Node {
        public Integer id;
        public Node next;
    
        public Node(Integer id) {
            this.id = id;
        }
    
    
    }

2.创建环形链表

//创建环形链表
    class CircleSingleLinkList {
        private Node first;
    
        public Node getFirst() {
            return first;
        }
    
        //添加
        public void add(int nums) {
            if (nums < 1) {
                System.out.println("nums的值不正确");
                return;
            }
            Node temp = null;
            for (int i = 1; i <= nums; i++) {
                Node node = new Node(i);
                if (i == 1) {
                    first = node;
                    first.next = first;
                    temp = node;
                } else {
                    temp.next = node;
                    node.next = first;
                    temp = node;
    
                }
    
    
            }
    
        }
    
        public void list() {
            Node temp = first;
            if (first == null) {
                System.out.println("链表为空");
                return;
            }
            do {
                System.out.println(temp.id);
                temp = temp.next;
            } while (temp != first);
        }
    
    
    }

#### 3.测试 ####

public class LinkCircleList {
        public static void main(String[] args) {
            CircleSingleLinkList list = new CircleSingleLinkList();
            list.add(10);
            list.list();
    
        }
    }

输出结果:

> 1  
> 2  
> 3  
> 4  
> 5  
> 6  
> 7  
> 8  
> 9  
> 10

### 3.约瑟夫问题代码的实现 ###

根据用户的输入，生成一个小孩出圈的顺序

n= 5,即有5个人

k=1,从第一个人开始报数

m = 2,数2下  
需求创建一个辅助指针(变量) helper,事先应该指向环形链表的最后这个节点.  
补充:小孩报数前，先让first和helper移动k-1次  
2.当小孩报数时，让first和helper指针同时的移动m - 1次这时就可以将first指向的小孩节点出圈  
first = first.next  
helper.next =first  
原来first指向的节点就没有任何引用，就会被回收  
出圈的顺序:  
2->4->1->5->3

//创建环形链表
    class CircleSingleLinkList {
        private Node first;
    
        public Node getFirst() {
            return first;
        }
    
    //根据用户的输入,设定小孩出圈的顺序
        public void outCircle(int startNo, int countNum, int size) {
    //当链表为空或者起始位置大于结点的个数时,是错误的
            if (first == null || startNo < 1 || startNo > size) {
                System.out.println("参数输入有误");
                return;
            }
    //创建一个helper 指针,使他指向first指针的上一个指针位置
            Node helper = first;
            while (helper.next != first) {
                helper = helper.next;
            }
    //确定startNo的位置,first和helper同时移动
            for (int i = 0; i < startNo - 1; i++) {
                first = first.next;
                helper = helper.next;
            }
    //每次移动countNum-1个位置,并将此位置的数据输出,并将此结点删除,
    //然后将结点的个数-1,直到结点的个数为0的时候,说明所有的人都出圈了
            while (size != 0) {
                for (int i = 0; i < countNum - 1; i++) {
                    first = first.next;
                    helper = helper.next;
                }
                System.out.println(first.id);
                first = first.next;
                helper.next = first;
                size--;
    
    
            }
    
    
        }
    }

**测试**

public class LinkCircleList {
        public static void main(String[] args) {
            CircleSingleLinkList list = new CircleSingleLinkList();
            list.add(5);
            list.outCircle(1, 2, 5);
    
        }
    }

**输出结果**

> 2  
> 4  
> 1  
> 5  
> 3

[2f3aca997e14421bb4aced7b44bc651e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/b10f834e63c64c1894a832d35b8759a6.png
[063cc141661b4c83b0a7df68c6b40da9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/41eb9dc2010541bebd5de5754580bfcc.png
[d45f3f03883b46308367a69cd6c8821b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/9614dc1ff5424c44b13e235a144fbc74.png
[841f38012c834ba8ab90101e5f1b0168.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/c0c7fbd0f0f249839cc9719d1ab3d464.png