知新_RL

这个屌丝很懒，什么也没留下！

热门标签

数据结构与算法之双向链表_数据结构双向链表、树是否熟悉,数据算法

作者：知新_RL | 2024-06-10 02:20:44

踩

数据结构双向链表、树是否熟悉,数据算法

前言

前文介绍了单向链表，相信大家也了解单向链表是一个怎样的数据结构，除了单向链表，链表还有双向链表。
从名字也可以看出来，双向链表就是不止于从前(头部)向后(尾部)寻址，还可以从后向前寻址，显而易见的是，这样的数据结构，在某些场景，比如从尾部插入，删除等，比单向链表更有效率，相应的，由于每一个结点中存储了两个结点的地址，所以，双向链表比单向链表需要更大的空间，其实，这便是数据结构中空间换时间的思想。
在实际的应用中，并没有绝对最好的数据结构这样的说法，事实上，根据场景的不同，选择合适的数据结构，合理平衡空间与时间是最有益的。

双向链表

对于链表来说，仍然是理解结点以及结点寻址！
以下代码均由java实现：

/**
 * @program: thinking-in-all
 * @description: 双向链表
 * @author: Lucifinil
 * @create: 2019-12-30
 **/
public class TwoWayLinkedList<T> {
      
}

1
2
3
4
5
6
7
8
9
10

Node

