初识链表 By Swift

初识链表 By Swift

IOS小彩虹2021-08-17 15:37:31200A+A-

Github

初识链表

链表:链式结构,使用节点来存储内容,通过当前节点的 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
    }
}

点击这里复制本文地址 以上内容由权冠洲的博客整理呈现,请务必在转载分享时注明本文地址!如对内容有疑问,请联系我们,谢谢!

支持Ctrl+Enter提交

联系我们| 本站介绍| 留言建议 | 交换友链 | 域名展示
本站资源来自互联网收集,仅供用于学习和交流,请遵循相关法律法规,本站一切资源不代表本站立场,如有侵权、后门、不妥请联系本站删除

权冠洲的博客 © All Rights Reserved.  Copyright quanguanzhou.top All Rights Reserved
苏公网安备 32030302000848号   苏ICP备20033101号-1
本网站由 提供CDN/云存储服务

联系我们