数据结构与算法的重温之旅（四）——链表

迈不过友情╰ 2022-10-01 06:59 133阅读 0赞

# 一、链表概念 #

还记得上一篇文章中数组的概念吗，其实数组和链表都是线性表的一种，不过数组与链表有一点不同的是，链表是不需要连续内存空间来存储，它通过指针将一组零散的内存块串联起来使用。链表它的结构五花八门，常用的三种链表结构分别是**单链表、双向链表、循环链表和双向循环链表**。首先我们先将最简单的单链表。

# 二、单链表 #

上面有讲，链表是通过指针将一组零散的内存块串联在一起，其中这个内存块我们称之为链表的结点。为了将所有的结点串起来，每个结点除了存储数据之外还会记录链表上下一个结点的地址，这个记录下一个结点地址指针称作**后继指针next。单链表**如下图：

在图里有两个结点是十分特殊的，一个是**头结点**，另一个是**尾结点**。其中头结点是用来记录链表的基地址，有了它，我们可以遍历整条链表。而尾结点的特殊地方是指针不是指向下一个结点，而是指向一个**空地址NULL**，这里表示的是链表最后一个结点。

和数组一样，链表也支持数据的增加、删除和查找操作。由于数组是连续的，在进行随机的查找操作的时候时间复杂度是O(1)，而链表的话由于内存地址是不连续的，在单链表中每个结点只知道下一个结点的内存地址，所以在执行随机查找操作的时候是依次遍历整个链表，因此最好时间复杂度是O(1)，最坏时间复杂度为O(n)，平均时间复杂度为O(n)。

不过链表比数组多了一个有点就是链表在执行增加和删除操作的时候所要消耗的时间复杂度比数组小很多。由于数组是用连续的内存空间来存储数据，当执行删除或者增加操作的时候，为了保证数组空间的连续性，就必须对指定添加位置或者删除位置后面的数据进行数据迁移。而链表由于不是连续的内存空间来存储数据，并且链表当中的结点是知道下一个结点的内存地址，当我们执行添加操作的时候就只需把当前结点next指针指向要插入的数据，要插入的数据的next指针指向原来当前结点的下一个结点内存地址即可。同理在执行删除操作的时候只需把当前要被删除结点的上一个结点next指针指向被删除结点的下一个结点即可。由于增加和删除操作不需要对被操作结点后面数据进行迁移，所以增加和删除操作的时间复杂度都为O(1)。图解如下：

下面用JavaScript来实现单链表，可以把代码直接在浏览器上运行：

// 结点类
    class Node {
        /**
         * @param {string} element 链表结点值
         * **/
        constructor (element) {
            this.element = element
            this.next = null
        }
    }
    
    // 链表类
    class linkedList {
        constructor () {
            this.countLength = 0 // 链表长度
            this.head = null // 头节点
        }
        /**
         * @return {number} 链表长度
         * @description 获取链表长度方法
         * **/
        getLinkLength () {
            return this.countLength
        }
        /**
         * @param {string} item 链表结点的值
         * @return {linkedList} 返回链表结点
         * @description 链表查询方法
         * **/
        find (item) {
            let currNode = this.head
            while (currNode.element !== item) {
                currNode = currNode.next
            }
            return currNode
        }
        /**
         * @param {string} newElement 新的结点的值
         * @param {string} item 被插入结点的值
         * @description 链表结点插入方法
         * **/
        insertNode (newElement, item) {
            let newNode = new Node(newElement)
            if (this.head == null) {
                this.head = newNode
            }
            else {
                let currentNode = this.find(item)
                newNode.next = currentNode.next
                currentNode.next = newNode
            }
            ++this.countLength
        }
        /**
         * @param {string} item 被删除结点的值
         * @description 链表结点删除方法
         * **/
        removeNode (item) {
            let currNode = this.findPrevious(item)
            if (currNode.next != null) {
                currNode.next = currNode.next.next
                --this.countLength
            }
            else if (currNode && !currNode.next) {
                this.head = this.head.next
                --this.countLength
            }
        }
        /**
         * @param {string} item 查找结点的值
         * @return {linkedList} 返回一个当前要查找的上一个结点
         * @description 查找链表上一个结点
         * **/
        findPrevious (item) {
            let currNode = this.head
            while (currNode.next != null && currNode.next.element !== item) {
                currNode = currNode.next
            }
            return currNode
        }
        /**
         * @param {string} newItem 修改的新值
         * @param {string} item 修改的旧值
         * @description 链表结点编辑方法
         * **/
        editNode (newItem, item) {
            let currentNode = this.find(item)
            currentNode.element = newItem
        }
        /**
         * 链表展示方法
         * **/
        displayList () {
            let currNode = this.head
            while (currNode) {
                console.log(currNode.element)
                currNode = currNode.next
            }
        }
    }
    
    let myLink = new linkedList()
    myLink.insertNode('head')
    myLink.insertNode('ha', 'head')
    myLink.insertNode('ho', 'head')
    myLink.insertNode('he', 'head')
    myLink.removeNode('head')
    myLink.displayList()
    console.log(myLink.getLinkLength())复制代码

