您现在的位置是：首页 > 技术教程 正文

单链表的多语言表达：C++、Java、Python、Go、Rust

admin 阅读： 2024-03-24
后台-插件-广告管理-内容页头部广告（手机）

单链表

是一种链式数据结构，由一个头节点和一些指向下一个节点的指针组成。每个节点包含一个数据元素和指向下一个节点的指针。头节点没有数据，只用于表示链表的开始位置。

单链表的主要操作包括：

  1. 添加元素：在链表的头部添加新元素，需要修改头节点的指针。
  2. 删除元素：删除链表中的元素，需要修改头节点和其他节点的指针。
  3. 查找元素：在链表中查找某个元素，需要遍历整个链表。
  4. 遍历链表：按照链表的顺序依次访问每个元素，需要遍历整个链表。

单链表相对于数组的优点是插入和删除元素时不需要移动其他元素，时间复杂度为O(1)。但是，在查找元素时，单链表比数组要慢，时间复杂度为O(n)。

20210817204340750.png

本文总结了 C++、Java、Python、Go、Rust 五种语言的单链表的表达：

C++

c++语言既可以用struct也能用class来表示链表节点，类可以定义方法调用相对方便。另外C++类需要自定义析构函数用以退出时释放节点所占空间，其它语言有自动的垃圾回收机制。

struct 

// 定义结构体 Node，表示链表中的节点
struct Node {
    int data;  // 节点的数据
    Node* next;  // 指向下一个节点的指针
};

// 定义类 LinkedList，表示链表
class LinkedList {
private:
    Node* head;  // 指向链表头节点的指针
}

代码：

  1. #include
  3. using namespace std;
  5. // 定义结构体 Node，表示链表中的节点
  6. struct Node {
  7. int data; // 节点的数据
  8. Node* next; // 指向下一个节点的指针
  9. };
  11. // 定义类 LinkedList，表示链表
  12. class LinkedList {
  13. private:
  14. Node* head; // 指向链表头节点的指针
  16. public:
  17. // 构造函数，初始化链表为空链表
  18. LinkedList() {
  19. head = NULL;
  20. }
  22. // 析构函数，释放链表中的所有节点
  23. ~LinkedList() {
  24. Node* curr = head;
  25. while (curr != NULL) {
  26. Node* next = curr->next;
  27. delete curr;
  28. curr = next;
  29. }
  30. }
  32. // 在链表头部添加一个新节点
  33. void add(int value) {
  34. Node* newNode = new Node;
  35. newNode->data = value;
  36. newNode->next = head;
  37. head = newNode;
  38. }
  40. // 在链表尾部添加一个新节点
  41. void push(int value) {
  42. Node* newNode = new Node;
  43. newNode->data = value;
  44. newNode->next = NULL;
  45. if (head == NULL) {
  46. head = newNode;
  47. } else {
  48. Node* curr = head;
  49. while (curr->next != NULL) {
  50. curr = curr->next;
  51. }
  52. curr->next = newNode;
  53. }
  54. }
  56. // 删除最后一个节点，并返回该节点的数据
  57. int pop() {
  58. if (head == NULL) {
  59. return -1;
  60. } else if (head->next == NULL) {
  61. int data = head->data;
  62. delete head;
  63. head = NULL;
  64. return data;
  65. } else {
  66. Node* curr = head;
  67. while (curr->next->next != NULL) {
  68. curr = curr->next;
  69. }
  70. int data = curr->next->data;
  71. delete curr->next;
  72. curr->next = NULL;
  73. return data;
  74. }
  75. }
  77. // 遍历链表，打印每个节点的数据
  78. void traverse() {
  79. Node* curr = head;
  80. while (curr != NULL) {
  81. cout << curr->data << "->";
  82. curr = curr->next;
  83. }
  84. cout << "nil" << endl;
  85. }
  86. };
  88. int main() {
  89. LinkedList list;
  90. list.traverse(); // 打印空链表 nil
  91. list.add(1); // 在链表头部添加节点 1
  92. list.traverse(); // 打印链表 1->nil
  93. list.add(2); // 在链表头部添加节点 2
  94. list.traverse(); // 打印链表 2->1->nil
  95. list.add(3); // 在链表头部添加节点 3
  96. list.traverse(); // 打印链表 3->2->1->nil
  97. list.push(4); // 在链表尾部添加节点 4
  98. list.traverse(); // 打印链表 3->2->1->4->nil
  99. list.push(5); // 在链表尾部添加节点 5
  100. list.traverse(); // 打印链表 3->2->1->4->5->nil
  101. cout << list.pop() << endl; // 删除尾节点，并输出节点数据
  102. list.traverse(); // 打印链表 3->2->1->4->nil
  103. cout << list.pop() << endl; // 删除尾节点，并输出节点数据
  104. list.traverse(); // 打印链表 3->2->1->nil
  105. return 0;
  106. }

