链表

发表于 更新于 分类于 阅读次数： Valine：

链表介绍

链表与数组其实都是表的一个，而数组的存储是一个连续的地址空间，如果想要对数组进行插入删除操作，那么加入插入点在最后的位置，时间复杂度为o（1），但是如果插入点在最前面，而由于地址空间连续那么就需要使之后的所有的地址空间向后移动，时间开销较大，但是如果我们对数组进行访问操作，会访问的很快，根据数组的索引即可直接访问，但是链表只能从头节点开始遍历，链表的插入和删除操作比较简单，只需要改变对应位置的next域即可，这是因为链表的存储方式，地址空间不连续，所以进行插入时，其他的地址空间不会放生变化，

链表是有序的列表，内存如下：

image-20220605094900976

链表的各个节点不一定是连续存储的，链表分为有头节点与没有头节点的

单链表

头节点不存放具体的数据，作用是表示单链表的头

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
package 数据结构和算法.链表;

/**
 * @author 21050
 */
public class SingleLinkedList {

    //首先定义节点
    class HeroNode{
        int no;
        String name;
        String nickName;
        HeroNode next;

        public HeroNode(int 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 + '\'' +
                    '}';
        }
    }


    //建立节点，首先建立头节点，但是不存储数据，只是指向下一个位置
    HeroNode head=new HeroNode(0,"","");


    public void addNode(HeroNode heroNode){
        HeroNode temp=head;
        while (temp.next!=null){
            temp=temp.next;
        }
        temp.next=heroNode;
    }

    //显示当前链表
    public void show(){
        HeroNode temp=head.next;
        while (temp!=null){
            System.out.println(temp);
            temp=temp.next;
        }
    }

    HeroNode heroNode1=new HeroNode(1,"haha","heihei");
    HeroNode heroNode2=new HeroNode(2,"ha","hei");
    HeroNode heroNode3=new HeroNode(1,"hdfb","hei873");
    public static void main(String[] args) {
        SingleLinkedList singleLinkedList=new SingleLinkedList();
        singleLinkedList.addNode(singleLinkedList.heroNode1);
        singleLinkedList.addNode(singleLinkedList.heroNode2);
        singleLinkedList.addNode(singleLinkedList.heroNode3);
        singleLinkedList.show();
    }
}

image-20220605104247671

排序插入

现在我们需要提出一个要求，要求这个程序必须按照no的顺序进行插入，并且如果有相同的no则第二个添加的失败，那么我们就需要进行更改添加的方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public void addNode(HeroNode heroNode){
    HeroNode temp=head;
    while (temp.next!=null){
        if (temp.next.no==heroNode.no){
            System.out.println("序号相同，本次加入节点失败");
            return;
        }
        if (temp.next.no>heroNode.no){
            HeroNode temp1=temp.next;
            temp.next=heroNode;
            heroNode.next=temp1;
            return;
        }
        temp=temp.next;
    }
    temp.next=heroNode;

}

image-20220605110454179

修改节点信息

1
2
3
4
5
6
7
8
9
10
//通过no修改节点，这里还可以加上其他的配置，比如判断是否删除成功这个节点等等
public void update(int No){
    HeroNode temp=head;
    while (temp.next!=null){
        temp=temp.next;
        if (temp.no==No){
            temp.name="张三";
        }
    }
}

image-20220605112225842

删除节点

1
2
3
4
5
6
7
8
9
10
//删除节点
public void delete(int no){
    HeroNode temp=head;
    while (temp.next!=null){
        if (temp.next.no==no){
            temp.next=temp.next.next;
        }
        temp=temp.next;
    }
}

image-20220605114058165

疑问

在这个过程中，我们的temp仅仅是一个替代品，为什么改变了temp.next就可以改变head的链表，在

1
HeroNode temp=head;

操作下，temp其实拿到了head的地址，同时传过去的不仅仅是head，还有head.next都传输过去了，这里定义的temp其实是引用数据数据类型。

image-20220605114417807

链表练习

