官术网_书友最值得收藏!

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.

主站蜘蛛池模板: 桂东县| 天气| 盐山县| 温州市| 板桥市| 乾安县| 甘洛县| 宣城市| 阳曲县| 嵩明县| 呼和浩特市| 山东| 永修县| 桃园市| 平潭县| 中卫市| 灵寿县| 南陵县| 晋州市| 开化县| 靖西县| 萨嘎县| 噶尔县| 峨眉山市| 芮城县| 交城县| 天峻县| 合作市| 江城| 榆中县| 漾濞| 岗巴县| 博爱县| 同仁县| 富源县| 临沭县| 青阳县| 抚远县| 通化县| 兴隆县| 喀什市|