class

// 定义类 Node，表示链表中的节点
class Node {
public:
    int data;
    Node* next;
    Node(int value) {
        data = value;
        next = NULL;
    }
};

// 定义类 LinkedList，表示链表
class LinkedList {
private:
    Node* head;  // 指向链表头节点的指针
};

代码：

  1. #include
  3. using namespace std;
  5. // 定义类 Node，表示链表中的节点
  6. class Node {
  7. public:
  8. int data;
  9. Node* next;
  10. Node(int value) {
  11. data = value;
  12. next = NULL;
  13. }
  14. };
  16. // 定义类 LinkedList，表示链表
  17. class LinkedList {
  18. private:
  19. Node* head; // 指向链表头节点的指针
  21. public:
  22. // 构造函数，初始化链表为空链表
  23. LinkedList() {
  24. head = NULL;
  25. }
  27. // 析构函数，释放链表中的所有节点
  28. ~LinkedList() {
  29. Node* curr = head;
  30. while (curr != NULL) {
  31. Node* next = curr->next;
  32. delete curr;
  33. curr = next;
  34. }
  35. }
  37. // 在链表头部添加一个新节点
  38. void add(int value) {
  39. Node* newNode = new Node(value);
  40. newNode->next = head;
  41. head = newNode;
  42. }
  44. // 在链表尾部添加一个新节点
  45. void push(int value) {
  46. Node* newNode = new Node(value);
  47. newNode->next = NULL;
  48. if (head == NULL) {
  49. head = newNode;
  50. } else {
  51. Node* curr = head;
  52. while (curr->next != NULL) {
  53. curr = curr->next;
  54. }
  55. curr->next = newNode;
  56. }
  57. }
  59. // 删除最后一个节点，并返回该节点的数据
  60. int pop() {
  61. if (head == NULL) {
  62. return -1;
  63. } else if (head->next == NULL) {
  64. int data = head->data;
  65. delete head;
  66. head = NULL;
  67. return data;
  68. } else {
  69. Node* curr = head;
  70. while (curr->next->next != NULL) {
  71. curr = curr->next;
  72. }
  73. int data = curr->next->data;
  74. delete curr->next;
  75. curr->next = NULL;
  76. return data;
  77. }
  78. }
  80. // 遍历链表，打印每个节点的数据
  81. void traverse() {
  82. Node* curr = head;
  83. while (curr != NULL) {
  84. cout << curr->data << "->";
  85. curr = curr->next;
  86. }
  87. cout << "nil" << endl;
  88. }
  89. };
  91. int main() {
  92. LinkedList list;
  93. list.traverse(); // 打印空链表 nil
  94. list.add(1); // 在链表头部添加节点 1
  95. list.traverse(); // 打印链表 1->nil
  96. list.add(2); // 在链表头部添加节点 2
  97. list.traverse(); // 打印链表 2->1->nil
  98. list.add(3); // 在链表头部添加节点 3
  99. list.traverse(); // 打印链表 3->2->1->nil
  100. list.push(4); // 在链表尾部添加节点 4
  101. list.traverse(); // 打印链表 3->2->1->4->nil
  102. list.push(5); // 在链表尾部添加节点 5
  103. list.traverse(); // 打印链表 3->2->1->4->5->nil
  104. cout << list.pop() << endl; // 删除尾节点，并输出节点数据
  105. list.traverse(); // 打印链表 3->2->1->4->nil
  106. cout << list.pop() << endl; // 删除尾节点，并输出节点数据
  107. list.traverse(); // 打印链表 3->2->1->nil
  108. return 0;
  109. }

