数据结构与算法实自我实现-链表

Posted on | In | | 阅读数

前言

学了数据结构之后，就用编程语言去实现它，这样理解才通透。同时地，学会刷题也是很重要，例如现在人尽皆知的leetcode。 我的目标就是进大厂，而必须要过的一关就是数据结构，慢慢学吧~ 行百里者半九十。


我实现数据结构的代码是java，用什么语言不重要，主要是思路正确就可以了。所以你想学习c、c++也是一样的。


然后，这个博客系列是给小白看的，所以我有一些阅读建议：

  1. 我会给出实现思路，先跟着我一起思考，虽然有些地方说的有些拗口，没办法，这是写作的缺点之一，所以要理解每一个地方说的概念后再往下，不然发现看不懂自然而然就“收藏夹吃灰”了
  2. 看懂了不一定会，要自己实现一下，你会发现巨多的坑等着你
  3. 不要急，慢慢来，你可以学会的（真的）

前情回顾：

上一节我们提到了链表，那么我们这一篇就来实现其结构。

链表的定义：

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

2)每个节点包含data域（存放的数据）, next域:指向下一个节点，当next指向null时，可以表明才链表元素是尾结点


单向链表

首先，我们设计一个对象Node，对象里面只含有两个字段，分别是data域和next域

并添加上getter、setter方法，这个代码很简单

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
class Node{
    private String data;
    private Node next;

    public Node(String data, Node next) {
        this.data = data;
        this.next = next;
    }

    public String getData() {
        return data;
    }

    public void setData(String data) {
        this.data = data;
    }

    public Node getNext() {
        return next;
    }

    public void setNext(Node next) {
        this.next = next;
    }

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

接下来，就是设计API了，一个链表，应该拥有插入、删除、打印、获取链表长度等功能

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 传入一个头结点，遍历链表
   public void list(Node head){
       
   }

// 传入头结点以及参数i，删除第i个元素
   public Node delete(Node head, int i){
   
   }

// 传入头结点、参数i，在i-1的元素前面插入,node是要插入的节点
   public void insert(Node head, int i, Node node){
       
   }

// 返回链表的长度
   public int getLength(Node head){
       
   }

首先，我们来讨论一下主要的API的功能：


插入：

我们要实现的功能是，在i元素之前插入某个新节点。如图：

本来第 i 个节点是直接指向第 i+1 个节点的，由于来了新节点，我们就需要更改一下指向的顺序。

我们要做的具体步骤有三个：

① 找到第i个元素的节点

② 将该节点的next域指向我们传入的新节点

③ 将新节点的next域指向第 i+1 个节点


很简单，是不是？

不过，仔细一看上面这三个步骤，事情并没有那么简单。

我们想一想，如果实现了步骤②，那么到了步骤③，我们如何去表示 i 元素的 next 域呢？ 当前状态下， i 元素的 next 域可是新节点噢（步骤②做的事情）。所以我们丢失了原先 i 节点的下一节点，怎么办呢


换个角度想一下，先实现步骤③就可以了。

我们先将新节点指向第 i+1个节点，然后再把 i 节点指向新节点，就可以了（链表当中，顺序很重要）。



删除

而删除的思路跟插入是差不多的，实现的效果是：传入第i个位置的上一个位置，然后删除它下一个节点，再连向下一节点的下一节点。

为什么不直接找到节点然后直接删除呢？因为该链表是单向的，没办法表示“当前节点的上一个节点”，所以我们无法让“上一个节点”与“下一个节点相连”。


所以思路是：从链表头节点一直往下找，找i -1次，就找到了所删除节点的上一节点。


好了，说完思路，我把完整代码贴出来：

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
class singleLinkedList{
    /**
     * 传入一个头结点，遍历链表
     */
    public void list(Node head){
        Node temp = head.getNext();  // 头结点的下一节点

        while (true) {
            if (temp == null) {
                // 找到最后节点,跳出循环
                break;
            }
            System.out.println(temp);
            temp = temp.getNext();
        }
    }