# 三、循环链表 #

其实循环链表是一个特殊的单链表。上面的单链表的尾结点的next指针指向的是NULL，而循环链表里的尾结点next指针却是头结点。循环链表的有点是从尾结点到头结点比较方便，这种结构的链表特别适合解决具有环形数据结构，比如约瑟夫问题，下一篇文章会讲解约瑟夫问题。循环链表的图解如下：

下面用JavaScript来实现一个循环链表，其实实现的代码和上面的单链表差不多，只不过在插入和删除的时候要判断边界:

// 结点类
    class Node {
        /**
         * @param {string} element 链表结点值
         * **/
        constructor (element) {
            this.element = element
            this.next = null
        }
    }
    
    // 链表类
    class linkedList {
        constructor () {
            this.countLength = 0 // 链表长度
            this.head = null // 头节点
        }
        /**
         * @return {number} 链表长度
         * @description 获取链表长度方法
         * **/
        getLinkLength () {
            return this.countLength
        }
        /**
         * @param {string} item 链表结点的值
         * @return {linkedList} 返回链表结点
         * @description 链表查询方法
         * **/
        find (item) {
            let currNode = this.head
            while (currNode.element !== item) {
                currNode = currNode.next
            }
            return currNode
        }
        /**
         * @param {string} newElement 新的结点的值
         * @param {string} item 被插入结点的值
         * @description 链表结点插入方法
         * **/
        insertNode (newElement, item) {
            let newNode = new Node(newElement)
            if (this.head == null) {
                this.head = newNode
            }
            else {
                let currentNode = this.find(item)
                if (currentNode.next == null || currentNode.next.element === this.head.element) {
                    newNode.next = this.head
                }
                else {
                    newNode.next = currentNode.next
                }
    
                currentNode.next = newNode
            }
            ++this.countLength
        }
        /**
         * @param {string} item 被删除结点的值
         * @description 链表结点删除方法
         * **/
        removeNode (item) {
            let currNode = this.findPrevious(item)
            if (currNode.next != null) {
                if (currNode.next.element === this.head.element) {
                    this.head = currNode.next.next
                    currNode.next = this.head
                }
                else {
                    currNode.next = currNode.next.next
                }
                --this.countLength
            }
            else if (currNode && !currNode.next) {
                this.head = null
                --this.countLength
            }
        }
        /**
         * @param {string} item 要被查找结点的值
         * @return {linkedList} 返回一个当前要查找的上一个结点
         * @description 查找链表上一个结点
         * **/
        findPrevious (item) {
            let currNode = this.head
            while (currNode.next != null && currNode.next.element !== item) {
                currNode = currNode.next
            }
            return currNode
        }
        /**
         * @param {string} newItem 修改的新值
         * @param {string} item 修改旧值的旧值
         * @description 链表结点编辑方法
         * **/
        editNode (newItem, item) {
            let currentNode = this.find(item)
            currentNode.element = newItem
        }
        /**
         * 链表展示方法
         * **/
        displayList () {
            let currNode = this.head
            while (currNode) {
                console.log(currNode.element)
                currNode = currNode.next
                if (currNode.element === this.head.element) break
            }
        }
    }
    
    let myLink = new linkedList()
    myLink.insertNode('head', '')
    myLink.insertNode('ha', 'head')
    myLink.insertNode('ho', 'head')
    myLink.insertNode('he', 'head')
    myLink.removeNode('head')
    myLink.displayList()
    console.log(myLink.getLinkLength())复制代码

