JavaScript实现一个链表结构源码分享

落日映苍穹つ 2023-01-12 04:26 141阅读 0赞

#### 写在前面 ####

> 刷题的时候看到一个关于链表的题目，写了一会发现写不出来，所以干脆就将链表的知识使用js重现一遍，这里写一个js实现的链表。

#### 链表结构介绍 ####

> 没有写代码之前呢我们先简单的说一下什么是链表，我们都知道，在很多的数据结构中，有序的结构我们比较熟悉是数组，数组和链表还有一些不同，数组是内存空间按照挨个顺序来的，那么链表的话是可以不按照顺序来的,链表结构是当前元素（data），下一个元素(next)，上一个元素(pre)，第一位是head，最后一位的next指向null 链表分为下面几种常见的！

*  单向链表

> 每一个节点的next都指向下一个节点，最后一个节点的next指向的是null  
> ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDg1NDE0_size_16_color_FFFFFF_t_70]

*  双向链表

> 每一个节点都有一个next和pre，相互指向就形成了双向链表  
> ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDg1NDE0_size_16_color_FFFFFF_t_70 1]

*  单向循环链表

> 单向链表的最后一个节点指向了该链表的第一个节点  
> ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDg1NDE0_size_16_color_FFFFFF_t_70 2]

*  双向循环链表

> 第一个节点的pre指向了该链表的最后一个，该链表的最后一个next指向了第一个节点  
> ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDg1NDE0_size_16_color_FFFFFF_t_70 3]

*  环形链表

> 任意两个节点之间形成了pre和next相互指向的情况，都可以叫做环形链表  
> ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDg1NDE0_size_16_color_FFFFFF_t_70 4]

#### 源码实现 ####

> 我们使用js实现一个简单的单向链表，提供一种思路出来

/** * @author clearlove * @class Node 当前节点 * @class LinkedList 当前链表 * @function appendNode 添加节点 * @function getNode 根据索引查找节点元素 * @function appendAt 根据位置插入节点 * @function remove 移除节点 * @function searchCurrIndexof 根据元素查找索引 * @function sort 链表排序 * @function linkedToArr 链表转为数组 * @function arrToLinked 数组转为链表 * */
    //声明一个Node节点
    class Node { 
        constructor(data) { 
            this.data = data
            this.next = null
        }
    }
    class LinkedList { 
        constructor() { 
                this.size = 0
                this.head = null
            }
            //增加一个节点
        appendNode(tempNode) { 
                let node = new Node(tempNode)
                    //判断一下当前的链表是不是一个空的 this.head === null 或者是当前的链表的长度为0
                if (this.head === null) { 
                    //如果是空的，那么我们的当前的节点就是第一位
                    this.head = node
                } else { 
                    //如果不是空的，我们要做的是，将当前的节点追加到当前链表的最后一位的后面，
                    //也就是我们首先需要找到当前链表的最后一位，让后将他的next给当前的node
                    let current = this.getNode(this.size - 1) //找到当前的最后一位
                    current.next = node
                }
                //链表的长度追加
                this.size++
            }
            //找到当前一个 的节点
        getNode(index) { 
                if (index < 0 || index >= this.size) { 
                    throw new Error('error')
                }
                let current = this.head
                for (let i = 0; i < index; i++) { 
                    current = current.next
                }
                return current
            }
            //按照指定位置增加
        appendAt(position, tempNode) { 
                //首先要知道当前的位置是不是小于0 或者是大于当前链表的长度
                if (position < 0 || position > this.size) { 
                    throw new Error('error')
                }
                let node = new Node(tempNode)
                if (position === 0) { 
                    //从第一位开始追加，说明我们需要将当前的node的下一位等于之前的第一位，再将head等于当前的node
                    node.next = this.head
                    this.head = node
                } else { 
                    //如果当前位置插入一个节点，需要做的就是将插入位置的之前节点的位置找到即可
                    let pre = this.getNode(position - 1)
                    node.next = pre.next
                    pre.next = node
                }
                this.size++
            }
            //删除指定节点的元素
        remove(position) { 
            //首先要知道当前的位置是不是小于0 或者是大于当前链表的长度
            if (position < 0 || position > this.size) { 
                throw new Error('error')
            }
            //先将当前头部节点找到
            let currentHead = this.head
            if (position === 0) { 
                //说明当前我要删除的是第一位的节点,那么更新头部的信息为之前的节点的next
                this.head = currentHead.next
            } else { 
                //如果链表中的某一个节点的删除的时候，我们需要做的就是找到删除的节点的前一个节点，然后将前一个节点的next等于被删除的节点的next
                let pre = this.getNode(position - 1)
                currentHead = pre.next
                pre.next = currentHead.next
            }
            this.size--
        }
    
        //按照指定元素的索引
        searchCurrIndexof(tempNode) { 
                //从头部开始找
                let current = this.head
                for (let i = 1; i < this.size; i++) { 
                    if (current.data === tempNode) { 
                        return i
                    }
                    current = current.next
                }
                //完全找不到的时候我们直接返回-1或者false都可以
                return -1
            }
            //排序
        sort(tempLinked) { 
                let tempArr = this.linkedToArr(tempLinked)
                let maxL = tempArr.length - 1
                for (let j = 0; j < maxL; ++j) { 
                    let flag = true
                    for (let i = 0; i < maxL - j; ++i) { 
                        if (tempArr[i] > tempArr[i + 1]) { 
                            let temp = tempArr[i]
                            tempArr[i] = tempArr[i + 1]
                            tempArr[i + 1] = temp
                            flag = false
                        }
                    }
                    if (flag) { 
                        break
                    }
                }
                return this.arrToLinked(tempArr)
            }
            //链表转为数组
        linkedToArr(tempLinked) { 
                let result = []
                let headNode = tempLinked.head
                while (headNode) { 
                    result.push(headNode.data)
                    headNode = headNode.next
                }
                return result
            }
            //数组转为链表
        arrToLinked(tempArr) { 
            let ll = new LinkedList()
            tempArr.map(res => { 
                ll.appendNode(res)
            })
            return ll
        }
    }

#### 测试结果 ####

//测试
    let ll = new LinkedList()
    ll.appendNode(1)
    ll.appendNode(2)
    ll.appendNode(3)
    ll.appendAt(3, 'jim')
    ll.appendNode(4)
    //这里是为了将结果全部展开，所以序列化一下
    console.log(JSON.stringify(ll))

#### 最后 ####

> 链表可能说我们平常用的不是很多，但是这是一种很好的思路，我觉得还是很有必要了解和学习一下的，毕竟很多的数据结构都是从一些简单的结构进行开展思维的。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDg1NDE0_size_16_color_FFFFFF_t_70]: /images/20221119/671d363a2a2a4268af57fc2cecfd0755.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDg1NDE0_size_16_color_FFFFFF_t_70 1]: /images/20221119/a1982c49cb0d40b698388340f4730c0c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDg1NDE0_size_16_color_FFFFFF_t_70 2]: /images/20221119/4cae6c5cd7654b6ca2528a2ff335e8bc.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDg1NDE0_size_16_color_FFFFFF_t_70 3]: /images/20221119/d044ab171839482ba1139467777cd17b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDg1NDE0_size_16_color_FFFFFF_t_70 4]: /images/20221119/82df4af435a542b88fbe712761ec14ee.png