Java

Java没有跟C或Go类似的struct结构体，只有用类class来表达。

class 

public class LinkedList {
    public class Node {
        public int data;
        public Node next;

        public Node(int value) {
            data = value;
            next = null;
        }
    }

    public LinkedList() {
        head = null;
    }
}

代码：

  1. public class LinkedList {
  2. public class Node {
  3. public int data;
  4. public Node next;
  6. public Node(int value) {
  7. data = value;
  8. next = null;
  9. }
  10. }
  12. public LinkedList() {
  13. head = null;
  14. }
  16. private Node head;
  18. // 在链表头部添加一个新的节点
  19. public void add(int value) {
  20. Node newNode = new Node(value);
  21. newNode.next = head;
  22. head = newNode;
  23. }
  25. // 在链表尾部添加一个新的节点
  26. public void push(int value) {
  27. Node newNode = new Node(value);
  28. if (head == null) {
  29. head = newNode;
  30. } else {
  31. Node curr = head;
  32. while (curr.next != null) {
  33. curr = curr.next;
  34. }
  35. curr.next = newNode;
  36. }
  37. }
  39. // 删除尾节点，并返回该节点的数据
  40. public int pop() {
  41. if (head == null) {
  42. return -1;
  43. } else if (head.next == null) {
  44. int data = head.data;
  45. head = null;
  46. return data;
  47. } else {
  48. Node curr = head;
  49. while (curr.next.next != null) {
  50. curr = curr.next;
  51. }
  52. Node tail = curr.next;
  53. curr.next = null;
  54. return tail.data;
  55. }
  56. }
  58. // 遍历链表，打印每个节点的数据
  59. public void traverse() {
  60. Node curr = head;
  61. while (curr != null) {
  62. System.out.print(curr.data + "->");
  63. curr = curr.next;
  64. }
  65. System.out.println("nil");
  66. }
  68. public static void main(String[] args) {
  69. LinkedList list = new LinkedList();
  70. list.traverse(); // 打印空链表 nil
  71. list.add(1); // 在链表头部添加节点 1
  72. list.traverse(); // 打印链表 1->nil
  73. list.add(2); // 在链表头部添加节点 2
  74. list.traverse(); // 打印链表 2->1->nil
  75. list.add(3); // 在链表头部添加节点 3
  76. list.traverse(); // 打印链表 3->2->1->nil
  77. list.push(4); // 在链表尾部添加节点 4
  78. list.traverse(); // 打印链表 3->2->1->4->nil
  79. list.push(5); // 在链表尾部添加节点 5
  80. list.traverse(); // 打印链表 3->2->1->4->5->nil
  81. System.out.println(list.pop()); // 删除尾节点，并输出节点数据
  82. list.traverse(); // 打印链表 3->2->1->4->nil
  83. System.out.println(list.pop()); // 删除尾节点，并输出节点数据
  84. list.traverse(); // 打印链表 3->2->1->nil
  85. }
  86. }

Python

Python也没有struct结构体，只能用类class来表达。而且python是动态类型语言，变量在创建时无需显式指定类型，也没有指针概念。

class 

class Node:
    def __init__(self, data):
        self.data = data  # 节点的数据
        self.next = None  # 节点的下一个指针，初始为空

class LinkedList:
    def __init__(self):
        self.head = None  # 链表的头指针，初始为空