# 四、双向链表 #

上面说到在单链表中，结点的next指针是指向它的下一个结点的内存地址，而双向链表则比单链表多了一个**前驱指针prev**指向它的上一个结点的内存地址。图解图下：

单链表和双向链表从结构上看的话，由于双向链表比单链表多了一个指向上一个结点的前驱指针，所以它的空间占用比单链表的大。不过由于比单链表多了一个前驱指针，使得它比单链表更加的灵活。比如在删除操作中，如果指定单链表某个结点删除的话，假设该结点不是头结点和尾结点，那么在删除之前我们是必须要知道该结点的上一点结点的内存地址，但由于单链表是无法往前遍历，所以需要遍历一遍链表来找到该结点的上一个结点的内存地址，才能够执行删除操作。而双向链表由于有一个前驱指针，所以并不需要遍历一遍链表才能进行删除操作。所以，整个删除流程双向链表比单链表要快，它的时间复杂度为O(1)。

可能各位同学看到这里会有点懵。这么上面说到单链表执行删除操作所要的时间复杂度是O(1)，而这里却是O(n)呢？其实单链表和双向链表执行删除操作的时间都是为O(1)，删除操作即把当前结点的上个结点的next指针指向当前结点下个结点的内存地址即可，但是它们中间整个删除流程有点区别，单链表是需要遍历链表找到前驱结点才能执行删除操作，而双向链表则不用遍历链表即可执行删除操作，这一点是有明显的差异的。

从这里我们可以发现，虽然双向链表牺牲了空间上的性能，却带来时间上性能的提升，在就是**以空间换时间**的设计思想。当我们的内存充足的时候，为了缩短程序运行时间，可以牺牲一定量的空间来换取时间性能上的提升。相反，如果空间资源比较短缺，我们则可以牺牲一点时间来换取空间上的优化。

下面用JavaScript来实现双向链表结构，方法比上面循环链表简单的地方在于不用判断插入和删除的是否在头尾结点，比单链表复杂的一点是在多了一个前驱指针，但是少了一个删除的时候需要上一个结点的遍历：

