数据结构

数据结构-单向链表

Posted by sunzhongliang on March 1, 2020

数据结构是计算机存储、组织数据的方式
本文演示代码为Swift语言

链表

在前篇描述了动态数组，但动态数组有个明显的缺点:
可能会造成内存空间的大量浪费(因为一开始申请动态数组的时候，就在内存当中开辟了固定长度的空间，而且每次删除等还会对动态数组当中的元素内存进行移位)
有没一种数据结构可以使用多少就申请多少内存呢？
链表就可以办到，链表分为单向链表和双向链表, 单向链表指的是只能通过next查找下一个节点，而不能通过prev查找上节点(只能是往后面查找元素)
本文先讲解单向链表:

链表是一种链式存储的线性表，所有元素的内存地址不一定是连续的

链表的设计

链表类当中应当有size属性和first属性，first指向了第一个Node(Node应当设计为class)，每次向链表中添加数据时应该修改first指针指向的Node，这样就实现了每次使用多少内存就申请多少内存

接口设计

链表的大部分接口和动态数组是一致的

方法：
清空元素 - clear()
添加元素 - add(int index, T element)
删除元素 - remove(int index)

完整代码：

/// 单向链表
class SingleLinkList<T: Comparable> {
    var size: Int = 0
    var firstNode: Node<T>? = nil
    
    class Node<T> {
        var element: T
        var nextNode: Node<T>?
        
        init(element: T, nextNode: Node<T>?) {
            self.element = element
            self.nextNode = nextNode
        }
    }
    
    /// 清空链表
    func clear() {
        self.size = 0
        self.firstNode = nil
    }
    
    /// 删除index位置的节点
    ///
    /// - Parameter index: index
    /// - Returns: 删除的节点
    func remove(index: Int) -> T {
        if index == 0 {
            let node: Node<T> = self.firstNode!
            self.firstNode = firstNode?.nextNode
            self.size = self.size - 1
            return node.element
        }
        else {
            let previous: Node<T> = self.node(index: index - 1)
            previous.nextNode = previous.nextNode!.nextNode
            self.size = self.size - 1
            return previous.element
        }
    }
    
    /// 在index位置添加新节点
    ///
    /// - Parameters:
    ///   - index: index
    ///   - element: 节点
    func add(index: Int, element: T) {
        // 如果要添加的位置在头节点(头结点的上一个节点为nil，因此需要特殊判断)
        if index == 0 {
            let newNode: Node<T> = SingleLinkList.Node(element: element, nextNode: self.firstNode)
            self.firstNode = newNode
        }
        else {
            // 取出要设置节点位置的前一个节点
            let previous: Node<T> = self.node(index: index - 1)
            // 初始化新的node(构造函数设置下一个节点为要添加位置节点的下一个节点)
            let newNode: Node<T> = SingleLinkList.Node(element: element, nextNode: previous.nextNode);
            // 指向要新创建的节点, 链表串联起来了
            previous.nextNode = newNode
        }
        
        self.size = self.size + 1
    }
    
    func add(element: T) {
        if self.size == 0 {
            // 初始化新的node(构造函数设置下一个节点为要添加位置节点的下一个节点)
            let newNode: Node<T> = SingleLinkList.Node(element: element, nextNode: nil);
            self.firstNode = newNode
        }
        else {
            // 取出要设置节点位置的前一个节点
            let previous: Node<T> = self.node(index: self.size - 1)
            // 初始化新的node(构造函数设置下一个节点为要添加位置节点的下一个节点)
            let newNode: Node<T> = SingleLinkList.Node(element: element, nextNode: previous.nextNode);
            // 指向要新创建的节点, 链表串联起来了
            previous.nextNode = newNode
        }
        
        self.size = self.size + 1
    }
    
    /// 获取index位置的节点
    ///
    /// - Parameter index: index
    /// - Returns: 节点
    func get(index: Int) -> Node<T> {
        return self.node(index: index)
    }
    
    
    /// 根据index设置对应位置的节点
    ///
    /// - Parameters:
    ///   - index: index
    ///   - element: 节点
    /// - Returns: 旧节点值
    func set(index: Int, element: T) -> T {
        // 取出当前位置的Node
        let node: Node<T> = self.node(index: index)
        
        // 旧节点
        let oldElement: T = node.element;
        // 设置新的element
        node.element = element
        
        return oldElement
    }
    
    /// 获取节点指定的index索引
    ///
    /// - Parameter element: 节点
    /// - Returns: index
    func indexOf(element: T?) -> Int {
        if element == nil {
            var node: Node<T>? = self.firstNode
            for i in 0..<self.size {
                if node?.element == nil {
                    return i
                }
                node = node!.nextNode!
            }
        }
        else {
            var node: Node<T> = self.firstNode!
            
            for i in 0..<self.size {
                if element == node.element {
                    return i
                }
                node = node.nextNode!
            }
        }
        
        return -1
    }
    
    
    /// 根据index查找node节点
    ///
    /// - Parameter index: 索引
    /// - Returns: node节点
    private func node(index: Int) -> Node<T> {
        if index > self.size {
            // TODO: 索引检查
            
        }
        var node: Node<T>? = self.firstNode
        
        for _ in 0..<index {
            node = node!.nextNode
        }
        return node!
    }
    
    func toString() -> Void {
        var node: Node<T>? = self.firstNode
        for _ in 0..<self.size {
            print(node?.element ?? "")
            node = node?.nextNode
        }
    }
    
    enum LinkListError: Error {
        case invalidSelection
        case insufficientFunds(coinsNeed: Int)
        case indexOutOfBounds(index: Int, size: Int)
    }
}

调用：

