索取营销诊断书
021-80394720QQ
您的位置：上海毫米网络优化公司 > 小程序 > 百度小程序 >
相关推荐recommended
单链表的多语言表达：C++、Java、Python、Go、Rust
作者：mmseoamin日期：2023-12-14

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

单链表

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

单链表的主要操作包括：

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

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

单链表的多语言表达：C++、Java、Python、Go、Rust,20210817204340750.png,第2张

本文总结了 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 
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;
}

class

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

class Node {

public:

    int data;

    Node* next;

    Node(int value) {

        data = value;

        next = NULL;

    }

};

// 定义类 LinkedList，表示链表

class LinkedList {

private:

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

};

代码：

#include 
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;
}

Java

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

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

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

Python

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

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

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

Golang

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

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

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
}

Rust

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

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

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

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 }

    }

}

代码：

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 }
    }
    // 在链表头部添加一个新节点
    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 {
        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
}

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

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

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

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

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

完

上一篇：【3w字吐血总结 | 新手必看】全网最详细Go笔记

下一篇：如何使用SpringSecurity

网站优化运营
整站seo优化
网络营销运营
成功案例
品牌创意网站
营销型网站
小程序
微信小程序
微信公众号
百度熊掌号
网站优化分享
关于我们
公司概况
公司新闻
公司文化
结构体系
企业资质
加入我们
关注我们
扫描二维码
获取更多信息
精彩一手掌握
Copyright © 2014-2019 seo,上海网站优化_网络制作_网站seo排名_网站建设推广_上海网络公司 版权所有 沪ICP备19022315号