算法--Swift--链表算法--Swift--链表

算法不分语言,重要的是思想,这里我用swift来记录算法的实现,供大家一起学习.
首先我们看下链表的结构

1.单链表
文章图片
屏幕快照 2017-12-04 上午11.53.23.png
2,双链表
文章图片
屏幕快照 2017-12-04 上午11.55.11.png
我们主要讲解双链表
在这里我们创建一个链表类和节点类(下方代码)

/// 声明链表类 public final class LinkedList{ /// 声明节点类 public class LinkedListNode{ var value: T var next: LinkedListNode? weak var previous: LinkedListNode? //这里使用week避免循环引用public init(value: T) { self.value = https://www.it610.com/article/value } }/// 重命名节点类,方便使用 public typealias Node = LinkedListNode/// 链表头节点 fileprivate var head: Node?/// 链表初始化 public init() {}}

下面为该链表添加基本的属性和方法

/// 判断链表是否空 public var isEmpty: Bool { return head == nil }/// 获取链表第一个节点 public var first: Node? { return head }/// 获取最后一个节点 public var last: Node?{ guard var node = head else { return nil }while let next = node.next { node = next } return node }/// 计算节点的个数 public var count: Int {guard var node = head else { return 0 }var count: Int = 1 while let next = node.next { node = next count += 1 } return count }/// 获得某个位置的节点 /// /// - Parameter index: 链表中第几个节点(从0开始) /// - Returns: Optional LinkedListNode public func node(at index: Int) -> Node! { assert(head != nil ,"链表为空") assert(index >= 0, "index 必须大于等于0")if index == 0 { return head! }else { var node = head!.next for _ in 1.. T { let node = self.node(at: index) return node!.value }/// 添加一个节点到链表的尾部 public func append(_ node: Node!){ if head == nil { head = node return }last!.next = node node.previous = last }/// 添加一个value值到链表的尾部 public func append(_ value: T) { let newNode = Node(value: value) self.append(newNode) }/// 插入一个节点到链表中 public func insert(_ newNode: Node!, at index: Int) { if index == 0 { newNode.next = head head?.previous = newNode head = newNode }else { let nextNode = node(at: index) let previousNode = node(at: index - 1)newNode.next = nextNode nextNode?.previous = newNodenewNode.previous = previousNode previousNode?.next = newNode } }/// 插入一个value到链表中 public func insert(value: T, at index: Int){ let newNode = Node(value: value) self.insert(newNode, at: index) }/// 移除所有的 node/value public func removeAll() { head = nil }/// 移除某个节点 public func remove(node: Node!) { assert(head != nil, "该链表没有节点")let previousNode: Node? = node.previous let nextNode: Node? = node.nextif previousNode == nil { head = nextNode }else{ previousNode!.next = nextNode nextNode?.previous = previousNode }node.previous = nil node.next = nil }/// 移除指定位置的节点 public func remove(at index: Int) { let node = self.node(at: index) self.remove(node: node) }

写完方法,让我们做下简单的测试吧,验证链表的正确性

let list = LinkedList() list.isEmpty//true list.first//nil list.last//nillist.append("小码儿")//[小码儿] list.isEmpty//false list.first!.value//"小码儿" list.last!.value//"小码儿" list.count//1list.append("666")//[小码儿,666] list.first!.value//"小码儿" list.last!.value//"666" list.count//2list.first!.previous//nil list.first!.next!.value//"666" list.last!.previous!.value//"666" list.last!.next//nillist.node(at: 0).value//"小码儿" list.node(at: 1).value//"666" list.insert(value: "mySwift", at: 1)//[小码儿,mySwift,666] list.remove(at: 1)//[小码儿,666]

上方链表的基本操作都已经完成,为了更好的理解,现在让我们一起做下扩展吧:
1.扩展打印链表的方法,方便我们查看

/// 打印链表当我们调用print 格式 ["value1","value2"] extension LinkedList: CustomStringConvertible { public var description: String { var node = head var text: String = "[" while node != nil { text += "\(node!.value)" node = node!.next if node != nil { text += "," } } return text + "]" } }

2.将列表反转

//反转链表(通过迭代的方式反转,这里需要重点理解下) extension LinkedList { public func reverse() { var node = head while let currentNode = node { node = currentNode.next swap(¤tNode.next, ¤tNode.previous) head = currentNode } } }

同时附上单链表的反转

/// 实现单链表的反转(迭代) public func reverseLinkList(){ var node1: Node? = head var node2: Node? = nil var node3: Node? = nilwhile node1 != nil{ node2 = node1 node1 = node1!.nextnode2!.next = node3node3 = node2 head = node2 } }

【算法--Swift--链表】今天先到这里,以后关于链表的问题会不断的补充进来