Rust - 纯Safe双向链表

该代码仅仅提供学习与交流，你要是和我考究性能，你开心就好。

Rust实现

struct Node<T> {
    data: Box<T>,
    head: Option<Arc<Mutex<Node<T>>>>,
    next: Option<Arc<Mutex<Node<T>>>>,
}

impl <T> Node<T> {
    fn new(data: T) -> Self {
        Node {
            data: Box::new(data),
            head: None,
            next: None,
        }
    }
}

struct BiLinkedList<T> {
    head: Option<Arc<Mutex<Node<T>>>>,
    tail: Option<Arc<Mutex<Node<T>>>>,
}

impl <T> BiLinkedList<T> {
    fn new() -> Self {
        BiLinkedList {
            head: None,
            tail: None,
        }
    }

    fn push(&mut self, data: T) {
        let mut node = Node::new(data);
        if self.head.is_none() {
            let head = Arc::new(Mutex::new(node));
            self.tail = Some(Arc::clone(&head));
            self.head = Some(head);
        } else {
            let mut head = self.head.take().unwrap();
            node.next = Some(head.clone());
            let new_head = Arc::new(Mutex::new(node));
            let mut head = head.lock().unwrap();
            head.head = Some(Arc::clone(&new_head));
            self.head = Some(new_head);
        }
    }

    fn pop(&mut self) -> Option<Arc<Mutex<Node<T>>>> {
        if self.head.is_none() {
            return None;
        }
        let head = self.head.take().unwrap();
        let lock = head.lock().unwrap();
        if lock.next.is_some() {
            self.head = lock.next.clone();
        } else {
            self.head = None;
            self.tail = None;
        }
        drop(lock);
        Some(head)
    }
}

#[tokio::main]
async fn main() {
    let start_time = Instant::now();


    let mut sum = 0;
    for _ in 0..100_0000 {
        let mut list = BiLinkedList::<i32> {
            head: None,
            tail: None,
        };
        list.push(1);
        list.push(2);
        list.push(3);
        list.push(4);
        list.push(5);
        list.push(6);
        list.push(7);
        list.push(8);
        let mut node = list.head.clone();
        while node.is_some() {
            let mutex = node.clone().unwrap();
            let mut lock = mutex.lock().unwrap();
            sum += *lock.data.as_ref();
            node = lock.next.clone();
        }
    }
    println!("{}", sum);
    println!("Cost: {}ms", start_time.elapsed().as_millis());
}

C++代码

template<class T>
class Node {
public:
    T* data;
    Node<T>* prev;
    Node<T>* next;

    Node(T* data) {
        this->data = data;
        this->prev = nullptr;
        this->next = nullptr;
    }
};

template<class T>
class BiLinkedList {
public:
    Node<T>* head = nullptr;
    Node<T>* tail = nullptr;

    void append(T* data) {
        Node<T>* newNode = new Node<T>(data);
        if (tail) {
            tail->next = newNode;
            newNode->prev = tail;
            tail = newNode;
        } else {
            head = tail = newNode;
        }
    }

    void prepend(T* data) {
        Node<T>* newNode = new Node<T>(data);
        if (head) {
            head->prev = newNode;
            newNode->next = head;
            head = newNode;
        } else {
            head = tail = newNode;
        }
    }

    void remove(Node<T>* node) {
        if (!node) return;

        if (node->prev) {
            node->prev->next = node->next;
        } else {
            head = node->next;
        }

        if (node->next) {
            node->next->prev = node->prev;
        } else {
            tail = node->prev;
        }

        delete node->data;
        delete node;
    }

    Node<T>* find(T* data) {
        Node<T>* current = head;
        while (current) {
            if (*(current->data) == *data) {
                return current;
            }
            current = current->next;
        }
        return nullptr;
    }

    int printList() {
        int sum = 0;
        Node<T>* current = head;
        while (current) {
            //std::cout << *(current->data) << " ";
            sum += *(current->data);
            current = current->next;
        }
        return sum;
    }

    ~BiLinkedList() {
        Node<T>* current = head;
        while (current) {
            Node<T>* next = current->next;
            //delete current->data; 测试用例，数据在栈，无需delete
            delete current;
            current = next;
        }
    }
};

int main() {
    auto start = std::chrono::high_resolution_clock::now();
    int sum = 0;
    for (int i = 0; i < 1000000; ++i) {
        BiLinkedList<int> list{};
        int a = 1, b = 2, c = 3, d = 4, e = 5, f = 6, g = 7, h = 8;
        list.prepend(&a);
        list.prepend(&b);
        list.prepend(&c);
        list.prepend(&d);
        list.prepend(&e);
        list.prepend(&f);
        list.prepend(&g);
        list.prepend(&h);
        sum += list.printList();
    }
    std::cout << sum << "\n";
    auto end = std::chrono::high_resolution_clock::now();
    auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count();
    std::cout << "Cost: "<< duration << "ms" << std::endl;
    return 0;
}

表现

// Rust
36000000
Cost: 1735ms
// C++
36000000
Cost: 252ms