代码：

  1. class Node:
  2. def __init__(self, data):
  3. self.data = data # 节点的数据
  4. self.next = None # 节点的下一个指针，初始为空
  6. class LinkedList:
  7. def __init__(self):
  8. self.head = None # 链表的头指针，初始为空
  10. def add(self, data):
  11. # 在链表头部插入一个新节点
  12. newNode = Node(data)
  13. newNode.next = self.head
  14. self.head = newNode
  16. def push(self, data):
  17. # 在链表尾部添加一个新节点
  18. newNode = Node(data)
  19. if self.head is None:
  20. self.head = newNode
  21. else:
  22. curr = self.head
  23. while curr.next is not None:
  24. curr = curr.next
  25. curr.next = newNode
  27. def pop(self):
  28. # 删除尾节点，并返回该节点的值
  29. if self.head is None:
  30. return None
  31. if self.head.next is None:
  32. data = self.head.data
  33. self.head = None
  34. return data
  35. curr = self.head
  36. while curr.next.next is not None:
  37. curr = curr.next
  38. tail = curr.next
  39. curr.next = None
  40. return tail.data
  42. def traverse(self):
  43. # 遍历链表，打印每个节点的数据
  44. curr = self.head
  45. while curr is not None:
  46. print(curr.data, end='->')
  47. curr = curr.next
  48. print('nil')
  50. if __name__ == '__main__':
  51. head = LinkedList() # 创建链表
  52. head.traverse() # 遍历空链表
  53. head.add(1) # 在链表头部添加节点 1
  54. head.traverse() # 遍历链表 1->nil
  55. head.add(2) # 在链表头部添加节点 2
  56. head.traverse() # 遍历链表 2->1->nil
  57. head.add(3) # 在链表头部添加节点 3
  58. head.traverse() # 遍历链表 3->2->1->nil
  59. head.push(4) # 在链表尾部添加节点 4
  60. head.traverse() # 遍历链表 3->2->1->4->nil
  61. head.push(5) # 在链表尾部添加节点 5
  62. head.traverse() # 遍历链表 3->2->1->4->5->nil
  63. print(head.pop()) # 删除尾节点，并输出节点数据
  64. head.traverse() # 打印链表 3->2->1->4->nil
  65. print(head.pop()) # 删除尾节点，并输出节点数据
  66. head.traverse() # 打印链表 3->2->1->nil

Golang

Go没有class类，使用结构体 struct 来代替类。结构体可以包含字段（成员变量），并且可以定义方法（成员函数）来操作结构体的数据。

struct

type Node struct {
    data int
    next *Node
}

type LinkedList struct {
    head *Node
}

// 创建一个新的节点
func new(value int) *Node {
    return &Node{
        data: value,
        next: nil,
    }
}

代码：

  1. package main
  3. import "fmt"
  5. type Node struct {
  6. data int
  7. next *Node
  8. }
  10. type LinkedList struct {
  11. head *Node
  12. }
  14. // 创建一个新的节点
  15. func new(value int) *Node {
  16. return &Node{
  17. data: value,
  18. next: nil,
  19. }
  20. }
  22. // 在链表头部添加一个新节点
  23. func (list *LinkedList) add(value int) {
  24. newNode := new(value)
  25. newNode.next = list.head
  26. list.head = newNode
  27. }
  29. // 在链表尾部添加一个新节点
  30. func (list *LinkedList) push(value int) {
  31. newNode := new(value)
  32. if list.head == nil {
  33. list.head = newNode
  34. } else {
  35. curr := list.head
  36. for curr.next != nil {
  37. curr = curr.next
  38. }
  39. curr.next = newNode
  40. }
  41. }
  43. // 删除尾节点，并返回该节点的值
  44. func (list *LinkedList) pop() int {
  45. if list.head == nil {
  46. return -1
  47. } else if list.head.next == nil {
  48. data := list.head.data
  49. list.head = nil
  50. return data
  51. } else {
  52. curr := list.head
  53. for curr.next.next != nil {
  54. curr = curr.next
  55. }
  56. tail := curr.next
  57. curr.next = nil
  58. return tail.data
  59. }
  60. }
  62. // 遍历链表，打印每个节点的数据
  63. func (list *LinkedList) traverse() {
  64. curr := list.head
  65. for curr != nil {
  66. fmt.Printf("%d->", curr.data)
  67. curr = curr.next
  68. }
  69. fmt.Println("nil")
  70. }
  72. func main() {
  73. list := LinkedList{}
  74. list.traverse() // 打印空链表 nil
  75. list.add(1) // 在链表头部添加节点 1
  76. list.traverse() // 打印链表 1->nil
  77. list.add(2) // 在链表头部添加节点 2
  78. list.traverse() // 打印链表 2->1->nil
  79. list.add(3) // 在链表头部添加节点 3
  80. list.traverse() // 打印链表 3->2->1->nil
  81. list.push(4) // 在链表尾部添加节点 4
  82. list.traverse() // 打印链表 3->2->1->4->nil
  83. list.push(5) // 在链表尾部添加节点 5
  84. list.traverse() // 打印链表 3->2->1->4->5->nil
  85. fmt.Println(list.pop()) // 删除尾节点，并打印数据
  86. list.traverse() // 打印链表 3->2->1->4->nil
  87. fmt.Println(list.pop()) // 删除尾节点，并打印数据
  88. list.traverse() // 打印链表 3->2->1->nil
  89. }

