CoderHann

双向链表的实现

发表于 | 分类于 ， | | 阅读次数

双链表简介


双链表的结构如上，跟单链表相比只是增加了结点的向前引用，下面简单过一下相关双链表的构成元素：
结点：构成双链表的基本单元，每个结点都有一个data区和两个结点指向区。data区就是存放数据的地方，一般存储基本类型数据或者引用对象的地址，两个结点previous,next分别指向前一个结点地址和下一个结点的地址。
头结点：首结点，指向双链表中的第一个结点。
尾结点：指向双链表中的最后一个结点。
链表长度：记录链表中存在的结点个数，即我们存储的数据个数。

双链表的实现

双链表相比单链表只是增加了向前结点的引用构成双向结构，整体来看跟单链表保持一致。双链表的优势体现在获取某个结点的前一个结点提供了便利。建议在了解双链表之前先看下单链表的基本实现，以便自己区分两者的细微区别。由于双链表和单链表结构保持一致，该博客主要流程仍然使用java语言进行讲解。

结点类的创建

创建链表的基本单元结点类跟单链表结点类相差不大，该类提供了数据存储区和前后接点指向区，以及便捷的构造函数：

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
// DoubleLinkedList.java
// 结点类Node<E>
class Node<E> {
    /**
     * 数据区
     */
    public E data;
    /**
     * 前一个结点引用
     */
    public Node<E> previous;
    /**
     * 下一个结点引用
     */
    public Node<E> next;
    public Node(E e) {
        data = e;
        previous = null;
        next = null;
    }
    /**
     * 判断该结点后是否有下一个结点
     * @return
     */
    public boolean hasNext() {
        return this.next != null;
    }
    /**
     * 判断该结点是否有前置结点
     * @return
     */
    public boolean hasPrevious() {
        return this.previous != null;
    }
}

双链表类的创建

跟单链表一样该模块实现数据的添加、删除、打印，反转等功能，下面是DoubleLinkedList的主要成员变量的介绍：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// DoubleLinkedList.java
// class DoubleLinkedList<E>
public class DoubleLinkedList<E> {
    /**
     * 存储结点数量
     */
    private int length;
    /**
     * 头结点引用
     */
    private Node<E> header;
    /**
     * 尾结点引用
     */
    private Node<E> footer;
}

添加功能
添加方法分为了两种，一种是直接在链表尾部添加一个数据，另一个是在指定位置结点的后面添加一个数据。

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
/**
 * 在链表最后的位置添加对象
 * @param e 泛型对象
 */
public void add(E e) {
    Node<E> indexNode = footer;
    try {
        addElement(indexNode,new Node<>(e));
    } catch (Exception e1) {
        e1.printStackTrace();
    }
}
/**
 * 在index位置的对象后面添加对象
 * @param index 索引从0开始，1表示header
 * @param e 泛型对象
 */
public void add(int index,E e) {
    Node<E> indexNode = null;
    try {
        indexNode = getNode(index);
        addElement(indexNode,new Node<>(e));
    } catch (Exception e1) {
        e1.printStackTrace();
    }
}
/**
 * 添加对象的集中处理代码块
 * @param frontElement 在这个对象上执行添加操作
 * @param element 要添加的对象
 */
private void addElement(Node<E> frontElement,Node<E> element) throws Exception{
    if (element.data == null) {
        throw new Exception("添加数据为空");
    }
    if (frontElement == null) {
        if (header != null) { //插入位置为0，链表不为空
            element.next = header;
            header.previous = element;
            header = element;
        } else { //链表长度为0，在首位添加数据
            header = element;
        }
    } else {
        element.next = frontElement.next;
        if (frontElement.hasNext()) {
            frontElement.next.previous = element;
        }
        frontElement.next = element;
        element.previous = frontElement;
    }
    if (!element.hasNext()) {
        footer = element;
    }
    length++;
}

相比于单链表private void addElement(Node<E> frontElement,Node<E> element)这个核心处理方法有点变化，就是要将previous的更改处理好。主要体现在:

1
2
3
4
element.next = frontElement.next;
frontElement.next.previous = element;
frontElement.next = element;
element.previous = frontElement;

