数据结构之单链表

数组需要一块连续的内存空间来存储,对内存的要求比较高。而链表恰恰相反,它并不需要一块连续的内存空间,它通过指针将一组零散的内存块串联起来使用。链表结构五花八门,三种最常见的链表结构,它们分别是:单链表、双向链表和循环链表。本文来看最简单、最常用的单链表。

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
/**
 * 单链表
 */
class SinglyLinkedList
{

    /**
     * 链表头结点|哨兵节点
     *
     * @var SinglyLinkedListNode
     */
    public $head;

    /**
     * 链表长度
     *
     * @var int
     */
    private $length;

    /**
     * 初始化
     *
     * @param null $head            
     */
    public function __construct($head = null)
    {
        $this->head = $head === null ? (new SinglyLinkedListNode()) : $head;
        $this->length = 0;
    }

    /**
     * 获取链表长度
     *
     * @return int
     */
    public function getLength()
    {
        return $this->length;
    }

    /**
     * 插入|头插法
     *
     * @param mixed $data            
     * @return SinglyLinkedListNode
     */
    public function insert($data)
    {
        return $this->insertDataAfter($this->head, $data);
    }

    /**
     * 删除节点
     *
     * @param SinglyLinkedListNode $node            
     * @return bool
     */
    public function delete(SinglyLinkedListNode $node)
    {
        if ($node === null) {
            return false;
        }
        $prev_node = $this->getPrevNode($node);
        $prev_node->next = $node->next;
        unset($node);
        $this->length --;
        return true;
    }

    /**
     * 获取前置节点
     *
     * @param SinglyLinkedListNode $node            
     * @return SinglyLinkedListNode|null
     */
    public function getPrevNode(SinglyLinkedListNode $node)
    {
        if ($node === null) {
            return null;
        }
        $curr = $this->head;
        $prev = $this->head;
        while ($curr !== $node && $curr !== null) {
            $prev = $curr;
            $curr = $curr->next;
        }
        return $prev;
    }

    /**
     * 通过索引获取节点
     *
     * @param int $index            
     * @return SinglyLinkedListNode|null
     */
    public function getNodeByIndex($index)
    {
        if ($index >= $this->length) {
            return null;
        }
        $curr = $this->head->next;
        for ($i = 0; $i < $index; $i ++) {
            $curr = $curr->next;
        }
        return $curr;
    }

    /**
     * 在指定节点后插入新节点
     *
     * @param SinglyLinkedListNode $origin_node            
     * @param SinglyLinkedListNode $node            
     * @return SinglyLinkedListNode|null
     */
    public function insertNodeAfter(SinglyLinkedListNode $origin_node, SinglyLinkedListNode $node)
    {
        if ($origin_node === null || $node === null) {
            return null;
        }
        $node->next = $origin_node->next;
        $origin_node->next = $node;
        $this->length ++;
        return $node;
    }

    /**
     * 在指定节点后插入新节点(插入数据)
     *
     * @param SinglyLinkedListNode $origin_node            
     * @param mixed $data            
     * @return SinglyLinkedListNode|null
     */
    public function insertDataAfter(SinglyLinkedListNode $origin_node, $data)
    {
        if ($origin_node === null) {
            return null;
        }
        $node = new SinglyLinkedListNode();
        $node->data = $data;
        $node->next = $origin_node->next;
        $origin_node->next = $node;
        $this->length ++;
        return $node;
    }

    /**
     * 打印链表
     *
     * @return null
     */
    public function print()
    {
        if ($this->head->next === null) {
            return;
        }
        $curr = $this->head;
        $length = $this->length;
        while ($curr->next !== null && $length --) {
            // 假设data均为可输出字符串格式
            echo $curr->next->data . ' -> ';
            $curr = $curr->next;
        }
        echo 'NULL', PHP_EOL;
    }
}

/**
 * 单链表节点
 */
class SinglyLinkedListNode
{

    /**
     * 节点的数据域
     *
     * @var mixed
     */
    public $data;

    /**
     * 节点的指针域|指向下一个节点
     *
     * @var SinglyLinkedListNode
     */
    public $next;

    /**
     * 构造函数
     */
    public function __construct($data = null)
    {
        $this->data = $data;
        $this->next = null;
    }
}

// 【调用示例】
$linked_list = new SinglyLinkedList();
$a = $linked_list->insert('A');
$linked_list->print();
$b = $linked_list->insert('B');
$linked_list->print();
$c = $linked_list->insertDataAfter($b, 'C');
$linked_list->print();
$d = $linked_list->insert('D');
$linked_list->print();
$new_node = new SinglyLinkedListNode('E');
$linked_list->insertNodeAfter($d, $new_node);
$linked_list->print();

输出如下:

1
2
3
4
5
A -> NULL
B -> A -> NULL
B -> C -> A -> NULL
D -> B -> C -> A -> NULL
D -> E -> B -> C -> A -> NULL