- 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.
- 計算機組成原理與接口技術:基于MIPS架構實驗教程(第2版)
- 云數據中心基礎
- SQL Server入門經典
- Visual Studio 2015 Cookbook(Second Edition)
- Hadoop大數據實戰權威指南(第2版)
- 達夢數據庫性能優化
- Learning Proxmox VE
- 圖數據實戰:用圖思維和圖技術解決復雜問題
- 新基建:數據中心創新之路
- Python數據分析與挖掘實戰(第3版)
- 智慧的云計算
- 新手學會計(2013-2014實戰升級版)
- Mastering ROS for Robotics Programming(Second Edition)
- 大數據時代系列(套裝9冊)
- AI Crash Course