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

简介: 单链表是一种链式数据结构,由一个头节点和一些指向下一个节点的指针组成。每个节点包含一个数据元素和指向下一个节点的指针。头节点没有数据,只用于表示链表的开始位置。单链表相对于数组的优点是插入和删除元素时不需要移动其他元素,时间复杂度为O(1)。但是,在查找元素时,单链表比数组要慢,时间复杂度为O(n)。

 image.gif

单链表

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

单链表的主要操作包括:

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

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

    image.gif

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

    C++

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

    struct

    // 定义结构体 Node,表示链表中的节点

    struct Node {

       int data;  // 节点的数据

       Node* next;  // 指向下一个节点的指针

    };

    // 定义类 LinkedList,表示链表

    class LinkedList {

    private:

       Node* head;  // 指向链表头节点的指针

    }

    代码:

    #include <iostream>
    using namespace std;
    // 定义结构体 Node,表示链表中的节点
    struct Node {
        int data;  // 节点的数据
        Node* next;  // 指向下一个节点的指针
    };
    // 定义类 LinkedList,表示链表
    class LinkedList {
    private:
        Node* head;  // 指向链表头节点的指针
    public:
        // 构造函数,初始化链表为空链表
        LinkedList() {
            head = NULL;
        }
        // 析构函数,释放链表中的所有节点
        ~LinkedList() {
            Node* curr = head;
            while (curr != NULL) {
                Node* next = curr->next;
                delete curr;
                curr = next;
            }
        }
        // 在链表头部添加一个新节点
        void add(int value) {
            Node* newNode = new Node;
            newNode->data = value;
            newNode->next = head;
            head = newNode;
        }
        // 在链表尾部添加一个新节点
        void push(int value) {
            Node* newNode = new Node;
            newNode->data = value;
            newNode->next = NULL;
            if (head == NULL) {
                head = newNode;
            } else {
                Node* curr = head;
                while (curr->next != NULL) {
                    curr = curr->next;
                }
                curr->next = newNode;
            }
        }
        // 删除最后一个节点,并返回该节点的数据 
      int pop() {
          if (head == NULL) {
              return -1;
          } else if (head->next == NULL) {
              int data = head->data;
              delete head;
              head = NULL;
              return data;
          } else {
              Node* curr = head;
              while (curr->next->next != NULL) {
                  curr = curr->next;
              }
              int data = curr->next->data;
              delete curr->next;
              curr->next = NULL;
              return data;
            }
      }
        // 遍历链表,打印每个节点的数据
        void traverse() {
            Node* curr = head;
            while (curr != NULL) {
                cout << curr->data << "->";
                curr = curr->next;
            }
            cout << "nil" << endl;
        }
    };
    int main() {
        LinkedList list;
        list.traverse();  // 打印空链表 nil
        list.add(1);  // 在链表头部添加节点 1
        list.traverse();  // 打印链表 1->nil
        list.add(2);  // 在链表头部添加节点 2
        list.traverse();  // 打印链表 2->1->nil
        list.add(3);  // 在链表头部添加节点 3
        list.traverse();  // 打印链表 3->2->1->nil
        list.push(4);  // 在链表尾部添加节点 4
        list.traverse();  // 打印链表 3->2->1->4->nil
        list.push(5);  // 在链表尾部添加节点 5
        list.traverse();  // 打印链表 3->2->1->4->5->nil
        cout << list.pop() << endl;  // 删除尾节点,并输出节点数据
        list.traverse();  // 打印链表 3->2->1->4->nil
        cout << list.pop() << endl;  // 删除尾节点,并输出节点数据
        list.traverse();  // 打印链表 3->2->1->nil
      return 0;
    }

    image.gif

    class

    // 定义类 Node,表示链表中的节点

    class Node {

    public:

       int data;

       Node* next;

       Node(int value) {

           data = value;

           next = NULL;

       }

    };

    // 定义类 LinkedList,表示链表

    class LinkedList {

    private:

       Node* head;  // 指向链表头节点的指针

    };

    代码:

    #include <iostream>
    using namespace std;
    // 定义类 Node,表示链表中的节点
    class Node {
    public:
        int data;
        Node* next;
        Node(int value) {
            data = value;
            next = NULL;
        }
    };
    // 定义类 LinkedList,表示链表
    class LinkedList {
    private:
        Node* head;  // 指向链表头节点的指针
    public:
        // 构造函数,初始化链表为空链表
        LinkedList() {
            head = NULL;
        }
        // 析构函数,释放链表中的所有节点
        ~LinkedList() {
            Node* curr = head;
            while (curr != NULL) {
                Node* next = curr->next;
                delete curr;
                curr = next;
            }
        }
        // 在链表头部添加一个新节点
        void add(int value) {
            Node* newNode = new Node(value);
            newNode->next = head;
            head = newNode;
        }
        // 在链表尾部添加一个新节点
        void push(int value) {
            Node* newNode = new Node(value);
            newNode->next = NULL;
            if (head == NULL) {
                head = newNode;
            } else {
                Node* curr = head;
                while (curr->next != NULL) {
                    curr = curr->next;
                }
                curr->next = newNode;
            }
        }
        // 删除最后一个节点,并返回该节点的数据 
      int pop() {
          if (head == NULL) {
              return -1;
          } else if (head->next == NULL) {
              int data = head->data;
              delete head;
              head = NULL;
              return data;
          } else {
            Node* curr = head;
            while (curr->next->next != NULL) {
                curr = curr->next;
            }
            int data = curr->next->data;
            delete curr->next;
            curr->next = NULL;
            return data;
          }
      }
        // 遍历链表,打印每个节点的数据
        void traverse() {
            Node* curr = head;
            while (curr != NULL) {
                cout << curr->data << "->";
                curr = curr->next;
            }
            cout << "nil" << endl;
        }
    };
    int main() {
        LinkedList list;
        list.traverse();  // 打印空链表 nil
        list.add(1);  // 在链表头部添加节点 1
        list.traverse();  // 打印链表 1->nil
        list.add(2);  // 在链表头部添加节点 2
        list.traverse();  // 打印链表 2->1->nil
        list.add(3);  // 在链表头部添加节点 3
        list.traverse();  // 打印链表 3->2->1->nil
        list.push(4);  // 在链表尾部添加节点 4
        list.traverse();  // 打印链表 3->2->1->4->nil
        list.push(5);  // 在链表尾部添加节点 5
        list.traverse();  // 打印链表 3->2->1->4->5->nil
        cout << list.pop() << endl;  // 删除尾节点,并输出节点数据
        list.traverse();  // 打印链表 3->2->1->4->nil
        cout << list.pop() << endl;  // 删除尾节点,并输出节点数据
        list.traverse();  // 打印链表 3->2->1->nil
      return 0;
    }

    image.gif


    Java

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

    image.gif

    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;

       }

    }

    代码:

    public class LinkedList {
        public class Node {
            public int data;
            public Node next;
            public Node(int value) {
                data = value;
                next = null;
            }
        }
        public LinkedList() {
            head = null;
        }
        private Node head;
        // 在链表头部添加一个新的节点
        public void add(int value) {
            Node newNode = new Node(value);
            newNode.next = head;
            head = newNode;
        }
        // 在链表尾部添加一个新的节点
        public void push(int value) {
            Node newNode = new Node(value);
            if (head == null) {
                head = newNode;
            } else {
                Node curr = head;
                while (curr.next != null) {
                    curr = curr.next;
                }
                curr.next = newNode;
            }
        }
        // 删除尾节点,并返回该节点的数据
        public int pop() {
            if (head == null) {
                return -1;
            } else if (head.next == null) {
                int data = head.data;
                head = null;
                return data;
            } else {
                Node curr = head;
                while (curr.next.next != null) {
                    curr = curr.next;
                }
                Node tail = curr.next;
                curr.next = null;
                return tail.data;
            }
        }
        // 遍历链表,打印每个节点的数据
        public void traverse() {
            Node curr = head;
            while (curr != null) {
                System.out.print(curr.data + "->");
                curr = curr.next;
            }
            System.out.println("nil");
        }
        public static void main(String[] args) {
            LinkedList list = new LinkedList();
            list.traverse();  // 打印空链表 nil
            list.add(1);  // 在链表头部添加节点 1
            list.traverse();  // 打印链表 1->nil
            list.add(2);  // 在链表头部添加节点 2
            list.traverse();  // 打印链表 2->1->nil
            list.add(3);  // 在链表头部添加节点 3
            list.traverse();  // 打印链表 3->2->1->nil
            list.push(4);  // 在链表尾部添加节点 4
            list.traverse();  // 打印链表 3->2->1->4->nil
            list.push(5);  // 在链表尾部添加节点 5
            list.traverse();  // 打印链表 3->2->1->4->5->nil
            System.out.println(list.pop());  // 删除尾节点,并输出节点数据
            list.traverse();  // 打印链表 3->2->1->4->nil
            System.out.println(list.pop());  // 删除尾节点,并输出节点数据
            list.traverse();  // 打印链表 3->2->1->nil
        }
    }

    image.gif


    Python

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

    image.gif

    class

    class Node:

       def __init__(self, data):

           self.data = data  # 节点的数据

           self.next = None  # 节点的下一个指针,初始为空

    class LinkedList:

       def __init__(self):

           self.head = None  # 链表的头指针,初始为空

    代码:

    class Node:
        def __init__(self, data):
            self.data = data  # 节点的数据
            self.next = None  # 节点的下一个指针,初始为空
    class LinkedList:
        def __init__(self):
            self.head = None  # 链表的头指针,初始为空
        def add(self, data):
            # 在链表头部插入一个新节点
            newNode = Node(data)
            newNode.next = self.head
            self.head = newNode
        def push(self, data):
            # 在链表尾部添加一个新节点
            newNode = Node(data)
            if self.head is None:
                self.head = newNode
            else:
                curr = self.head
                while curr.next is not None:
                    curr = curr.next
                curr.next = newNode
        def pop(self):
            # 删除尾节点,并返回该节点的值
            if self.head is None:
                return None
            if self.head.next is None:
                data = self.head.data
                self.head = None
                return data
            curr = self.head
            while curr.next.next is not None:
                curr = curr.next
            tail = curr.next
            curr.next = None
            return tail.data
        def traverse(self):
            # 遍历链表,打印每个节点的数据
            curr = self.head
            while curr is not None:
                print(curr.data, end='->')
                curr = curr.next
            print('nil')
    if __name__ == '__main__':
        head = LinkedList() # 创建链表
        head.traverse()     # 遍历空链表
        head.add(1)         # 在链表头部添加节点 1
        head.traverse()     # 遍历链表 1->nil
        head.add(2)         # 在链表头部添加节点 2
        head.traverse()     # 遍历链表 2->1->nil
        head.add(3)         # 在链表头部添加节点 3
        head.traverse()     # 遍历链表 3->2->1->nil
        head.push(4)        # 在链表尾部添加节点 4
        head.traverse()     # 遍历链表 3->2->1->4->nil
        head.push(5)        # 在链表尾部添加节点 5
        head.traverse()     # 遍历链表 3->2->1->4->5->nil
        print(head.pop())   # 删除尾节点,并输出节点数据
        head.traverse()     # 打印链表 3->2->1->4->nil
        print(head.pop())   # 删除尾节点,并输出节点数据
        head.traverse()     # 打印链表 3->2->1->nil

    image.gif


    Golang

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

    image.gif

    struct

    type Node struct {

       data int

       next *Node

    }

    type LinkedList struct {

       head *Node

    }

    // 创建一个新的节点

    func new(value int) *Node {

       return &Node{

           data: value,

           next: nil,

       }

    }

    代码:

    package main
    import "fmt"
    type Node struct {
      data int
      next *Node
    }
    type LinkedList struct {
      head *Node
    }
    // 创建一个新的节点
    func new(value int) *Node {
      return &Node{
        data: value,
        next: nil,
      }
    }
    // 在链表头部添加一个新节点
    func (list *LinkedList) add(value int) {
      newNode := new(value)
      newNode.next = list.head
      list.head = newNode
    }
    // 在链表尾部添加一个新节点
    func (list *LinkedList) push(value int) {
      newNode := new(value)
      if list.head == nil {
        list.head = newNode
      } else {
        curr := list.head
        for curr.next != nil {
          curr = curr.next
        }
        curr.next = newNode
      }
    }
    // 删除尾节点,并返回该节点的值
    func (list *LinkedList) pop() int {
      if list.head == nil {
        return -1
      } else if list.head.next == nil {
        data := list.head.data
        list.head = nil
        return data
      } else {
        curr := list.head
        for curr.next.next != nil {
          curr = curr.next
        }
        tail := curr.next
        curr.next = nil
        return tail.data
      }
    }
    // 遍历链表,打印每个节点的数据
    func (list *LinkedList) traverse() {
      curr := list.head
      for curr != nil {
        fmt.Printf("%d->", curr.data)
        curr = curr.next
      }
      fmt.Println("nil")
    }
    func main() {
      list := LinkedList{}
      list.traverse()         // 打印空链表 nil
      list.add(1)             // 在链表头部添加节点 1
      list.traverse()         // 打印链表 1->nil
      list.add(2)             // 在链表头部添加节点 2
      list.traverse()         // 打印链表 2->1->nil
      list.add(3)             // 在链表头部添加节点 3
      list.traverse()         // 打印链表 3->2->1->nil
      list.push(4)            // 在链表尾部添加节点 4
      list.traverse()         // 打印链表 3->2->1->4->nil
      list.push(5)            // 在链表尾部添加节点 5
      list.traverse()         // 打印链表 3->2->1->4->5->nil
      fmt.Println(list.pop()) // 删除尾节点,并打印数据
      list.traverse()         // 打印链表 3->2->1->4->nil
      fmt.Println(list.pop()) // 删除尾节点,并打印数据
      list.traverse()         // 打印链表 3->2->1->nil
    }

    image.gif


    Rust

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

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

    image.gif

    struct

    struct Node {

       data: i32,

       next: Option<Box<Node>>,

    }

    impl Node {

       fn new(value: i32) -> Node {

           Node { data: value, next: None }

       }

    }

    struct LinkedList {

       head: Option<Box<Node>>,

    }

    impl LinkedList {

       fn new() -> LinkedList {

           LinkedList { head: None }

       }

    }

    代码:

    struct Node {
        data: i32,
        next: Option<Box<Node>>,
    }
    impl Node {
        fn new(value: i32) -> Node {
            Node { data: value, next: None }
        }
    }
    struct LinkedList {
        head: Option<Box<Node>>,
    }
    impl LinkedList {
        fn new() -> LinkedList {
            LinkedList { head: None }
        }
        // 在链表头部添加一个新节点
        fn add(&mut self, value: i32) {
            let mut new_node = Box::new(Node::new(value));
            new_node.next = self.head.take();
            self.head = Some(new_node);
        }
        // 在链表尾部添加一个新节点
        fn push(&mut self, value: i32) {
            let new_node = Box::new(Node::new(value));
            let mut curr = &mut self.head;
            while let Some(node) = curr {
                curr = &mut node.next;
            }
            *curr = Some(new_node);
        }
        // 删除尾节点,并返回该节点的数据
        fn pop(&mut self) -> Option<i32> {
            if self.head.is_none() {
                return None;
            }
            if self.head.as_ref().unwrap().next.is_none() {
                let data = self.head.take().unwrap().data;
                return Some(data);
            }
            let mut curr = self.head.as_mut().unwrap();
            while curr.next.as_ref().unwrap().next.is_some() {
                curr = curr.next.as_mut().unwrap();
            }
            let data = curr.next.take().unwrap().data;
            Some(data)
        }
        // 遍历链表,打印每个节点的数据
        fn traverse(&self) {
            let mut curr = &self.head;
            while let Some(node) = curr {
                print!("{}->", node.data);
                curr = &node.next;
            }
            println!("nil");
        }
    }
    fn main() {
        let mut list = LinkedList::new();
        list.traverse();  // 打印空链表 nil
        list.add(1);  // 在链表头部添加节点 1
        list.traverse();  // 打印链表 1->nil
        list.add(2);  // 在链表头部添加节点 2
        list.traverse();  // 打印链表 2->1->nil
        list.add(3);  // 在链表头部添加节点 3
        list.traverse();  // 打印链表 3->2->1->nil
        list.push(4);  // 在链表尾部添加节点 4
        list.traverse();  // 打印链表 3->2->1->4->nil
        list.push(5);  // 在链表尾部添加节点 5
        list.traverse();  // 打印链表 3->2->1->4->5->nil
        println!("{}", list.pop().unwrap());  // 删除尾节点,并输出节点数据
        list.traverse();  // 打印链表 3->2->1->4->nil
        println!("{}", list.pop().unwrap());  // 删除尾节点,并输出节点数据
        list.traverse();  // 打印链表 3->2->1->nil
    }

    image.gif

    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() }

       }

    }

    代码:

    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() }
        }
        fn add(&mut self, value: i32) {
            let mut new_node = Box::new(Node::new(value));
            new_node.next = self.head;
            self.head = Box::into_raw(new_node);
        }
        fn push(&mut self, value: i32) {
            let new_node = Box::new(Node::new(value));
            let mut curr = &mut self.head;
            while !(*curr).is_null() {
                curr = unsafe { &mut (**curr).next };
            }
            *curr = Box::into_raw(new_node);
        }
        fn pop(&mut self) -> Option<i32> {
            if self.head.is_null() {
                return None;
            }
            let mut curr = self.head;
            let mut prev = std::ptr::null_mut();
            while unsafe { !(*curr).next.is_null() } {
                prev = curr;
                curr = unsafe { (*curr).next };
            }
            let data = unsafe { Box::from_raw(curr) }.data;
            if prev.is_null() {
                self.head = std::ptr::null_mut();
            } else {
                unsafe { (*prev).next = std::ptr::null_mut(); }
            }
            Some(data)
        }
        fn traverse(&self) {
            let mut curr = self.head;
            while !curr.is_null() {
                unsafe {
                    print!("{}->", (*curr).data);
                    curr = (*curr).next;
                }
            }
            println!("nil");
        }
        fn cleanup(&mut self) {
            let mut curr = self.head;
            while !curr.is_null() {
                let next = unsafe { (*curr).next };
                unsafe { Box::from_raw(curr) };
                curr = next;
            }
        }
    }
    fn main() {
        let mut list = LinkedList::new();
        list.traverse();  // 打印空链表 nil
        list.add(1);
        list.traverse();
        list.add(2);
        list.traverse();
        list.add(3);
        list.traverse();
        list.push(4);
        list.traverse();
        list.push(5);
        list.traverse();
        println!("{}", list.pop().unwrap());
        list.traverse();
        println!("{}", list.pop().unwrap());
        list.traverse();
        list.cleanup();
    }

    image.gif

    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

    image.gif

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

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


    目录
    相关文章
    |
    3月前
    |
    人工智能 安全 Java
    Java和Python在企业中的应用情况
    Java和Python在企业中的应用情况
    94 7
    |
    4月前
    |
    数据采集 缓存 Java
    Python vs Java:爬虫任务中的效率比较
    Python vs Java:爬虫任务中的效率比较
    |
    3月前
    |
    Java 程序员 开发工具
    在比较Java和Python哪个更易学
    在比较Java和Python哪个更易学
    49 4
    |
    3月前
    |
    Java 程序员 Python
    Java和Python
    Java和Python
    34 2
    |
    5月前
    |
    Java
    java数据结构,双向链表的实现
    文章介绍了双向链表的实现,包括数据结构定义、插入和删除操作的代码实现,以及双向链表的其他操作方法,并提供了完整的Java代码实现。
    java数据结构,双向链表的实现
    |
    4月前
    |
    Rust 资源调度 安全
    为什么使用 Rust over C++ 进行 IoT 解决方案开发
    为什么使用 Rust over C++ 进行 IoT 解决方案开发
    128 7
    |
    4月前
    |
    存储 安全 Java
    【用Java学习数据结构系列】探索顺序表和链表的无尽秘密(附带练习唔)pro
    【用Java学习数据结构系列】探索顺序表和链表的无尽秘密(附带练习唔)pro
    35 3
    |
    4月前
    |
    Rust 监控 编译器
    解密 Python 如何调用 Rust 编译生成的动态链接库(一)
    解密 Python 如何调用 Rust 编译生成的动态链接库(一)
    91 2
    |
    4月前
    |
    Rust 安全 Python
    解密 Python 如何调用 Rust 编译生成的动态链接库(二)
    解密 Python 如何调用 Rust 编译生成的动态链接库(二)
    84 1
    |
    5月前
    |
    Java Linux Python
    Linux环境下 代码java调用python出错
    Linux环境下 代码java调用python出错
    91 4