// 结点类
    class Node {
        /**
         * @param {string} element 链表结点值
         * **/
        constructor (element) {
            this.element = element
            this.next = null
            this.prev = null
        }
    }
    
    // 链表类
    class linkedList {
        constructor () {
            this.countLength = 0 // 链表长度
            this.head = null // 头节点
        }
        /**
         * @return {number} 链表长度
         * @description 获取链表长度方法
         * **/
        getLinkLength () {
            return this.countLength
        }
        /**
         * @param {string} item 链表结点的值
         * @return {linkedList} 返回链表结点
         * @description 链表查询方法
         * **/
        find (item) {
            let currNode = this.head
            while (currNode.element !== item) {
                currNode = currNode.next
            }
            return currNode
        }
        /**
         * @param {string} newElement 新的结点的值
         * @param {string} item 被插入结点的值
         * @description 链表结点插入方法
         * **/
        insertNode (newElement, item) {
            let newNode = new Node(newElement)
            if (this.head == null) {
                this.head = newNode
            }
            else {
                let currentNode = this.find(item)
                newNode.next = currentNode.next
                currentNode.next = newNode
                newNode.prev = currentNode
                if (newNode.next) {
                    newNode.next.prev = newNode
                }
            }
            ++this.countLength
        }
        /**
         * @param {string} item 被删除结点的值
         * @description 链表结点删除方法
         * **/
        removeNode (item) {
            let currNode = this.find(item).prev
            if (currNode) {
                currNode.next = currNode.next.next
                if (currNode.next.next) {
                    currNode.next.prev = currNode
                }
            }
            else {
                this.head = this.head.next
                this.head.prev = null
            }
            --this.countLength
        }
        /**
         * @param {string} newItem 修改的新值
         * @param {string} item 修改的旧值
         * @description 链表结点编辑方法
         * **/
        editNode (newItem, item) {
            let currentNode = this.find(item)
            currentNode.element = newItem
        }
        /**
         * 链表展示方法
         * **/
        displayList () {
            let currNode = this.head
            while (currNode) {
                console.log(currNode.element)
                currNode = currNode.next
            }
        }
    }
    
    let myLink = new linkedList()
    myLink.insertNode('head')
    myLink.insertNode('ha', 'head')
    myLink.insertNode('ho', 'head')
    myLink.insertNode('he', 'head')
    myLink.removeNode('head')
    myLink.displayList()
    console.log(myLink.getLinkLength())复制代码

# 五、双向循环链表 #

这个链表链表其实就是循环链表和双向链表的合体，比循环链表在空间上占用更多资源，不过同时也更加的灵活。图解如下：

下面用JavaScript来实现双向循环链表，如果读者按照上面那样能够熟练的写出单链表、双向链表和循环链表的话，相信这里的双向循环链表写起来则十分的得心应手：

// 结点类
    class Node {
        /**
         * @param {string} element 链表结点值
         * **/
        constructor (element) {
            this.element = element
            this.next = null
            this.prev = null
        }
    }
    
    // 链表类
    class linkedList {
        constructor () {
            this.countLength = 0 // 链表长度
            this.head = null // 头节点
        }
        /**
         * @return {number} 链表长度
         * @description 获取链表长度方法
         * **/
        getLinkLength () {
            return this.countLength
        }
        /**
         * @param {string} item 链表结点的值
         * @return {linkedList} 返回链表结点
         * @description 链表查询方法
         * **/
        find (item) {
            let currNode = this.head
            while (currNode.element !== item) {
                currNode = currNode.next
            }
            return currNode
        }
        /**
         * @param {string} newElement 新的结点的值
         * @param {string} item 被插入结点的值
         * @description 链表结点插入方法
         * **/
        insertNode (newElement, item) {
            let newNode = new Node(newElement)
            if (this.head == null) {
                this.head = newNode
            }
            else {
                let currentNode = this.find(item)
                if (currentNode.next) {
                    newNode.next = currentNode.next
                }
                else {
                    newNode.next = this.head
                }
                currentNode.next = newNode
                newNode.prev = currentNode
                if (newNode.next) {
                    newNode.next.prev = newNode
                }
            }
            ++this.countLength
        }
        /**
         * @param {string} item 被删除结点的值
         * @description 链表结点删除方法
         * **/
        removeNode (item) {
            let currNode = this.find(item)
            if (currNode.prev) {
                if (currNode.element === this.head.element) {
                    this.head = this.head.next
                }
                currNode.prev.next = currNode.next
                currNode.next.prev = currNode.prev
            }
            else {
                this.head = null
            }
            --this.countLength
        }
        /**
         * @param {string} newItem 修改的新值
         * @param {string} item 修改的旧值
         * @description 链表结点编辑方法
         * **/
        editNode (newItem, item) {
            let currentNode = this.find(item)
            currentNode.element = newItem
        }
        /**
         * 链表展示方法
         * **/
        displayList () {
            let currNode = this.head
            while (currNode) {
                console.log(currNode.element)
                currNode = currNode.next
                if (currNode.element === this.head.element) break
            }
        }
    }
    
    let myLink = new linkedList()
    myLink.insertNode('head')
    myLink.insertNode('ha', 'head')
    myLink.insertNode('ho', 'head')
    myLink.insertNode('he', 'head')
    myLink.removeNode('head')
    myLink.displayList()
    console.log(myLink.getLinkLength())复制代码