Rust

Rust中也没有类的概念，但它提供了结构体 struct 和 trait 两种重要的机制来实现面向对象的编程风格。结构体用于定义数据结构，而 trait 则用于定义方法集合。

另外在Rust中，一般不使用unsafe指针std::ptr来操作链表，而是 Option 类型来表示链表指针，它代表的值可以存在（Some）也可以不存在（None）。Option 类型被广泛用于处理可能为空的值，以避免出现空指针异常。

struct

struct Node {
    data: i32,
    next: Option>,
}

impl Node {
    fn new(value: i32) -> Node {
        Node { data: value, next: None }
    }
}

struct LinkedList {
    head: Option>,
}

impl LinkedList {
    fn new() -> LinkedList {
        LinkedList { head: None }
    }
}

代码：

  1. struct Node {
  2. data: i32,
  3. next: Option<Box>,
  4. }
  6. impl Node {
  7. fn new(value: i32) -> Node {
  8. Node { data: value, next: None }
  9. }
  10. }
  12. struct LinkedList {
  13. head: Option<Box>,
  14. }
  16. impl LinkedList {
  17. fn new() -> LinkedList {
  18. LinkedList { head: None }
  19. }
  21. // 在链表头部添加一个新节点
  22. fn add(&mut self, value: i32) {
  23. let mut new_node = Box::new(Node::new(value));
  24. new_node.next = self.head.take();
  25. self.head = Some(new_node);
  26. }
  28. // 在链表尾部添加一个新节点
  29. fn push(&mut self, value: i32) {
  30. let new_node = Box::new(Node::new(value));
  31. let mut curr = &mut self.head;
  32. while let Some(node) = curr {
  33. curr = &mut node.next;
  34. }
  35. *curr = Some(new_node);
  36. }
  38. // 删除尾节点，并返回该节点的数据
  39. fn pop(&mut self) -> Option<i32> {
  40. if self.head.is_none() {
  41. return None;
  42. }
  43. if self.head.as_ref().unwrap().next.is_none() {
  44. let data = self.head.take().unwrap().data;
  45. return Some(data);
  46. }
  47. let mut curr = self.head.as_mut().unwrap();
  48. while curr.next.as_ref().unwrap().next.is_some() {
  49. curr = curr.next.as_mut().unwrap();
  50. }
  51. let data = curr.next.take().unwrap().data;
  52. Some(data)
  53. }
  55. // 遍历链表，打印每个节点的数据
  56. fn traverse(&self) {
  57. let mut curr = &self.head;
  58. while let Some(node) = curr {
  59. print!("{}->", node.data);
  60. curr = &node.next;
  61. }
  62. println!("nil");
  63. }
  64. }
  66. fn main() {
  67. let mut list = LinkedList::new();
  68. list.traverse(); // 打印空链表 nil
  69. list.add(1); // 在链表头部添加节点 1
  70. list.traverse(); // 打印链表 1->nil
  71. list.add(2); // 在链表头部添加节点 2
  72. list.traverse(); // 打印链表 2->1->nil
  73. list.add(3); // 在链表头部添加节点 3
  74. list.traverse(); // 打印链表 3->2->1->nil
  75. list.push(4); // 在链表尾部添加节点 4
  76. list.traverse(); // 打印链表 3->2->1->4->nil
  77. list.push(5); // 在链表尾部添加节点 5
  78. list.traverse(); // 打印链表 3->2->1->4->5->nil
  79. println!("{}", list.pop().unwrap()); // 删除尾节点，并输出节点数据
  80. list.traverse(); // 打印链表 3->2->1->4->nil
  81. println!("{}", list.pop().unwrap()); // 删除尾节点，并输出节点数据
  82. list.traverse(); // 打印链表 3->2->1->nil
  83. }

