单向链表
链表就是一串节点，每个Node中有两个关键参数
1、节点Node的值，value
2、持有的下一个Node的引用，nil表示链表最后一个Node
如创建一个基本的Node类，并重写description
public class FMNode<T> {
public var val:T
var nextNode:FMNode?
init(val:T,nextNode:FMNode? = nil) {
self.val = val
self.nextNode = nextNode
}
}
extension FMNode:CustomStringConvertible{
public var description: String{
guard let nextNode = nextNode else {
return "\(val)"
}
return "\(val) -> " + String(describing: nextNode)
}
}
如果我们要使用该节点，则需要用ListNode来管理这些节点
public struct FMListNode<T>{
public var head:FMNode<T>?
public var size:NSInteger = 0
public init(){
}
public var isEmpty:Bool {
return head == nil
}
}
extension FMListNode:CustomStringConvertible {
public var description: String{
guard let head = head else {
return "Empty list"
}
return String(describing: head)
}
}
在这里，为了方便以后使用该链表，我们可以添加如下几种方法：
-
push: 从头部添加数据 -
append: 从尾部添加数据 -
get:获取某个节点的数据 -
remove：删除某个节点 -
reverse:反转链表
其完整代码如下：
public class FMNode<T> {
public var val:T
var nextNode:FMNode?
init(val:T,nextNode:FMNode? = nil) {
self.val = val
self.nextNode = nextNode
}
}
extension FMNode:CustomStringConvertible{
public var description: String{
guard let nextNode = nextNode else {
return "\(val)"
}
return "\(val) -> " + String(describing: nextNode)
}
}
public struct FMListNode<T>{
public var head:FMNode<T>?
public var size:NSInteger = 0
public init(){
}
public var isEmpty:Bool {
return head == nil
}
}
extension FMListNode:CustomStringConvertible {
public var description: String{
guard let head = head else {
return "Empty list"
}
return String(describing: head)
}
}
extension FMListNode {
//从头部增加结点
mutating func pushNode(val:T){
let node = FMNode(val: val, nextNode: head)
node.nextNode = head
head = node
size = size + 1
}
//从尾部增加结点
mutating func appendNode(val:T){
let node = FMNode(val: val,nextNode:nil)
let tail = self.getNode(at: size - 1)
if tail == nil {
head = node
}else{
tail!.nextNode = node
}
size = size + 1
}
//获取某个结点
func getNode(at:NSInteger) -> FMNode<T>?{
if isEmpty || head == nil || size == 0 || at < 0 || !(at < size){
return nil
}
var location:NSInteger = 0
var nextNode = head
while nextNode != nil {
if at == location {
return nextNode
}
nextNode = nextNode!.nextNode
location = location + 1
}
return nil
}
//删除某个结点
mutating func removeNode(at:NSInteger) -> Bool{
if isEmpty || head == nil || size == 0 || at < 0 || !(at < size){
return false
}
if at == 0 {
let mid = head?.nextNode
head = mid
size = size - 1
return true
}
var location:NSInteger = 1
var middleNode:FMNode<T> = head!
while middleNode.nextNode != nil {
if at == location {
let mid = middleNode.nextNode!.nextNode
middleNode.nextNode = mid
size = size - 1
return true
}
middleNode = middleNode.nextNode!
location = location + 1
}
return false
}
}
extension FMListNode{
//反转单向链表
mutating func reverseList(){
if isEmpty {
return
}
var preNode:FMNode<T>? = nil
var currentNode:FMNode<T> = head!
print(self)
//0 -> 2 -> 4 -> 6 -> 8
while currentNode.nextNode != nil {
let nextNode:FMNode<T> = currentNode.nextNode!
currentNode.nextNode = preNode
preNode = currentNode
currentNode = nextNode
}
currentNode.nextNode = preNode
head = currentNode
}
}