# 六、数组与链表的对比 #

通过前面内容的学习，你应该已经知道，数组和链表是两种截然不同的内存组织方式。正是因为内存存储的区别，它们插入、删除、随机访问操作的时间复杂度正好相反。不过，数组和链表的对比，并不能局限于时间复杂度。而且，在实际的软件开发中，不能仅仅利用复杂度分析就决定使用哪个数据结构来存储数据。

数组简单易用，在实现上使用的是连续的内存空间，可以借助 CPU 的缓存机制，预读数组中的数据，所以访问效率更高。而链表在内存中并不是连续存储，所以对 CPU 缓存不友好，没办法有效预读。数组的缺点是大小固定，一经声明就要占用整块连续内存空间。如果声明的数组过大，系统可能没有足够的连续内存空间分配给它，导致“内存不足（out of memory）”。如果声明的数组过小，则可能出现不够用的情况。这时只能再申请一个更大的内存空间，把原数组拷贝进去，非常费时。链表本身没有大小的限制，天然地支持动态扩容，我觉得这也是它与数组最大的区别。

除此之外，如果你的代码对内存的使用非常苛刻，那数组就更适合你。因为链表中的每个结点都需要消耗额外的存储空间去存储一份指向下一个结点的指针，所以内存消耗会翻倍。而且，对链表进行频繁的插入、删除操作，还会导致频繁的内存申请和释放，容易造成内存碎片，如果是 Java 语言，就有可能会导致频繁的 GC（Garbage Collection，垃圾回收）。所以，在我们实际的开发中，针对不同类型的项目，要根据具体情况，权衡究竟是选择数组还是链表。

# 七、关于指针 #

上面讲了那么多，反复的提到一个关键字指针。在C或C++语言里，就有指针这个概念，但是在JavaScript或者Java语言中，听到引用这个概念比较多，几乎很少有听到指针这个概念。其实指针和引用是用一个东西，都是存储所指对象的内存地址。对于指针的理解，有一句话总结：**将某个变量赋值给指针，实际上就是将这个变量的地址赋值给指针，或者反过来说，指针中存储了这个变量的内存地址，指向了这个变量，通过指针就能找到这个变量。**

# 八、总结 #

关于链表这个概念，上面已经讲述的差不多了，下面这里提几点在写链表代码时要注意的事项和技巧：

## 1.警惕指针丢失和内存泄漏 ##

指针丢失多数出现在增加或删除操作上，如下面代码所示：

> p.next = x; // 将 p 的 next 指针指向 x 结点；  
> x.next = p.next; // 将 x 的结点的 next 指针指向 b 结点；

这里插入了一个结点x，这行代码里，p结点的next指针被指向到x结点上，按道理x结点的next指针是要指向p结点的next指针的结点，但是由于这行代码的顺序问题，x的next指针指回x结点，使得链表在x结点处发生了断裂。所以在执行链表的插入和删除操作时要十分注意顺序。在C语言里，由于内存垃圾需要程序员自己回收，所以在执行链表删除的时候要记得回收掉垃圾，防止内存泄漏。

## 2.利用带头链表来简化实现难度 ##

从上面的这四个代码来看，我们可以看出，针对链表的插入、删除操作，需要对插入第一个结点和删除最后一个结点的情况进行特殊处理。这样代码实现起来就会很繁琐，不简洁，而且也容易因为考虑不全而出错。如何来解决这个问题呢？

