建设微网站多少钱,wordpress端口,wordpress调用自定义分类标题,wordpress the_tags()单链表
是一种链式数据结构#xff0c;由一个头节点和一些指向下一个节点的指针组成。每个节点包含一个数据元素和指向下一个节点的指针。头节点没有数据#xff0c;只用于表示链表的开始位置。
单链表的主要操作包括#xff1a;
添加元素#xff1a;在链表的头部添加新…
单链表
是一种链式数据结构由一个头节点和一些指向下一个节点的指针组成。每个节点包含一个数据元素和指向下一个节点的指针。头节点没有数据只用于表示链表的开始位置。
单链表的主要操作包括
添加元素在链表的头部添加新元素需要修改头节点的指针。删除元素删除链表中的元素需要修改头节点和其他节点的指针。查找元素在链表中查找某个元素需要遍历整个链表。遍历链表按照链表的顺序依次访问每个元素需要遍历整个链表。
单链表相对于数组的优点是插入和删除元素时不需要移动其他元素时间复杂度为O(1)。但是在查找元素时单链表比数组要慢时间复杂度为O(n)。 本文总结了 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 iostreamusing 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(); // 打印空链表 nillist.add(1); // 在链表头部添加节点 1list.traverse(); // 打印链表 1-nillist.add(2); // 在链表头部添加节点 2list.traverse(); // 打印链表 2-1-nillist.add(3); // 在链表头部添加节点 3list.traverse(); // 打印链表 3-2-1-nillist.push(4); // 在链表尾部添加节点 4list.traverse(); // 打印链表 3-2-1-4-nillist.push(5); // 在链表尾部添加节点 5list.traverse(); // 打印链表 3-2-1-4-5-nilcout list.pop() endl; // 删除尾节点并输出节点数据list.traverse(); // 打印链表 3-2-1-4-nilcout list.pop() endl; // 删除尾节点并输出节点数据list.traverse(); // 打印链表 3-2-1-nilreturn 0;
}
class
// 定义类 Node表示链表中的节点 class Node { public: int data; Node* next; Node(int value) { data value; next NULL; } };
// 定义类 LinkedList表示链表 class LinkedList { private: Node* head; // 指向链表头节点的指针 };
代码
#include iostreamusing 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(); // 打印空链表 nillist.add(1); // 在链表头部添加节点 1list.traverse(); // 打印链表 1-nillist.add(2); // 在链表头部添加节点 2list.traverse(); // 打印链表 2-1-nillist.add(3); // 在链表头部添加节点 3list.traverse(); // 打印链表 3-2-1-nillist.push(4); // 在链表尾部添加节点 4list.traverse(); // 打印链表 3-2-1-4-nillist.push(5); // 在链表尾部添加节点 5list.traverse(); // 打印链表 3-2-1-4-5-nilcout list.pop() endl; // 删除尾节点并输出节点数据list.traverse(); // 打印链表 3-2-1-4-nilcout list.pop() endl; // 删除尾节点并输出节点数据list.traverse(); // 打印链表 3-2-1-nilreturn 0;
} 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; } }
代码
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(); // 打印空链表 nillist.add(1); // 在链表头部添加节点 1list.traverse(); // 打印链表 1-nillist.add(2); // 在链表头部添加节点 2list.traverse(); // 打印链表 2-1-nillist.add(3); // 在链表头部添加节点 3list.traverse(); // 打印链表 3-2-1-nillist.push(4); // 在链表尾部添加节点 4list.traverse(); // 打印链表 3-2-1-4-nillist.push(5); // 在链表尾部添加节点 5list.traverse(); // 打印链表 3-2-1-4-5-nilSystem.out.println(list.pop()); // 删除尾节点并输出节点数据list.traverse(); // 打印链表 3-2-1-4-nilSystem.out.println(list.pop()); // 删除尾节点并输出节点数据list.traverse(); // 打印链表 3-2-1-nil}
} 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 # 链表的头指针初始为空
代码
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.headself.head newNodedef push(self, data):# 在链表尾部添加一个新节点newNode Node(data)if self.head is None:self.head newNodeelse:curr self.headwhile curr.next is not None:curr curr.nextcurr.next newNodedef pop(self):# 删除尾节点并返回该节点的值if self.head is None:return Noneif self.head.next is None:data self.head.dataself.head Nonereturn datacurr self.headwhile curr.next.next is not None:curr curr.nexttail curr.nextcurr.next Nonereturn tail.datadef traverse(self):# 遍历链表打印每个节点的数据curr self.headwhile curr is not None:print(curr.data, end-)curr curr.nextprint(nil)if __name__ __main__:head LinkedList() # 创建链表head.traverse() # 遍历空链表head.add(1) # 在链表头部添加节点 1head.traverse() # 遍历链表 1-nilhead.add(2) # 在链表头部添加节点 2head.traverse() # 遍历链表 2-1-nilhead.add(3) # 在链表头部添加节点 3head.traverse() # 遍历链表 3-2-1-nilhead.push(4) # 在链表尾部添加节点 4head.traverse() # 遍历链表 3-2-1-4-nilhead.push(5) # 在链表尾部添加节点 5head.traverse() # 遍历链表 3-2-1-4-5-nilprint(head.pop()) # 删除尾节点并输出节点数据head.traverse() # 打印链表 3-2-1-4-nilprint(head.pop()) # 删除尾节点并输出节点数据head.traverse() # 打印链表 3-2-1-nilGolang
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, } }
代码
package mainimport fmttype Node struct {data intnext *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.headlist.head newNode
}// 在链表尾部添加一个新节点
func (list *LinkedList) push(value int) {newNode : new(value)if list.head nil {list.head newNode} else {curr : list.headfor 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.datalist.head nilreturn data} else {curr : list.headfor curr.next.next ! nil {curr curr.next}tail : curr.nextcurr.next nilreturn tail.data}
}// 遍历链表打印每个节点的数据
func (list *LinkedList) traverse() {curr : list.headfor curr ! nil {fmt.Printf(%d-, curr.data)curr curr.next}fmt.Println(nil)
}func main() {list : LinkedList{}list.traverse() // 打印空链表 nillist.add(1) // 在链表头部添加节点 1list.traverse() // 打印链表 1-nillist.add(2) // 在链表头部添加节点 2list.traverse() // 打印链表 2-1-nillist.add(3) // 在链表头部添加节点 3list.traverse() // 打印链表 3-2-1-nillist.push(4) // 在链表尾部添加节点 4list.traverse() // 打印链表 3-2-1-4-nillist.push(5) // 在链表尾部添加节点 5list.traverse() // 打印链表 3-2-1-4-5-nilfmt.Println(list.pop()) // 删除尾节点并打印数据list.traverse() // 打印链表 3-2-1-4-nilfmt.Println(list.pop()) // 删除尾节点并打印数据list.traverse() // 打印链表 3-2-1-nil
}Rust
Rust中也没有类的概念但它提供了结构体 struct 和 trait 两种重要的机制来实现面向对象的编程风格。结构体用于定义数据结构而 trait 则用于定义方法集合。
另外在Rust中一般不使用unsafe指针std::ptr来操作链表而是 Option 类型来表示链表指针它代表的值可以存在Some也可以不存在None。Option 类型被广泛用于处理可能为空的值以避免出现空指针异常。 struct
struct Node { data: i32, next: OptionBoxNode, }
impl Node { fn new(value: i32) - Node { Node { data: value, next: None } } }
struct LinkedList { head: OptionBoxNode, }
impl LinkedList { fn new() - LinkedList { LinkedList { head: None } } }
代码
struct Node {data: i32,next: OptionBoxNode,
}impl Node {fn new(value: i32) - Node {Node { data: value, next: None }}
}struct LinkedList {head: OptionBoxNode,
}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) - Optioni32 {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(); // 打印空链表 nillist.add(1); // 在链表头部添加节点 1list.traverse(); // 打印链表 1-nillist.add(2); // 在链表头部添加节点 2list.traverse(); // 打印链表 2-1-nillist.add(3); // 在链表头部添加节点 3list.traverse(); // 打印链表 3-2-1-nillist.push(4); // 在链表尾部添加节点 4list.traverse(); // 打印链表 3-2-1-4-nillist.push(5); // 在链表尾部添加节点 5list.traverse(); // 打印链表 3-2-1-4-5-nilprintln!({}, list.pop().unwrap()); // 删除尾节点并输出节点数据list.traverse(); // 打印链表 3-2-1-4-nilprintln!({}, 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) - Optioni32 {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(); // 打印空链表 nillist.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 其中Rust的节点值有点特殊使用了Some类型。比如
使用println!({:?}, list.pop()); 不需要pop()后面的.unwrap()返回Some(n)当链表为空时直接返回None。 完