对于双向链表的结点，与单向链表的结点相比，其区别就是结点存储两个地址，分别指向前驱和后继。
在这里插入图片描述
使用java来实现：

    private class Node {
        T value;
        Node precursor;
        Node successor;
        public Node(T value, Node precursor, Node successor) {
            this.value = value;
            this.precursor = precursor;
            this.successor = successor;
        }
        Node(T value) {
            this(value, null, null);
        }
        Node() {
            this(null, null, null);
        }
        @Override
        public String toString() {
            return value.toString();
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

属性

从上图的结点，我们很容易能想象到双向链表的样子:

在这里插入图片描述
可以看到，有两个特殊结点head和tail，head只存储后继结点地址，而tail只存储前驱结点地址，中间的所有node都存储前驱和后继结点的地址。
同样的，头结点和尾结点我们可以使用虚拟结点来表示，这样做的好处是：避免了在空链表或者只有一个结点时，head和tail的重叠，以及创建和删除结点时的复杂操作。
我们可以看看其区别，没有虚拟头尾结点：
在这里插入图片描述
我们可以看到，添加一个第一个结点，第二个结点，以及第三个及以后结点是三种不同的情况，究其原因，便是我们需要对头尾结点进行单独处理，而有虚拟头尾结点：

在这里插入图片描述
我们无论添加多少个结点，都是从头尾结点中间添加，不涉及到对头尾结点的操作，唯一的缺点的是多占了两个node的空间，微乎不计…
下面，用代码来实现虚拟头结点和尾结点！

    //虚拟头结点
    private Node dummyHead;   
    //虚拟尾结点结点
    private Node dummyTail;
1
2
3
4

如此简单，如此美妙！
除此之外，元素数量是我们必不可少的属性！

    //链表元素数量
    private int size;
1
2

构造器

其实，链表本身的构造器很简单，因为链表是真正意义上的动态数据结构，它的创建不需要预先设置一个大小，我们需要给其固有的属性赋予初始值，并且让头尾结点指向彼此形成空链表的初始状态：在这里插入图片描述

    public TwoWayLinkedList() {
        dummyHead = new Node();
        dummyTail = new Node();
        dummyHead.successor = dummyTail;
        dummyTail.precursor = dummyHead;
        size = 0;
    }
1
2
3
4
5
6
7

辅助函数

获取元素数量，判空，是否包含元素等是各个数据结构几乎都有的辅助函数：

获取元素数量：

    //获取链表元素数量
    public int size() {
        return size;
    }
1
2
3
4

判断链表是否为空：

    //获取链表是否为空链表
    public boolean isEmpty() {
        return size == 0;
    }
1
2
3
4

这两个函数很简单，获得元素数量，直接返回size就可以了，我们需要注意的是对size的维护，判断是否为空，只要判断size是否尾0。
是否包含元素e ：

    //判断链表中是否包含元素e
    public boolean contains(T e) {
        Node cur = dummyHead.successor;
        while (cur != null) {
            if (cur.value.equals(e)) {
                return true;
            }
            cur = cur.successor;
        }
        return false;
    }
1
2
3
4
5
6
7
8
9
10
11

这里我们需要注意的是，是否包含元素e这个方法，虽然双向链表相较于单向链表增加了尾结点，但事实上这个方法我们不知道元素e在链表更靠近头部还是尾部，所以，这里我沿用了单向链表的实现，从头部遍历，直到找到该元素或者遍历全部，当然，我们也可以选择从尾部遍历，甚至，两端一起遍历：

    public boolean contains(T e) {
        Node cur1 = dummyHead.successor;
        Node cur2 = dummyTail.precursor;
        while (true) {
            if (cur1.value.equals(e)) {
                return true;
            }
            if (cur2.value.equals(e)){
                return true;
            }
            cur1 = cur1.successor;
            if (cur1.equals(cur2)){
                return false;
            }
            cur2 = cur2.precursor;
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

增加与删除结点

其实，看到这里，很容易可以想到双向链表的增删结点怎么完成的，无非是在单向链表的基础上，多改变一次结点的指向地址！
增加结点：
在这里插入图片描述
从上图可以看到，增加结点，无论是头部还是尾部增加，都是改变新增结点的前驱结点和后继结点的地址指向，只不过与单向链表不同的是，它是改变两个地址，而且它的遍历是可选择的，不再是一定要通过头部来寻址，它也可以通过尾部来寻址。
越靠近头部的便从头部开始遍历，越靠近尾部的便从尾部开始遍历，这样可以保证寻址效率更高：

    public void add(int index, T e) {
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("Add failed.Illegal index.");
        }
        if (index <= size / 2) {
            Node prev = dummyHead;
            for (int i = 0; i < index; i++) {
                //获得新增结点的前驱
                prev = prev.successor;
            }
            //创建新增结点
            Node node = new Node(e);
            //获得新增结点的后继
            Node succ = prev.successor;

            //为了结构清晰，这里把新增操作的三个结点都表示出来

            //使新增结点的后继指向succ
            node.successor = succ;
            //使新增结点的前驱指向prev
            node.precursor = prev;

            //此刻新增结点已经添加进去了，但是其前驱和后继的地址还有待修正

            //修正前驱结点，使其后继指向node，而非succ
            prev.successor = node;
            //修正后继结点，使其前驱指向node，而非prev
            succ.precursor = node;

        } else {
            Node succ = dummyTail;
            for (int i = size - 1; i > index; i--) {
                //同上，只是从尾部开始寻址！
                succ = succ.precursor;
            }
            Node node = new Node(e);
            Node prev = succ.precursor;

            node.precursor = prev;
            node.successor = succ;

            succ.precursor = node;
            prev.successor = node;
        }
        size++;
    }
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

代码中的关键步骤，已经给出说明，这里不再赘述！其实上述代码是可以简化的，数据结构与算法的学习，在前期不太熟悉的时候，写清晰每一步，有助于我们的理解！不过，我们很容易地观察到，除了找到三个相关结点(新增结点，前驱后继)的方式有所差异，后续操作完全相同，优化后的代码为：

       public void add(int index, T e) {
            if (index < 0 || index > size) {
                throw new IllegalArgumentException("Add failed.Illegal index.");
            }
            Node prev;
            //创建新增结点
            Node node = new Node(e);
            Node succ;
            if (index <= size / 2) {
                prev = dummyHead;
                for (int i = 0; i < index; i++) {
                    //获得新增结点的前驱
                    prev = prev.successor;
                }
                //获得新增结点的后继
                succ = prev.successor;
            } else {
                succ = dummyTail;
                for (int i = size; i > index; i--) {
                    //同上，只是从尾部开始寻址！
                    //获得新增结点的后继
                    succ = succ.precursor;
                }
                //获得新增结点的前驱
                prev = succ.precursor;
            }

            //为了结构清晰，这里把新增操作的三个结点都表示出来

            //使新增结点的后继指向succ
            node.successor = succ;
            //使新增结点的前驱指向prev
            node.precursor = prev;

            //此刻新增结点已经添加进去了，但是其前驱和后继的地址还有待修正

            //修正前驱结点，使其后继指向node，而非succ
            prev.successor = node;
            //修正后继结点，使其前驱指向node，而非prev
            succ.precursor = node;

            size++;
        }
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

删除结点：
在这里插入图片描述
从图片可以看到，被删除结点，所有与其相关引用全部置空，其前驱与后继建立相互引用！
代码如下：

     public T remove(int index){
        if (isEmpty()) {
            throw new IllegalArgumentException("Remove failed.Linklist is empty.");
        }
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("Remove failed.Illegal index.");
        }
        if (index <= size / 2) {
            Node prev = dummyHead;
            for (int i = 0; i < index; i++) {
                //获得待删除结点的前驱
                prev = prev.successor;
            }

            //获得待删除结点
            Node node = prev.successor;
            //获得待删除结点的后继
            Node succ = node.successor;

            //同样的，我们获得删除操作所涉及的三个结点，更加清晰地进行结点的删除操作

            //将待删除结点的前驱结点的后继指向待删除结点的后继结点
            //这句话需要好好理解，也就是说前驱结点跳过了待删除结点指向后继结点，在图中可以看到
            prev.successor = succ;
            //同样的，将待删除结点的后继结点的前驱指向待删除结点的前驱结点
            //经过这样两步，这样结点就在链表中被"剔除"了
            succ.precursor = prev;

            //由于java的内存是GC管理，但存在引用的对象，是可能继续占用内存的
            //养成良好的编码习惯，将不适用的对象引用置空
            node.precursor = null;
            node.successor = null;
            size--;
            return node.value;
        }else {
            Node succ = dummyTail;
            for (int i = size - 1; i > index; i--) {
                //同理
                succ = succ.precursor;
            }
            Node node = succ.precursor;
            Node prev = node.precursor;

            node.precursor = null;
            node.successor = null;

            prev.successor = succ;
            succ.precursor = prev;
            size--;
            return node.value;
        }
    }
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

代码中的关键步骤已经用注释说明，这样我们需要注意的是，对于链表中管理索引的步骤，应当小心警惕！
另外，经过观察可以看到，文中有大量重复代码，经过优化后：

       public T remove(int index) {
            if (isEmpty()) {
                throw new IllegalArgumentException("Remove failed.Linklist is empty.");
            }
            if (index < 0 || index >= size) {
                throw new IllegalArgumentException("Remove failed.Illegal index.");
            }
            //我们获得删除操作所涉及的三个结点，更加清晰地进行结点的删除操作
            Node prev;
            Node node;
            Node succ;
            if (index <= size / 2) {
                prev = dummyHead;
                for (int i = 0; i < index; i++) {
                    //获得待删除结点的前驱
                    prev = prev.successor;
                }
                //获得待删除结点
                node = prev.successor;
                //获得待删除结点的后继
                succ = node.successor;
            } else {
                succ = dummyTail;
                for (int i = size-1 ; i > index; i--) {
                    //同理
                    succ = succ.precursor;
                }
                node = succ.precursor;
                prev = node.precursor;
            }

            //将待删除结点的前驱结点的后继指向待删除结点的后继结点
            //这句话需要好好理解，也就是说前驱结点跳过了待删除结点指向后继结点，在图中可以看到
            prev.successor = succ;
            //同样的，将待删除结点的后继结点的前驱指向待删除结点的前驱结点
            //经过这样两步，这样结点就在链表中被"剔除"了
            succ.precursor = prev;

            //由于java的内存是GC管理，但存在引用的对象，是可能继续占用内存的
            //养成良好的编码习惯，将不适用的对象引用置空
            node.precursor = null;
            node.successor = null;
            size--;
            return node.value;
        }
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

代码的优化，说明了一个关键点，从图中我们也能观察到这个结论，那就是删除结点，除了遍历方式不同，删除结点的方式，修正前驱后继结点引用的方式都是相同的！

查改元素

到了这样，我觉得小伙伴们想到修改与查询元素是very easy滴，上图！

在这里插入图片描述
从图上，我们可以看到双向链表的修改与单向链表几乎是一样的，不同的只是双向链表寻址的方式可以从尾部开始遍历，结合上文的增删结点，我们可以得到查改的代码：
查询：

public T get(int index ){
        if (isEmpty()) {
            throw new IllegalArgumentException("Get failed.Linklist is empty.");
        }
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("Get failed.Illegal index.");
        }
        Node cur;
        if (index <= size / 2) {
            cur = dummyHead.successor;
            for (int i = 0; i < index; i++) {
                cur = cur.successor;
            }
        } else {
            cur = dummyTail.precursor;
            for (int i = size-1; i >index ; i--) {
                cur = cur.precursor;
            }
        }
        return cur.value;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

修改：

    public void set(int index, T e) {
        if (isEmpty()) {
            throw new IllegalArgumentException("Set failed.Linklist is empty.");
        }
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("Set failed.Illegal index.");
        }
        Node cur;
        if (index <= size / 2) {
            cur = dummyHead.successor;
            for (int i = 0; i < index; i++) {
                cur = cur.successor;
            }
        } else {
            cur = dummyTail.precursor;
            for (int i = size-1; i >index ; i--) {
                cur = cur.precursor;
            }
        }
        cur.value = e;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

头尾操作

既然双向链表头部和尾部的操作效率都是O(1),我们可以利用其特性，复用上文实现的函数，实现对头尾的crud操作：
头部操作：

    public void addFirst(T e){
        add(0,e);
    }
    public T removeFirst(){
        return remove(0);
    }
    public T getFirst(){
        return get(0);
    }
    public void setFirst(T e){
        set(0,e);
    }
1
2
3
4
5
6
7
8
9
10
11
12

尾部操作：

     public void addLast(T e) {
        add(size , e);
    }

    public T removeLast() {
        return remove(size-1);
    }

    public T getLast() {
        return get(size-1 );
    }

    public void setLast(T e) {
        set(size-1 , e);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

因为添加操作是在index所在位置添加，在尾部添加其实是对一个不存在的元素进行添加，该位置是index等于size的地方！
我相信，小伙伴们对这种头部和尾部的操作一定不会陌生！因为栈，队列等结构便是涉及头部尾部的操作！
我们可以使用双向链表封装自己的栈和队列等！

完整代码

以下代码已经经过测试，小伙伴们放心食用，不要忘了点赞哟！–来自帅帅的路西菲尔：）

    package com.lucifer.linkedlist;

    /**
     * @program: thinking-in-all
     * @description: 双向链表
     * @author: Lucifinil
     * @create: 2019-12-30
     **/
    public class TwoWayLinkedList<T> {

        private class Node {
            T value;
            Node precursor;
            Node successor;

            Node(T value, Node precursor, Node successor) {
                this.value = value;
                this.precursor = precursor;
                this.successor = successor;
            }

            Node(T value) {
                this(value, null, null);
            }

            Node() {
                this(null, null, null);
            }

            @Override
            public String toString() {
                return value.toString();
            }
        }

        //虚拟头结点
        private Node dummyHead;
        //虚拟尾结点结点
        private Node dummyTail;
        //链表元素数量
        private int size;

        public TwoWayLinkedList() {
            dummyHead = new Node();
            dummyTail = new Node();
            dummyHead.successor = dummyTail;
            dummyTail.precursor = dummyHead;
            size = 0;
        }

        //获取链表元素数量
        public int size() {
            return size;
        }

        //获取链表是否为空链表
        public boolean isEmpty() {
            return size == 0;
        }

        public boolean contains(T e) {
            Node cur1 = dummyHead.successor;
            Node cur2 = dummyTail.precursor;
            while (true) {
                if (cur1.value.equals(e)) {
                    return true;
                }
                if (cur2.value.equals(e)) {
                    return true;
                }
                cur1 = cur1.successor;
                if (cur1.equals(cur2)) {
                    return false;
                }
                cur2 = cur2.precursor;
            }
        }

        public void add(int index, T e) {
            if (index < 0 || index > size) {
                throw new IllegalArgumentException("Add failed.Illegal index.");
            }
            Node prev;
            //创建新增结点
            Node node = new Node(e);
            Node succ;
            if (index <= size / 2) {
                prev = dummyHead;
                for (int i = 0; i < index; i++) {
                    //获得新增结点的前驱
                    prev = prev.successor;
                }
                //获得新增结点的后继
                succ = prev.successor;
            } else {
                succ = dummyTail;
                for (int i = size; i > index; i--) {
                    //同上，只是从尾部开始寻址！
                    //获得新增结点的后继
                    succ = succ.precursor;
                }
                //获得新增结点的前驱
                prev = succ.precursor;
            }

            //为了结构清晰，这里把新增操作的三个结点都表示出来

            //使新增结点的后继指向succ
            node.successor = succ;
            //使新增结点的前驱指向prev
            node.precursor = prev;

            //此刻新增结点已经添加进去了，但是其前驱和后继的地址还有待修正

            //修正前驱结点，使其后继指向node，而非succ
            prev.successor = node;
            //修正后继结点，使其前驱指向node，而非prev
            succ.precursor = node;

            size++;
        }

            public T remove(int index) {
                if (isEmpty()) {
                    throw new IllegalArgumentException("Remove failed.Linklist is empty.");
                }
                if (index < 0 || index >= size) {
                    throw new IllegalArgumentException("Remove failed.Illegal index.");
                }
                //我们获得删除操作所涉及的三个结点，更加清晰地进行结点的删除操作
                Node prev;
                Node node;
                Node succ;
                if (index <= size / 2) {
                    prev = dummyHead;
                    for (int i = 0; i < index; i++) {
                        //获得待删除结点的前驱
                        prev = prev.successor;
                    }
                    //获得待删除结点
                    node = prev.successor;
                    //获得待删除结点的后继
                    succ = node.successor;
                } else {
                    succ = dummyTail;
                    for (int i = size-1 ; i > index; i--) {
                        //同理
                        succ = succ.precursor;
                    }
                    node = succ.precursor;
                    prev = node.precursor;
                }
    
                //将待删除结点的前驱结点的后继指向待删除结点的后继结点
                //这句话需要好好理解，也就是说前驱结点跳过了待删除结点指向后继结点，在图中可以看到
                prev.successor = succ;
                //同样的，将待删除结点的后继结点的前驱指向待删除结点的前驱结点
                //经过这样两步，这样结点就在链表中被"剔除"了
                succ.precursor = prev;
    
                //由于java的内存是GC管理，但存在引用的对象，是可能继续占用内存的
                //养成良好的编码习惯，将不适用的对象引用置空
                node.precursor = null;
                node.successor = null;
                size--;
                return node.value;
            }

        public void set(int index, T e) {
            if (isEmpty()) {
                throw new IllegalArgumentException("Set failed.Linklist is empty.");
            }
            if (index < 0 || index >= size) {
                throw new IllegalArgumentException("Set failed.Illegal index.");
            }
            Node cur;
            if (index <= size / 2) {
                cur = dummyHead.successor;
                for (int i = 0; i < index; i++) {
                    cur = cur.successor;
                }
            } else {
                cur = dummyTail.precursor;
                for (int i = size - 1 ; i > index; i--) {
                    cur = cur.precursor;
                }
            }
            cur.value = e;
        }

        public T get(int index) {
            if (isEmpty()) {
                throw new IllegalArgumentException("Get failed.Linklist is empty.");
            }
            if (index < 0 || index >= size) {
                throw new IllegalArgumentException("Get failed.Illegal index.");
            }
            Node cur;
            if (index <= size / 2) {
                cur = dummyHead.successor;
                for (int i = 0; i < index; i++) {
                    cur = cur.successor;
                }
            } else {
                cur = dummyTail.precursor;
                for (int i = size - 1; i > index; i--) {
                    cur = cur.precursor;
                }
            }
            return cur.value;
        }

        public void addFirst(T e) {
            add(0, e);
        }

        public T removeFirst() {
            return remove(0);
        }

        public T getFirst() {
            return get(0);
        }

        public void setFirst(T e) {
            set(0, e);
        }

        public void addLast(T e) {
            add(size, e);
        }

        public T removeLast() {
            return remove(size - 1);
        }

        public T getLast() {
            return get(size - 1);
        }

        public void setLast(T e) {
            set(size - 1, e);
        }

        @Override
        public String toString() {
            StringBuilder res = new StringBuilder();
            res.append("head [ ");
            Node cur = dummyHead.successor;
            for (int i = 0; i < size; i++) {
                res.append(cur.toString()).append(" <-> ");
                cur = cur.successor;
            }
            res.append("tail ]");
            return res.toString();
        }
    }


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
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259

总结

链表的形式多种多样，不止于此，除了这样的双向链表，还有单向环链表，双向环链表等等。
除了前文提到的使用循环遍历来寻址，链表和树这样的动态结构，是具有递归性质的，我们可以使用递归来实现。
其实，就算是基础的数据结构，我们在剖析与实现的过程中，也会学习到一些思想，对于双向链表来说，以空间换时间就是对于单向链表效率的进一步提升，当然，除了这样的思路，数据结构和算法，还有许许多多的方法和技巧，我觉得这就是数据结构与算法的魅力所在。
最后，今天是2020年的最后一天，希望我与小伙伴们以及我爱的人们都能身体健康，万事如意！也期待未来的一年能得到更好的发展，能将学习作为自己的事业坚持下去！
我是帅气的路西菲尔，期待与你一同成长：）
如有不正，敬请指出，原文来自路西菲尔https://blog.csdn.net/csdn_1364491554/article/details/103768706！

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/知新_RL/article/detail/696798