这里就可以利用哨兵结点来解决了。哨兵，解决的是国家之间的边界问题。同理，这里说的哨兵也是解决“边界问题”的，不直接参与业务逻辑。如果我们引入哨兵结点，在任何时候，不管链表是不是空，head 指针都会一直指向这个哨兵结点。我们也把这种有哨兵结点的链表叫**带头链表**，相反，没有哨兵结点的链表就叫作**不带头链表**。

下面用图和代码来让各位同学一目了然：

// 结点类
    class Node {
        /**
         * @param {string} element 链表结点值
         * **/
        constructor(element) {
            this.element = element
            this.next = null
        }
    }
    
    // 链表类
    class linkedList {
        constructor () {
            this.head = new Node('head')
        }
        /**
         * @param {string} item 链表结点的值
         * @return {linkedList} 返回链表结点
         * @description 链表查询方法
         * **/
        find (item) {
            let currNode = this.head
            while (currNode.element != item) {
                currNode = currNode.next
            }
            return currNode
        }
        /**
         * @param {string} newElement 新的结点的值
         * @param {string} item 被插入结点的值
         * @description 链表结点插入方法
         * **/
        insertNode (newElement, item) {
            let newNode = new Node(newElement)
            let current = this.find(item)
            newNode.next = current.next
            current.next = newNode
        }
        /**
         * @param {string} item 要被查找结点的值
         * @return {linkedList} 返回一个当前要查找的上一个结点
         * @description 查找链表上一个结点
         * **/
        findPrevious (item) {
            let currNode = this.head
            while (!(currNode.next == null) && (currNode.next.element != item)) {
                currNode = currNode.next
            }
            return currNode
        }
        /**
         * @param {string} item 被删除结点的值
         * @description 链表结点删除方法
         * **/
        removeNode (item) {
            let prevNode = this.findPrevious(item)
            if (!(prevNode.next == null)) {
                prevNode.next = prevNode.next.next
            }
        }
        /**
         * @param {string} newItem 修改的新值
         * @param {string} item 修改的旧值
         * @description 链表结点编辑方法
         * **/
        editNode (item, newItem) {
            let element = this.find(item)
            element.element = newItem
        }
        /**
         * 链表展示方法
         * **/
        displayList () {
            let currNode = this.head
            while (!(currNode.next == null)) {
                console.log(currNode.next.element)
                currNode = currNode.next
            }
        }
    }复制代码

## 3.注意链表的边界问题 ##

软件开发中，代码在一些边界或者异常情况下，最容易产生 Bug。链表代码也不例外。要实现没有 Bug 的链表代码，一定要在编写的过程中以及编写完成之后，检查边界条件是否考虑全面，以及代码在边界条件下是否能正确运行。

下面有几个注意点需要大家注意的：

### 1.如果链表为空时，代码是否能正常工作？ ###

### 2.如果链表只包含一个结点时，代码是否能正常工作？ ###

### 3.如果链表只包含两个结点时，代码是否能正常工作？ ###

### 4.代码逻辑在处理头结点和尾结点的时候，是否能正常工作？ ###

当你写完链表代码之后，除了看下你写的代码在正常的情况下能否工作，还要看下在上面我列举的几个边界条件下，代码仍然能否正确工作。如果这些边界条件下都没有问题，那基本上可以认为没有问题了。当然，边界条件不止我列举的那些。针对不同的场景，可能还有特定的边界条件，这个需要你自己去思考，不过套路都是一样的。

上一篇文章：[数据结构与算法的重温之旅（三）——数组][Link 1]

下一篇文章：[数据结构与算法的重温之旅（五）——如何运用链表][Link 2]

转载于:https://juejin.im/post/5ce8d8e56fb9a07ef376442c

[Link 1]: https://juejin.im/post/5ce584e2518825685e02bbdf
[Link 2]: https://juejin.im/post/5cf63aaaf265da1ba56b0af8