简介

链表（Linked List）是一种常见的线性数据结构，与数组相比，它具有不同的存储方式和操作特性。链表通过节点（Node）来存储数据，每个节点包含数据域和指针域，指针域指向下一个节点，从而形成一条节点链。

链表类型

  1. 单向链表（Singly Linked List）：每个节点只有一个指针，指向下一个节点。
  2. 双向链表（Doubly Linked List）：每个节点有两个指针，分别指向前一个节点和后一个节点。
  3. 循环链表（Circular Linked List）：链表的最后一个节点指向第一个节点，形成一个环。

链表操作

  1. 插入（Insertion）：在链表的指定位置插入一个新节点。
  2. 删除（Deletion）：删除链表中的指定节点。
  3. 查找（Search）：在链表中查找指定值的节点。
  4. 遍历（Traversal）：从头到尾访问链表中的每个节点。

Rust实现

完整代码可以看这里

数据结构定义

先定义链表的基本结构。链表由多个节点（Node）组成，每个节点包含一个元素（elem）和一个指向下一个节点的指针（next）。这里使用 Option<Box<Node<T>>> 作为节点指针的类型，主要是为了使用 None 表示空节点。

type NodePtr<T> = Option<Box<Node<T>>>;

pub struct List<T> {
    head: NodePtr<T>,
}

struct Node<T> {
    elem: T,
    next: NodePtr<T>,
}
  • NodePtr<T> 是一个类型别名，表示一个可能为空的节点指针。
  • List<T> 是链表的结构体，包含一个指向链表头部的指针 head。
  • Node<T> 是链表中的节点结构体，包含一个元素 elem 和一个指向下一个节点的指针 next。

链表基本操作

初始化链表

LinkedList的new方法用于创建一个空的链表。

impl<T> List<T> {
    pub fn new() -> Self {
        List { head: None }
    }
}

向链表中插入元素

push 方法用于在链表的头部插入一个新元素。这里直接创建一个新的节点，并将其插入到链表的头部。

pub fn push(&mut self, elem: T) {
    let new_node = Box::new(Node {
        elem: elem,
        next: self.head.take(),
    });
    self.head = Some(new_node);
}
  • self.head.take() 取出当前的链表头部，并将其置为 None。
  • 创建一个新的节点 new_node，并将其 next 指针指向原来的链表头部。
  • 最后，将链表的头部更新为新创建的节点。

信息

补充: take() 可以等效为 std::mem::replace(&mut option, None)。 它用于将 Option 中的值取出，并将其替换为 None。相较于 match ... Some(x) ... 的写法，take() 更加简洁。

从链表中弹出元素

pop 方法用于从链表的头部移除并返回一个元素。

pub fn pop(&mut self) -> Option<T> {
    self.head.take().map(|node| {
        self.head = node.next;
        node.elem
    })
}
  • self.head.take() 取出当前的链表头部，并将其置为 None。
  • 如果链表头部存在，则将其 next 指针赋值给 self.head，并返回节点的元素 node.elem。

信息

补充: map() 方法用于对 Option 进行映射操作，如果 Option 是 Some，则对其内部值进行操作，否则返回 None。

查看链表头部元素

peek 方法用于查看链表头部的元素，但不移除它。

pub fn peek(&self) -> Option<&T> {
    self.head.as_ref().map(|node| &node.elem)
}
  • self.head.as_ref() 获取链表头部的不可变引用。
  • 如果链表头部存在，则返回节点的元素引用 &node.elem。

修改链表头部元素

peek_mut 方法用于获取链表头部元素的可变引用，以便修改它。

pub fn peek_mut(&mut self) -> Option<&mut T> {
    self.head.as_mut().map(|node| &mut node.elem)
}
  • self.head.as_mut() 获取链表头部的可变引用。
  • 如果链表头部存在，则返回节点的元素可变引用 &mut node.elem。

在链表中插入元素

insert 方法用于在链表的指定位置插入一个新元素。

pub fn insert(&mut self, index: usize, elem: T) -> Result<(), &'static str> {
    let mut current = &mut self.head;

    for _ in 0..index {
        if let Some(node) = current {
            current = &mut node.next;
        } else {
            return Err("Index out of bounds");
        }
    }

    current.take().map(|node| {
        let new_node = Box::new(Node {
            elem,
            next: Some(node),
        });
        *current = Some(new_node);
    });

    Ok(())
}
  • 遍历链表到指定位置 index。
  • 如果位置合法，则在当前位置插入新节点。

从链表中移除元素

remove 方法用于从链表的指定位置移除一个元素。

pub fn remove(&mut self, index: usize) -> Result<(), &'static str> {
    let mut current = &mut self.head;
    for _ in 0..index {
        if let Some(node) = current {
            current = &mut node.next;
        } else {
            return Err("Index out of bounds");
        }
    }
    if let Some(node) = current.take() {
        *current = node.next;
        Ok(())
    } else {
        Err("Index out of bounds")
    }
}
  • 遍历链表到指定位置 index。
  • 如果位置合法，则移除当前位置的节点。

反转链表

reverse 方法用于反转整个链表。

pub fn reverse(&mut self) {
    let mut prev = None;
    let mut current = self.head.take();
    while let Some(mut node) = current {
        let next = node.next.take();
        node.next = prev;
        prev = Some(node);
        current = next;
    }
    self.head = prev;
}
  • 使用三个指针 prev、current 和 next 来反转链表。
  • 遍历链表，将每个节点的 next 指针指向前一个节点。
  • 最后，将链表的头部指向反转后的链表。

迭代器

消费迭代器

into_iter 方法用于将链表转换为一个消费迭代器。

pub fn into_iter(self) -> IntoIter<T> {
    IntoIter(self)
}

pub struct IntoIter<T>(List<T>);

impl<T> Iterator for IntoIter<T> {
    type Item = T;
    fn next(&mut self) -> Option<Self::Item> {
        self.0.pop()
    }
}

不可变引用迭代器

iter 方法用于获取链表的不可变引用迭代器。

pub fn iter(&self) -> Iter<'_, T> {
    Iter {
        next: self.head.as_deref(),
    }
}

pub struct Iter<'a, T> {
    next: Option<&'a Node<T>>,
}

impl<'a, T> Iterator for Iter<'a, T> {
    type Item = &'a T;

    fn next(&mut self) -> Option<Self::Item> {
        self.next.map(|node| {
            self.next = node.next.as_deref();
            &node.elem
        })
    }
}

可变引用迭代器

iter_mut 方法用于获取链表的可变引用迭代器。

pub fn iter_mut(&mut self) -> IterMut<'_, T> {
    IterMut {
        next: self.head.as_deref_mut(),
    }
}

pub struct IterMut<'a, T> {
    next: Option<&'a mut Node<T>>,
}

impl<'a, T> Iterator for IterMut<'a, T> {
    type Item = &'a mut T;

    fn next(&mut self) -> Option<Self::Item> {
        self.next.take().map(|node| {
            self.next = node.next.as_deref_mut();
            &mut node.elem
        })
    }
}