    /**
     * 传入参数i，删除第i个元素
     */
    public Node delete(Node head, int i){

        Node temp = head.getNext();  // 辅助节点, 指向了头结点的下一节点

        for (int j = 1; j < i; j++) {
            if (temp != null){

                temp = temp.getNext();  // 辅助节点往后移动

            }else{  // 说明temp.getNext() == null ，已经到了尾结点
                System.out.println("链表长度不足"+i+",请重新传参");
                return null;
            }
        }

        // 跳出循环，表示找到要删除节点的上一节点

        Node two_next = temp.getNext().getNext();  // 找到下一节点的下一节点，记为two_next

        temp.getNext().setNext(null); // 将下一节点的值设置为空

        temp.setNext(two_next);  // 将当前节点直接指向two_next


        return head;
    }


    /**
     * 传入参数i，在i-1的元素前面插入,node是要插入的节点
     */
    public void insert(Node head, int i, Node node){
        Node temp = head;  // 辅助节点

        for (int j = 1; j < i; j++) {
            if (temp == null) {
                // 下一节点为空，表示链表长度不够
                System.out.println("链表长度不足"+i+",请重新传参");
                break;
            }
            else{
                temp = temp.getNext();
            }
        }

        // 跳出循环时，temp表示要插入节点位置的上一个节点

        Node nextNode = temp.getNext();
        node.setNext(nextNode);
        temp.setNext(node);

    }


    /**
     * 返回链表的长度
     * @return
     */
    public int getLength(Node head){
        int count = 0;
        Node temp = head.getNext();
        while (temp != null){
            temp =  temp.getNext();
            count++;
        }

        return count;
    }
}



环形链表

将单链表中终端结点的指针端由空指针改为指向头结点,就使整个单链表形成一个环,这种头尾相接的单链表称为单循环链表,简称循环链表( circular linked list)。

循环链表如图所示：

跟链表结构没有多大差别，只不过我们判断是否是尾结点的方式由 a.next == null 改成了 a.next == head（头结点）

当next域指向的是头结点时，我们认为当前节点为尾结点。

环形链表的好处：

当我们总是要获取最后一个节点时，可以使用环形链表。

首先实例化一个指向尾结点的变量，这意味着遍历时总是从尾结点开始找，对于前几个元素，只不过把操作数+1；而原本我们想要获取最后一个元素需要操作n次（链表节点个数的大小），而现在，有了环形链表，访问最后一个节点的操作数是1。

但是我们发现，这还是有些不够灵活，如果我们想要获取倒数第二个节点怎么办？

这时候，双向链表就起到了作用……



双向链表

双向链表，就是可以通过两个方向遍历链表，别看这图画的有些复杂，其实就是多了一个pre域（与next域相对的），用于指向上一个节点。

双向链表的优点：

双向链表相对于单链表来说,要更复杂一些,不过,双向链表使得对某个结点的前后结点的操作,带来了方便,可以有效提高算法的时间性能。说白了,就是用空间来换时间。

对于双向链表的操作，也就是多了几步，但原理是一样的。下面举个添加节点的例子表明一下：

步骤①：将node（新节点）的pre域指向temp

步骤②：新节点指向下一节点

步骤③：下一节点的上一节点指向新节点

步骤④：当前节点的下一节点指向node


嗯…好啰嗦好啰嗦，简单来说，就是多了一个pre域，但是指向域的操作顺序是很重要的，不然就发生丢失节点的情况了（参考单向链表）。


添加代码实现：

假设，现在有个新节点node，temp为想要添加位置的前一个位置节点。

1
2
3
4
5
6
7
8
9
10
11
12
    
if (temp.next != null){   // 如果这个节点不是尾结点
    
    temp = node.pre;  // 当前节点下一节点指向node（新节点）
    node.next = temp.next;  // 新节点指向下一节点
    temp.next.pre = node;  // 下一节点的上一节点指向新节点
    node.pre = temp;  // 当前节点的下一节点指向node
    
}else{                  // 如果这个节点是尾结点
    temp.next = node;
    node.pre = temp;
    }



写在后面

这个系列会一直写，后面的还有数组、队列、还有我还没学的二叉树等等。

对于知识点梳理的同时，又创作了一篇博客，还有各位小伙伴点的赞，这给我带来无穷大的动力。

冲冲冲！！