初识链表 By Swift__GodIsCoder的专栏文章_微信文章

初识链表

链表：链式结构，使用节点来存储内容，通过当前节点的 next 指针指向下一个节点。可以通过分散的内存来存储节点，因此内存利用率更高，占用内存空间更小。但因为只有通过 next 指针才能找到下一个节点，所以每次查找节点都需要从头结点开始。

因为 next 指针的关系，它的查找效率和修改的效率不如数组，但添加和删除的效率要高于数组。

结构图：

          (Node)           (Node)           (Node)
        -----------      -----------      -----------
        |         |      |         |      |         |
head--> |  value  | ---> |  value  | ---> |  value  | --> nil
        |         |      |         |      |         |
        -----------      -----------      -----------
复制代码

定义一个链表

class Node {
    var val: Int
    var next: Node?
    
    init(val: Int, next: Node?) {
        self.val = val
        self.next = next
    }
}

class LinkList {
    var dummy: Node?
    var size: Int
    
    init() {
        dummy = Node(val: 0, next: nil)
        size = 0
    }

    private func node(_ index: Int) -> Node? {
        var curNode = dummy?.next
        var curIndex = index
        
        while curIndex > 0 {
            curNode = curNode?.next
            curIndex -= 1
        }
        return curNode
    }
}
复制代码

首先声明一个包含 val 和 next 的 Node 类。val 用来存储值，而 next 用来指向下一个节点。

然后再声明一个名 LinkList 类来代表链表。dummy 的 next 用来指向头结点，size 用来存储链表的当前长度。

这里需要说明的是，为什么要设置 dummy 节点。因为这样做是可以避免在添加第一个节点时的很多逻辑判断。

最后，创建一个 node(_:) 的私有函数，用来获取当前 index 的节点。

添加

public func append(val: Int) {
    let newNode = Node(val: val, next: nil)
    
    if size == 0 {
        dummy?.next = newNode
    } else {
        var curSize = size
        var curNode = dummy
        
        while curSize > 0 {
            curNode = curNode?.next
            curSize -= 1
        }
        curNode?.next = newNode
    }
    
    size += 1
}
复制代码

在尾部添加节点有以下两种情况：

condition 1：size == 0，说明没有链表未保存节点。
condition 2：size > 0，链表已经保存节点，只需要找到尾结点即可。

在 condition 1 的情况下，将 dummy 的 next 指向 newNode 即可，而在 condition 2 的情况下，寻找到尾结点，将尾结点的 next 指向 newNode。

最后，不要忘记将 size + 1。

删除

public func remove(_ index: Int) -> Int? {
    guard index > -1 && index < size else { return nil }
    let val: Int
    if index == 0 {
        val = dummy?.next?.val ?? 0
        dummy?.next = dummy?.next?.next
    } else {
        let prev = node(index - 1)
        val = prev?.next?.val ?? 0
        prev?.next = prev?.next?.next
    }
    size -= 1
    return val
}
复制代码

进行移除操作时，需要对 index 的合法性进行校验。

移除操作同添加操作也是有以下两种情况：

condition 1：移除头结点。
condition 2：移除其它节点。

移除操作的核心就是找到需要移除节点的前一个节点 prev（通过 node(_:) 可以获得），将 prev 的 next 指针指向它 next 的 next 即可。如：prev?.next = prev?.next?.next。

最后不要忘记 size - 1 。

插入

public func insert(_ val: Int, atIndex index: Int) {
    guard index > -1 && index <= size else { return }
    let newNode = Node(val: val, next: nil)
    
    if index == 0 {
        newNode.next = dummy?.next
        dummy?.next = newNode
    } else {
        let pre = node(index - 1)
        newNode.next = pre?.next
        pre?.next = newNode
    }
    
    size += 1
}
复制代码

插入操作相对来说是比较复杂的一个操作，要考虑好 index == 0，index == size 等条件的情况。

插入操作的核心操作分两步：

将新建节点 newNode 的 next 指向当前 index 的节点。
将当前节点的 prev 节点的 next 指向新建节点 newNode。

以上两步的顺序很重要，切记不要搞错。

通过上面的步骤来分析插入操作的代码。当 index == 0 时，说明要在头结点的位置进行插入，首先进行第一步：将 newNode 的 next 指向当前 index 的节点 - newNode.next = dummy?.next;接着进行第二步：将当前节点的 prev 节点的 next 指向新建节点 newNode - dummy?.next = newNode。

当 index > 0 时同上。最后不要忘记 size + 1 。

查询

public func get(_ index: Int) -> Int? {
    guard index > -1 && index < size - 1 else { return nil }
    return node(index)?.val
}
复制代码

查询操作是最简单的一个。只需要判断下 index 的有效性，然后通过 node(_:) 获取相应的节点即可。

以上，就是链表基本操作的实现。

扩展

支持泛型

上面的示例代码只支持存储 Int 类型的数据，而在项目中可能需要支持多种类型，所以将其改成支持泛型还是很有必要的。

class Node<Element> {
    var val: Element?
    var next: Node?
    
    init(val: Element?, next: Node?) {
        self.val = val
        self.next = next
    }
}

class LinkList<Element> {
    var dummy: Node<Element>?
    var size: Int
    
    public init() {
        dummy = Node(val: nil, next: nil)
        size = 0
    }
    
    public func append(val: Element) {
        let newNode = Node(val: val, next: nil)
        
        if size == 0 {
            dummy?.next = newNode
        } else {
            // 查找尾结点
            var curSize = size
            var curNode = dummy
            
            while curSize > 0 {
                curNode = curNode?.next
                curSize -= 1
            }
            curNode?.next = newNode
        }
        
        size += 1
    }
    
    public func remove(_ index: Int) -> Element? {
        guard index > -1 && index < size else { return nil }
        let val: Element?
        if index == 0 {
            val = dummy?.next?.val
            dummy?.next = dummy?.next?.next
        } else {
            let prev = node(index - 1)
            val = prev?.next?.val
            prev?.next = prev?.next?.next
        }
        size -= 1
        return val
    }
    
    public func get(_ index: Int) -> Element? {
        guard index > -1 && index < size - 1 else { return nil }
        return node(index)?.val
    }
    
    public func insert(_ val: Element, atIndex index: Int) {
        guard index > -1 && index <= size else { return }
        let newNode = Node(val: val, next: nil)
        
        if index == 0 {
            newNode.next = dummy?.next
            dummy?.next = newNode
        } else {
            let pre = node(index - 1)
            newNode.next = pre?.next
            pre?.next = newNode
        }
        
        size += 1
    }
    
    private func node(_ index: Int) -> Node<Element>? {
        var curNode = dummy?.next
        var curIndex = index
        
        while curIndex > 0 {
            curNode = curNode?.next
            curIndex -= 1
        }
        return curNode
    }
}

复制代码

支持索引

通过重写 subscript 也可以支持索引操作。

extension LinkList {
    public subscript(index: Int) -> Element? {
        return node(index)?.val
    }
}
复制代码