- Hands-On Data Structures and Algorithms with Rust
- Claus Matzinger
- 266字
- 2021-07-02 14:11:52
Doubly linked list
The transaction log of the previous section is due for an upgrade. The product team wants to enable users to be able to examine the log by going through it forward and backward to see what each step does. This is bad news for the regular linked list, as it's really inefficient to go anywhere other than forward. So, how is this rectified?
It is rectified using the doubly linked list. The doubly linked list introduces the link back. While this sounds like a minor change, it allows to work on that list backward as well as forward, which significantly improves the ability to look up items. By augmenting the previous singly linked list item with a back pointer, the doubly linked list is almost created:
#[derive(Debug, Clone)]
struct Node {
value: String,
next: Link,
prev: Link,
}
type Link = Option<Rc<RefCell<Node>>>;
#[derive(Debug, Clone)]
pub struct BetterTransactionLog {
head: Link,
tail: Link,
pub length: u64,
}
Similar to the singly linked list, the list itself only consists of a head and a tail pointer, which makes accessing either end of the list cheap and easy. Additionally, the nodes now also feature a pointer back to the preceding node, making the list look like this:

This is also the point that makes the doubly linked list tricky in Rust. The ownership principle is great if there is a hierarchy of ownership: a customer has an address, a text file has several lines of text, and so on. However, a node in a doubly linked list doesn't have clear ownership of either of its neighbors.
- Greenplum:從大數據戰略到實現
- SQL Server 2012數據庫技術與應用(微課版)
- 分布式數據庫系統:大數據時代新型數據庫技術(第3版)
- 數亦有道:Python數據科學指南
- 從0到1:JavaScript 快速上手
- 深入淺出 Hyperscan:高性能正則表達式算法原理與設計
- 高維數據分析預處理技術
- 活用數據:驅動業務的數據分析實戰
- Python數據分析從小白到專家
- 大數據數學基礎(R語言描述)
- Access 2016數據庫應用基礎
- PostgreSQL高可用實戰
- 基于數據發布的隱私保護模型研究
- Practical Convolutional Neural Networks
- 數據挖掘與數據化運營實戰:思路、方法、技巧與應用