数据结构 链表_单链表前驱结点 后继结点

概述

在讲链表的数据结构之前，我们先说一个最简单的数据结构-线性表。对于线性表，想必作为开发者都不会陌生，我们常用的数组就是通过线性表实现的，线性表就是在内存中一段连续的内存地址。

与线性表相比，链表的数据结构也是按照每个元素的线性顺序排列的，但是与线性表不同的是，链表的顺序是通过每个元素中指针决定的。

双链表

双向链表也叫双链表，是链表的一种，它的每个数据节点中都有两个指针，分别指向前驱结点和后继结点：pre和next。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。

一般情况下，链表在创建时，都会创建一个头结点。当链表中不存在其他元素是，该头结点的前驱和后继都是指向本身的，此时链表为空链表。如果一个链表的前驱结点指向头结点，那么该结点为链表的头（head）；如果一个结点的后继节点为空，那么该节点就是链表的尾结点（tail）。

单链表和循环链表

如果一个链表的节点中没有指针指向前驱结点，那么该链表为单链表。
如果一个双向链表的尾结点的后继结点指向头结点，同时，链表的头结点的前驱结点指向链表的尾结点，那么该链表被称为循环链表。

双链表的代码实现

package structdemo;

/**
 * 双向链表
 * 
 * @author zhangke
 *
 */
public class LinkedList<E> {

    /**
     * 定义头结点
     */
    private Node header;

    private int size;

    public LinkedList() {
        // 初始化头节点，此时头结点的前驱和后继都指向自己
        header = new Node(null, null, null);
        header.preNode = header;
        header.nextNode = header;
    }

    /**
     * 添加，默认在末尾添加
     * 
     * @param data
     */
    public void add(E data) {
        add(size, data);
    }

    /**
     * 指定位置添加
     */
    public void add(int index, E data) {
        Node node = node(index);

        Node newNode = new Node(node.preNode, node, data);
        node.preNode.nextNode = newNode;
        node.preNode = newNode;

        size++;
    }

    /**
     * 删除指定位置节点
     * 
     * @param indext
     * @return
     */
    public E delete(int indext) {
        Node node = node(indext);
        node.preNode.nextNode = node.nextNode;
        node.nextNode.preNode = node.preNode;

        size--;
        return node.data;
    }

    /**
     * 查询指定位置节点
     */
    public E get(int index) {
        Node node = node(index);
        return node.data;
    }

    /**
     * 获取指定位置的节点
     * 
     * @param index
     * @return
     */
    private Node node(int index) {
        if (index > size || index < 0) {
            throw new IndexOutOfBoundsException();
        }

        Node node = header;

        /**
         * 这里使用了二分法的思想，如果插入的元素在链表后半段，那么从后查找，否则从前查找，可以节约寻址时间
         */
        if (index >= size / 2) {
            for (int i = size - 1; i >= index; i--) {
                node = node.preNode;
            }
        } else {
            for (int i = 0; i <= index; i++) {
                node = node.nextNode;
            }
        }
        return node;
    }

    /**
     * 返回链表的大小
     * 
     * @return
     */
    public int getSize() {
        return size;
    }

    /**
     * 链表是否为空
     * 
     * @return
     */
    public boolean isEmpty() {
        return (header.preNode == header.nextNode);
        // return (size == 0)? true:false;

    }

    /**
     * 定义链表的节点
     * 
     * @author zhangke
     *
     */
    private class Node {

        public Node(Node pre, Node next, E data) {
            this.preNode = pre;
            this.nextNode = next;
            this.data = data;
        }

        /**
         * 前驱节点
         */
        public Node preNode;
        /**
         * 后继节点
         */
        public Node nextNode;
        /**
         * 节点的数据
         */
        public E data;

    }

}
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