算法不分语言,重要的是思想,这里我用swift来记录算法的实现,供大家一起学习.
首先我们看下链表的结构
屏幕快照 2017-12-04 上午11.53.23.png
2,双链表
屏幕快照 2017-12-04 上午11.55.11.png
我们主要讲解双链表
在这里我们创建一个链表类和节点类(下方代码)
/// 声明链表类
public final class LinkedList<T>{
/// 声明节点类
public class LinkedListNode<T>{
var value: T
var next: LinkedListNode<T>?
weak var previous: LinkedListNode<T>? //这里使用week避免循环引用
public init(value: T) {
self.value = value
}
}
/// 重命名节点类,方便使用
public typealias Node = LinkedListNode<T>
/// 链表头节点
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..<index {
node = node?.next
if node == nil {
break
}
}
assert(node != nil, "index 超出接线")
return node!
}
}
/// 获得指定下标节点的内容
///
/// - Parameter index: 链表中第几个节点(从0开始)
public func value(index: Int) -> 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 = newNode
newNode.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.next
if 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<String>()
list.isEmpty //true
list.first //nil
list.last //nil
list.append("小码儿") //[小码儿]
list.isEmpty //false
list.first!.value //"小码儿"
list.last!.value //"小码儿"
list.count //1
list.append("666") //[小码儿,666]
list.first!.value //"小码儿"
list.last!.value //"666"
list.count //2
list.first!.previous //nil
list.first!.next!.value //"666"
list.last!.previous!.value //"666"
list.last!.next //nil
list.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? = nil
while node1 != nil{
node2 = node1
node1 = node1!.next
node2!.next = node3
node3 = node2
head = node2
}
}
今天先到这里,以后关于链表的问题会不断的补充进来
