数据结构之链表

链表相较于数组的优缺点

1. 链表在插入、删除、移动数据效率比数组要高，数组插入、移动、删除数据需要改变没有数据的索引，而链表则只需要更改指针即可

2. 在查询方面，数组要优于链表，数组存储的数据是连续的，可以直接通过位置信息读取到数据，而链表则需要通过遍历的方式找到对应的指针

3. 灵活性方面，传统的数组是需要固定长度的，而链表则可以是任意长度

备注：JavaScript中会根据实际情况，将数组转换为快数组或者慢数组（掘金的文章：https://juejin.cn/post/6844903943638794248#heading-0）

链表图解：

链表实现（实现了循环链表、双向链表、单项链表）：

// 创建链表
class Node {
    constructor(element) {
        this.element = element
        this.next = null
        // 实现双向链表指针
        this.prev = null
    }
}
class SingleList {
    constructor() {
        this.size = 0
        this.head = null
        this.tail = this.head
    }

    // 在尾部添加元素
    append(element) {
        const newNode = new Node(element)
        // 实现循环链表（其实就是将最后一个元素的指针指向 head）
        // newNode.next = this.head
        if (!this.head) {
            this.head = newNode
        } else {
            this.tail.next = newNode
            newNode.prev = this.tail
        }

        this.tail = newNode
        this.size++
    }
　　// 对 size 进行缓存，获取长度的时候直接返回即可
    getLength() {
        return this.size
    }

    find(element) {
        let _elm = this.head
        let i = 0
        // while(_elm) {} 因为实现了循环链表，_elm不可能为空
        while (i < this.size) {
            if (_elm.element === element) {
                return _elm
            }

            _elm = _elm.next
            i++
        }

        return null
    }
    // 删除指定元素
    remove(element) { 
        const _delItem = this.find(element)

        if(!_delItem) {
            return false
        }
　　　　// 通过改变指针选项实现
        const _oldNext = _delItem.next
        const prev = _delItem.prev
        prev.next = _oldNext

        return true
    }
　　// 或者最后一个元素，this.tail 已经进行缓存，故直接返回即可
    findLast() { return this.tail }

    insert(newItem, posItem) {
        if (posItem) {
            const pos = this.find(posItem)
            if (!pos) {
                return false
            }
　　　　　　　// 通过改变指针指向实现插入元素
            const oldNext = pos.next
            const newNext = new Node(newItem)
            newNext.prev = pos
            newNext.next = oldNext
            pos.next = newNext
        } else {
            this.append(newItem)
        }
    }
}

链表拓展算法：

1. 链表反转

function reverse(head) {
    let _newHead = null

    while(head) {
        const tmp = head.next
        head.next = _newHead 
        _newHead = head
        head = tmp       
    }

    return _newHead
}

// 模拟一个链表格式
const head = {"element":1,"next":{"element":2,"next":{"element":3,"next":null}}}
reverse(head)
// 分析一波：
// 第一次while(head = {"element":1,"next":{"element":2,"next":{"element":3,"next":null}}})：
//     const tmp = head.next // tmp -> {"element":2,"next":{"element":3,"next":null}}
//     head.next = _newHead // head -> {"element":1,"next": null }
//     _newHead = head // _newHead -> {"element":1,"next": null }
//     head = tmp // head -> {"element":2,"next":{"element":3,"next":null}}

// 第二次while(head = {"element":2,"next":{"element":3,"next":null}})：
//     const tmp = head.next // tmp -> {"element":3,"next":null}
//     head.next = _newHead // head -> {"element":2,"next": {"element":1,"next": null }}
//     _newHead = head // _newHead -> {"element":2,"next": {"element":1,"next": null }}
//     head = tmp // head -> {"element":3,"next":null}

// 第三次while(head = {"element":3,"next":null})：
//     const tmp = head.next // tmp -> null
//     head.next = _newHead // head -> {"element":3,"next":{"element":2,"next": {"element":1,"next": null }}}
//     _newHead = head // _newHead -> {"element":3,"next":{"element":2,"next": {"element":1,"next": null }}}
//     head = tmp // head -> null

2. 判断是否为回文链表

备注：这里使用快慢指针的方式实现时间复杂度O(n)，空间复杂度O(1)，也可以先将链表转为数组实现，时间复杂度O(n) 空间复杂度O(n)

// 判断是否是 回文链表
function isPalindrome(head) {
    if(!head || !head.next) {
        return true
    }
    let fast = head;
    let slow = head;
    let prev;
    while (fast && fast.next) {
        prev = slow;
        slow = slow.next;
        fast = fast.next.next;
    }
    // 断开链表
    prev.next = null

    // 翻转后半段链表
    let head2 = null
    while(slow) {
        const tmp = slow.next
        slow.next = head2
        head2 = slow
        slow = tmp
    }
    
    // 对比
    while(head && head2) {
        if(head.element !== head2.element) {
            return false
        }
        head = head.next
        head2 = head2.next
    }

    return true
}

JSVue技术相关

数据结构之链表

相关

标签