单链表有效的个数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public void getNums(HeroNode head){
    int count=0;
    if (head.next==null){
        System.out.println("链表为空");
    }else {
        HeroNode node=head;
        while (node.next!=null){
            count++;
            node=node.next;
        }
        System.out.println("拥有"+count+"个节点");
    }

}

image-20220606141511242

查找单链表中倒数第k个节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public void getReciprocalNum(int k,HeroNode head){
    //首先得到链表的长度
    int size=getNums(head);
    if (size==0||k>size){
        System.out.println("无效");
        return;
    }
    HeroNode temp=head;
    for (int i=0;i<=size-k;i++){
        temp=temp.next;
    }
    System.out.println(temp.toString());

}

image-20220606143344455

单链表的反转

我们将第一个节点加入到节点之后，然后将第一个节点删除，依次循环类推

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public void reverseLinkedList(HeroNode head) {
        if (head.next == null) {
            System.out.println("无效链表");
            return;
        }
        //建立一个新的头节点
        HeroNode newHead = new HeroNode(0, "", "");

        while (head.next!=null){
            HeroNode heroNode = head.next;
            HeroNode temp=heroNode.next;
            heroNode.next=null;
            HeroNode temp1=newHead.next;
            newHead.next=heroNode;
            newHead.next.next=temp1;
            head.next=temp;
        }
        show(newHead);
    }

其他人的解决方法，此方法巧妙的将添加方法更改到cur上，而不是在新节点上面直接添加

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public void reverseList(HeroNode head){
    if (head.next==null){
        return;
    }
    HeroNode cur=head.next;
    HeroNode next=null;
    HeroNode newHead=new HeroNode(0,"","");
    while (cur!=null){
        next=cur.next;
        //将新节点的下一个节点当作cur的下一个节点
        cur.next=newHead.next;
        //新节点下一个节点相当于插入了cur
        newHead.next=cur;
        cur=next;
    }
    show(newHead);
}

从尾到头打印单链表

先反转，在打印，(⊙﹏⊙)，当然可以

这里展示递归调用的方法

1
2
3
4
5
6
7
8
public void printLinkList(HeroNode head){
    if (head.next==null){
        return;
    }
    HeroNode tempHead=head.next;
    printLinkList(tempHead);
    System.out.println(tempHead);
}

image-20220606171643583

栈调用

我们知道栈是先进后出的

1
2
3
4
5
6
7
8
9
10
11
public void printLinkList(HeroNode head){
    Stack<HeroNode> heroNodes=new Stack<>();
    HeroNode temp=head;
    while (temp.next!=null){
        temp=temp.next;
        heroNodes.add(temp);
    }
    while (heroNodes.size()>0){
        System.out.println(heroNodes.pop());
    }
}

上述的两种方法其实都是将同string重写之后输出的，并没有输出next域，也可以输出next域，但是如果还是想要达到这个效果，就需要对压栈的过程再次细化，这个写起来方便，就这样写喽

tostring方法

1
2
3
4
5
6
7
8
@Override
public String toString() {
    return "HeroNode{" +
            "no=" + no +
            ", name='" + name + '\'' +
            ", nickName='" + nickName + '\'' +
            '}';
}

合并链表，合并之后仍然有序

两个链表如下

image-20220606202324581

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
public static void mergeLinkedList(HeroNode head1, HeroNode head2) {
    HeroNode temp2=head2;
    while (temp2.next!=null){
        HeroNode cur=temp2.next;
        HeroNode next=cur.next;
        cur.next=null;
        head2.next=next;
        //将cur加入head1中
        HeroNode temp1=head1;
        while (temp1.next!=null){
            if (temp1.next.no== cur.no){
                System.out.println("序号重复，本次加入失败");
                break;
            }
            if (temp1.next.no> cur.no){
                cur.next=temp1.next;
                temp1.next=cur;
                break;
            }
            temp1=temp1.next;
        }
        temp1.next=cur;
    }
    show(head1);

}

image-20220606211700745

