链表（上）

链表：一种线性数据结构，通过“指针”将一组零散的内存串联起来，来存储数据。

组成链表各部分的称谓：

• 节点：每一个内存块称为链表的节点

• 后继指针 next：记录下一个节点地址的指针

• 头节点：习惯把第一个节点叫做头节点

• 尾节点：习惯把最后一个节点叫做尾节点。一个特殊的地方，指针不是指向下一个节点，而是指向一个空地址 NULL，表示这是链表上最后一个节点。

那问题来了，什么是线性表的数据结构呢？使用“指针”串联一组零散内存的意义在那里？为何能支持存储不同类型的数据呢？

线性表

非线性表

单链表的具体形式可以看下图：

单链表

单链表的插入、删除、随机访问操作及程序：

单链表的插入、删除

/**
 * 1）单链表的插入、删除、查找操作；
 * 2）链表中存储的是int类型的数据；
 */
class Node {
    constructor (element) {
        this.element = element
        this.next = null
    }
}
class LinkedList {
    constructor () {
        this.head = new Node('head')
    }
    // 根据value查找节点
    findByValue (item) {
        let currentNode = this.head.next
        while (currentNode !== null && currentNode.element !== item) {
            currentNode = currentNode.next
        }
        console.log(currentNode)
        return currentNode === null ? -1 : currentNode
    }

    // 指定元素向后插入
    insert (newElement, element) {
        const currentNode = this.findByValue(element)
        if (currentNode === -1) {
            console.log('未找到插入位置')
            return
        }
        const newNode = new Node(newElement)
        newNode.next = currentNode.next
        currentNode.next = newNode
    }

    // 根据值删除
    remove (item) {
        const prevNode = this.findPrev(item)
        if (prevNode === -1) {
            console.log('未找到元素')
            return
        }
        prevNode.next = prevNode.next.next
    }
}

三种最常见的链表结构：

• 循环链表

  • 循环链表的尾节点指针指向链表的头节点。

    • 循环链表内存示意图

• 双向链表

  • 每一个节点支持两个方向：前驱指针prev指向前面的节点，后继指针指向next指针。在消耗更多内存的同时，可以访问前一个节点，更加高效（用空间换时间）。实际开发中，使用的也更加广泛。

    • 双向链表内存示意图

• 双向循环链表

  • 双向循环链表内存分布图

数组基本功能实现程序

 * 1）单链表的插入、删除、查找操作；
 * 2）链表中存储的是int类型的数据；
 */
class Node {
    constructor (element) {
        this.element = element
        this.next = null
    }
}
​
class LinkedList {
    constructor () {
        this.head = new Node('head')
    }
    // 根据value查找节点
    findByValue (item) {
        let currentNode = this.head.next
        while (currentNode !== null && currentNode.element !== item) {
            currentNode = currentNode.next
        }
        console.log(currentNode)
        return currentNode === null ? -1 : currentNode
    } 

    // 根据index查找节点，下标从0开始
    findByIndex (index) {
        let currentNode = this.head.next
        let pos = 0
        while (currentNode !== null && pos !== index) {
            currentNode = currentNode.next
            pos++
        }
        console.log(currentNode)
        return currentNode === null ? -1 : currentNode
    }
​
    // 向链表末尾追加节点
    append(newElement) {
        const newNode = new Node(newElement)
        let currentNode = this.head
        while(currentNode.next) {
            currentNode = currentNode.next
        }
        currentNode.next = newNode
    }

    // 指定元素向后插入
    insert (newElement, element) {
        const currentNode = this.findByValue(element)
        if (currentNode === -1) {
            console.log('未找到插入位置')
        return
    }
        const newNode = new Node(newElement)
        newNode.next = currentNode.next
        currentNode.next = newNode
    } 

    // 查找前一个
    findPrev (item) {
        let currentNode = this.head
        while (currentNode.next !== null && currentNode.next.element !== item) {
            currentNode = currentNode.next
        }
        if (currentNode.next === null) {
            return -1
        }
        return currentNode
    } 

    // 根据值删除
    remove (item) {
        const prevNode = this.findPrev(item)
        if (prevNode === -1) {
            console.log('未找到元素')
            return
        }
        prevNode.next = prevNode.next.next
    }

    // 遍历显示所有节点
    display () {
        let currentNode = this.head.next // 忽略头指针的值
        while (currentNode !== null) {
            console.log(currentNode.element)
            currentNode = currentNode.next
        }
    }
}
// Test
const LList = new LinkedList()
LList.append('chen')
LList.append('curry')
LList.append('sang')
LList.append('zhao') // chen -> curry -> sang -> zhao
console.log('-------------insert item------------')
LList.insert('qian', 'chen') // 首元素后插入
LList.insert('zhou', 'zhao') // 尾元素后插入
LList.display() // chen -> qian -> curry -> sang -> zhao -> zhou
console.log('-------------remove item------------')
LList.remove('curry')
LList.display() // chen -> qian -> sang -> zhao -> zhou
console.log('-------------find by item------------')
LList.findByValue('chen')
console.log('-------------find by index------------')
LList.findByIndex(2)
console.log('-------------与头结点同值元素测试------------')
LList.insert('head', 'sang')
LList.display() // chen -> qian -> sang -> head -> zhao -> zhou
LList.findPrev('head') // sang
LList.remove('head')
LList.display() // chen -> qian -> sang -> zhao -> zhou

相关章节：链接
相关程序：链接