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

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.

主站蜘蛛池模板: 江都市| 临清市| 遂昌县| 鄂尔多斯市| 石景山区| 苍梧县| 赤峰市| 罗定市| 崇文区| 长兴县| 德昌县| 大宁县| 绩溪县| 阳东县| 拉孜县| 健康| 盐城市| 宁陕县| 尼勒克县| 双辽市| 佳木斯市| 额济纳旗| 神池县| 武宁县| 怀集县| 佛山市| 永顺县| 开远市| 宕昌县| 巴中市| 甘洛县| 乐陵市| 宾阳县| 望奎县| 西安市| 济宁市| 东丰县| 柳江县| 和硕县| 崇阳县| 闻喜县|