let list = SingleLinkList<String>()
list.add(index: 0, element: "1111")
list.add(index: 1, element: "2222")
list.add(index: 2, element: "3333")

print("向链表中添加元素：1111、2222、3333")
list.toString()

// 删除操作
list.remove(index: 1)
print("删除第2个节点后的链表元素：")
list.toString()

// 覆盖
list.set(index: 0, element: "0000")
print("向第0个节点覆盖新值：0000")
list.toString()

print("获取第二个节点的数据")
print(list.get(index: 1))

输出：

算法练习

在算法-复杂度当中介绍到算法的优化方向，而链表就属于时间换空间的一种思路(占用较少的内存空间，但查找链表元素时需要花费时间，因为不同于数组有index索引); 涉及到链表的算法也必然会很多

练习 - 删除链表中的节点

详细地址：删除链表中的节点

思路分析：常规思路肯定是for循环或者while循环遍历链表元素，判断遍历元素和要删除的节点值是否一致，如果一致就进行删除操作(将要删除的节点的前节点，指向要删除节点的下节点)
但这个肯定不是最优算法, 注意题目当中给定的条件，输入node=5，给的是一个node节点，通过给的node节点我们是不是可以找到next节点，找到了next节点将next节点的值赋值给传入的要删除的节点node=5，然后将要删除的节点node=5的next指向要删除的节点的next的next，画个图来分析一下： 实际操作：

练习 - 翻转一个链表

翻转一个链表

示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

递归方式：

let list = SingleLinkList<String>()
list.add(element: "1")
list.add(element: "2")
list.add(element: "3")
list.add(element: "4")
list.add(element: "5")

// 反转
func reverseList(head: SingleLinkList<String>.Node<String>?) -> SingleLinkList<String>.Node<String>? {
    if head == nil {
        return nil
    }
    if head!.nextNode == nil {
        return head
    }
    let newHead = reverseList(head: head!.nextNode)
    head!.nextNode?.nextNode = head
    head!.nextNode = nil
    
    return newHead
}

let newHead = reverseList(head: list.firstNode)

while循环方式:

// while 循环翻转
// head、newHead、tmp来实现
func reverseList_While(head :inout LinkList<String>.Node<String>?) -> LinkList<String>.Node<String>? {
    var newHead: LinkList<String>.Node<String>?
    while head != nil {
        // 取出当前循环的下一个节点，用tmp指向
        let tmp = head?.nextNode
        // 赋值当前节点的next为newHead
        head?.nextNode = newHead
        // newHead赋值为当前节点
        newHead = head
        // 当前节点=tmp
        head = tmp
    }
    return newHead
}

let newHead2 = reverseList_While(head: &list.firstNode)

while循环法，是使用了一个tmp变量将后面的节点保存下来，然后用head.next指向下一个节点赋值给newHead, 然后不断的循环来往前面指向newHead元素的方式来达到反转(核心思路是head指向的元素只有一个，然后head.next=newHead)
第一次：tmp = 2->3->4->5
head = 1 然后head.next = newHead newHead = head
最后变为 newHead = 1 head = 2->3->4->5
第二次：tmp = 3->4->5
head = 2 然后head.next = newHead newHead = head
最后变为 newHead = 2->1 head = 3->4->5
以此类推

练习 - 判断一个链表是否有环

详细地址:环形链表

环形链表：链表当中的某个节点的next又指向了链表当中的某个节点，形成了一个闭合的链表

解决思路
利用快慢指针方式，慢指针每次走一步，快指针每次走两步，一直循环，若存在环形链表则两个指针必然会重合, 若不存在环形链表则快指针指向节点会先为nil（这就好比钟表当中的秒针和分针，必然会重合在一起）

// 判断链表是否有环
func hasCycle(head: LinkList<String>.Node<String>?) -> Bool {
    if head == nil || head?.nextNode == nil {
        return false
    }
    
    var slow = head
    var fast = head?.nextNode
    while fast != nil && fast?.nextNode != nil {
        slow = slow?.nextNode
        fast = fast?.nextNode?.nextNode
        if slow == fast {
            return true
        }
    }
    
    return false
}

练习 - 链表的中间节点

给定一个带有头结点 head 的非空单链表，返回链表的中间结点。
如果有两个中间结点，则返回第二个中间结点。

示例 1：
输入：[1,2,3,4,5]
输出：3

示例 2：
输入：[1,2]
输出：2

解决思路
利用快慢指针，当慢指针遍历列表时，让快指针的速度是它的两倍。
当快指针到达列表的末尾时，慢指针必然位于中间。
此方案复杂度：时间复杂度：O(n)，空间复杂度O(1)

func middleNode(_ head: ListNode?) -> ListNode? {
    // 快慢指针法
    var slow = head
    var fast = head
    while fast != nil && fast?.next != nil {
        fast = fast?.next?.next
        slow = slow?.next
    }
    return slow
}

练习 - 删除链表中的重复元素

题目：给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次
示例：1->1->2 删除后变为 1->2


解决思路
由于题目的条件是链表是排序链表，因此可以遍历链表，找到链表的当前节点和下一节点进行比较， 如果相等就将指针指向next.next即可

func deleteDuplicates(_ head: ListNode?) -> ListNode? {
    var current = head
    var next = head?.next
    while next != nil {
        if current?.val == next?.val {
            current?.next = next?.next
            next = next?.next
        }
        else {
            current = next
            next = next?.next
        }
    }
    return head
}

本文首次发布于 孙忠良 Blog, 作者 [@sunzhongliang] , 转载请保留原文链接.

CATALOG
    FEATURED TAGS
    OC 算法 前端 swift 数据结构
    FRIENDS