struct unsafe

struct Node {
    data: i32,
    next: *mut Node,
}

impl Node {
    fn new(value: i32) -> Node {
        Node { data: value, next: std::ptr::null_mut() }
    }
}

struct LinkedList {
    head: *mut Node,
}

impl LinkedList {
    fn new() -> LinkedList {
        LinkedList { head: std::ptr::null_mut() }
    }
}

代码：

  1. struct Node {
  2. data: i32,
  3. next: *mut Node,
  4. }
  6. impl Node {
  7. fn new(value: i32) -> Node {
  8. Node { data: value, next: std::ptr::null_mut() }
  9. }
  10. }
  12. struct LinkedList {
  13. head: *mut Node,
  14. }
  16. impl LinkedList {
  17. fn new() -> LinkedList {
  18. LinkedList { head: std::ptr::null_mut() }
  19. }
  21. fn add(&mut self, value: i32) {
  22. let mut new_node = Box::new(Node::new(value));
  23. new_node.next = self.head;
  24. self.head = Box::into_raw(new_node);
  25. }
  27. fn push(&mut self, value: i32) {
  28. let new_node = Box::new(Node::new(value));
  29. let mut curr = &mut self.head;
  30. while !(*curr).is_null() {
  31. curr = unsafe { &mut (**curr).next };
  32. }
  33. *curr = Box::into_raw(new_node);
  34. }
  36. fn pop(&mut self) -> Option<i32> {
  37. if self.head.is_null() {
  38. return None;
  39. }
  40. let mut curr = self.head;
  41. let mut prev = std::ptr::null_mut();
  42. while unsafe { !(*curr).next.is_null() } {
  43. prev = curr;
  44. curr = unsafe { (*curr).next };
  45. }
  46. let data = unsafe { Box::from_raw(curr) }.data;
  47. if prev.is_null() {
  48. self.head = std::ptr::null_mut();
  49. } else {
  50. unsafe { (*prev).next = std::ptr::null_mut(); }
  51. }
  52. Some(data)
  53. }
  55. fn traverse(&self) {
  56. let mut curr = self.head;
  57. while !curr.is_null() {
  58. unsafe {
  59. print!("{}->", (*curr).data);
  60. curr = (*curr).next;
  61. }
  62. }
  63. println!("nil");
  64. }
  66. fn cleanup(&mut self) {
  67. let mut curr = self.head;
  68. while !curr.is_null() {
  69. let next = unsafe { (*curr).next };
  70. unsafe { Box::from_raw(curr) };
  71. curr = next;
  72. }
  73. }
  74. }
  76. fn main() {
  77. let mut list = LinkedList::new();
  78. list.traverse(); // 打印空链表 nil
  79. list.add(1);
  80. list.traverse();
  81. list.add(2);
  82. list.traverse();
  83. list.add(3);
  84. list.traverse();
  85. list.push(4);
  86. list.traverse();
  87. list.push(5);
  88. list.traverse();
  89. println!("{}", list.pop().unwrap());
  90. list.traverse();
  91. println!("{}", list.pop().unwrap());
  92. list.traverse();
  93. list.cleanup();
  94. }

cleanup()相当于析构函数，用于释放链表所占空间。

以上所有示例代码的输出都相同：

nil
1->nil
2->1->nil
3->2->1->nil
3->2->1->4->nil
3->2->1->4->5->nil
5
3->2->1->4->nil
4
3->2->1->nil

其中，Rust的节点值有点特殊，使用了Some类型。比如：

使用println!("{:?}", list.pop());  不需要pop()后面的.unwrap()，返回Some(n)；当链表为空时，直接返回None。

完

标签:
声明

1.本站遵循行业规范，任何转载的稿件都会明确标注作者和来源；2.本站的原创文章，请转载时务必注明文章作者和来源，不尊重原创的行为我们将追究责任；3.作者投稿可能会经我们编辑修改或补充。

在线投稿：投稿 站长QQ：1888636

后台-插件-广告管理-内容页尾部广告（手机）
相关文章
关注我们

扫一扫关注我们，了解最新精彩内容

搜索
排行榜
最近发表
标签列表