删除功能
删除功能也提供了两种方式：一个将index所在的数据删除，另一种是将对象地址相同的对象删除。代码如下请自行对比与单链表的不同处理：

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
/**
 * 链表的删除操作 索引
 * @param index 将要删除的对象索引 （1-length）
 * @return 删除掉的对象
 */
public E delete(int index) {
    if (index < 1 || index > this.length) {
        return null;
    }
    Node<E> deletedNode = null;
    Node<E> indexNode = header;
    while (index > 0) {
        if (index == 1) {
            deletedNode = deleteElement(indexNode.previous,indexNode);
            break;
        }
        index--;
        indexNode = indexNode.next;
    }
    return deletedNode.data;
}
/**
 * 链表的删除操作 指定对象
 * @param e 将要删除的对象
 * @return 删除掉的对象
 */
public E delete(E e) {
    Node<E> deletedNode = null;
    Node<E> indexNode = header;
    while (indexNode != null) {
        if (indexNode.data == e) {
            deletedNode = deleteElement(indexNode.previous,indexNode);
            break;
        }
        indexNode = indexNode.next;
    }
    return deletedNode.data;
}
/**
 * 删除操作集中处理
 * @param frontElement 前一个对象Node
 * @param element 要删除的对象Node
 * @return 删除掉的对象Node
 */
private Node<E> deleteElement(Node<E> frontElement,Node<E> element) {
    Node<E> deletedNode = element;
    if (frontElement == null) {
        header = element.next;
        if (header != null) {
            header.previous = null;    
        }
        
    } else {
        frontElement.next = element.next;
        if (element.next != null) {
            element.next.previous = frontElement;
        }
    }
    if (!deletedNode.hasNext()) {
        footer = deletedNode.previous;
    }
    length--;
    return deletedNode;
}

链表的反转
链表的反转即将链表原有的数据顺序以及指向颠倒下，请先看源码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * 链表的反转[A,B,C,D]->[D,C,B,A]
 */
public void reverseDoubleLinkedList() {
    Node<E> tempNode = header;
    while (tempNode != null) {
        Node<E> nextNode = tempNode.next;
        Node<E> temp = tempNode.previous;
        tempNode.previous = tempNode.next;
        tempNode.next = temp;
        tempNode = nextNode;
    }
    Node<E> temp = header;
    header = footer;
    footer = temp;
}

双链表的反转有别于单链表的递归实现而是通过循环遍历各个节点，对每个节点的previous和next进行互换，最后再对header和footer进行互换就可以达到我们想要的效果。

其它的方法
这里展示双链表其它相关方法如下：

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
/**
 * 正向打印双链表的数据
 */
public void printListFront() {
    Node<E> node = header;
    System.out.print("DoubleLinkedList:[");
    while (node != null) {
        System.out.print(node.data);
        if (node.hasNext()) {
            System.out.print(",");
        }
        node = node.next;
    }
    System.out.println("]");
}
/**
 * 反向打印双链表的数据
 */
public void printListBack() {
    Node<E> node = footer;
    System.out.print("DoubleLinkedList:[");
    while (node != null) {
        System.out.print(node.data);
        if (node.hasPrevious()) {
            System.out.print(",");
        }
        node = node.previous;
    }
    System.out.println("]");
}
/**
 * 获取指定索引位置的对象
 * @param index 索引
 * @return 链表存储的对象
 */
public E getObject(int index) {
    if (index < 1 || index > this.length) {
        return null;
    }
    Node<E> node = null;
    try {
        node = getNode(index);
    } catch (Exception e) {
        e.printStackTrace();
    }
    return node.data;
}
/**
 * 获取对应index的结点对象element
 * @param index 指定索引
 * @return Node<E> 对象
 * @throws Exception
 */
private Node<E> getNode(int index) throws Exception{
    if (index < 0 || index > this.length) {
        throw new Exception("索引值越界");
    }
    Node<E> node = null;
    if (index == 0) {
        return node;
    }
    Node<E> indexNode = header;
    for (int i = 0;i < index - 1;i++) {
        indexNode = indexNode.next;
    }
    node = indexNode;
    return node;
}

总结

双向链表跟单链表一样具有相同的优点：结点的添加(插入)、删除比较方便，不需要占用较大的连续存储空间，除此之外双向链表表现的更为灵活。当然查询操作效率比较低下。

附加

更多相关内容请前往内功修炼系列！！！

1
2
1
2