双向链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Node{
    //定义数据区
    int date;
    Node next;
    Node pre;
    //初始化链表
    public Node(int date) {
        this.date = date;
    }

    @Override
    public String toString() {
        return "Node{" +
                "date=" + date +
                '}';
    }
}

插入节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//我们首先定义一个头节点
static Node  head=new Node(0);
//在最末尾位置插入节点
public void insertNode(Node node){
    Node temp=head;
    while (temp.next!=null){
        temp=temp.next;
    }
    temp.next=node;
    node.pre=temp;
}

//遍历链表
public void showNode(Node head){
    Node temp=head;
    while (temp.next!=null){
        temp=temp.next;
        System.out.println(temp);
    }
}

image-20220607191156373

顺序插入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//顺序插入
public void insertByOrder(Node node){
    Node cur=head;
    while (cur.next!=null){
        cur=cur.next;
        if (node.date==cur.date){
            System.out.println("相同的序号，不允许加入");
        }
        if (node.date<cur.date){
            cur.pre.next=node;
            node.pre=cur.pre;
            node.next=cur;
            cur.pre=node;
            return;
        }

    }
    cur.next=node;
    node.pre=cur;
    
}

删除节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public void deleteNode(int no){
        Node cur=head;
        while (cur.next!=null){
            cur=cur.next;
            //此时我们需要防止这是否为最后一个节点，如果是最后一个节点，小心空指针
            if (cur.date==no){
                //删除最后一个节点
                if (cur.next==null){
                    cur.pre.next=null;
                    cur.pre=null;
                }else {
                cur.pre.next=cur.next;
                cur.next.pre=cur.pre;
                cur.pre=null;
                cur.next=null;
                }
                System.out.println("删除成功");
                return;
            }
        }
        System.out.println("删除失败，没有找到对应的节点信息");
    }

image-20220607195032636

环形链表

约瑟夫问题：

15个教徒和15个非教徒在深海上遇险，必须将一半的人投入海中，其余的人才能幸免于难，于是想了一个办法：30个人围成一圆圈，从第一个人开始依次报数，每数到第九个人就将他扔入大海，如此循环进行直到仅余15个人为止。问怎样排法，才能使每次投入大海的都是非教徒。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Node{
    int data;
    Node next;

    public Node(int data) {
        this.data = data;
    }

    @Override
    public String toString() {
        return "Node{" +
                "data=" + data +
                '}';
    }
}

环形链表的增加

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public void insertByorder(Node node){

        Node cur=first.next;
        if (cur.data== node.data){
            System.out.println("这个节点已经加入了");
            return;
        }
        while (cur.next.data!=first.data){
            if (cur.next.data== node.data){
                System.out.println("这个节点已经加入了");
                return;
            }
            if (cur.next.data>node.data){
                node.next=cur.next;
                cur.next=node;
                return;
            }
            cur=cur.next;
        }
        cur.next=node;
        node.next=first;
    }

image-20220607210336747

环形链表的删除

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
     * @param n 表示循环几次删除一个节点*/
    public void delete(int n) {
        Node cur = first;
        for (int i=0;i<n-1;i++){
            if (i!=0){
                cur=cur.next;
            }
        }
        //此时cur是应该删除的前一个
        System.out.println("我是节点"+cur.next+"我真可怜，要被杀了");
        //此时cur指向被杀节点的前一个节点
        cur.next=cur.next.next;
    }

image-20220607220413046

约瑟夫问题解决

这时候我们改一下删除的方法，加上一个循环，注意这一次循环判断条件要增加

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
 * @param n 表示循环几次删除一个节点*/
public void delete(int n) {
    Node cur = first;
    for (int j = 0; j < 15; j++) {
        for (int i = 0; i < n - 1; i++) {
            if (i != 0||j!=0) {
                cur = cur.next;
            }
        }
        //此时cur是应该删除的前一个
        System.out.println("我是节点" + cur.next + "我真可怜，要被杀了");
        //此时cur指向被杀节点的前一个节点
        cur.next = cur.next.next;
    }
}

image-20220607222738772