用JavaScript撸一个静态链表

红太狼 2024-03-17 11:47 5阅读 0赞

最近重新开始翻起《大话数据结构》，看到了静态链表部分里面讲C语言是利用数组模拟，觉得十分有趣。但是在JavaScript中，也可以用类似的方式去实现，定义一个数据域和一个结点域，然后实现链表的基础操作。弱类型语言没有指针，所以需要自己区实现。算法的乐趣就在于解决一些思路上的问题，直击问题的本质。  
首先可以定义Node类，如下所示：

class Node {
        constructor(value) {
            this.data = value;
            this.next = null;
        }
    }

然后实现StaticLinkedList类，先定义简单的append和display方法：

class StaticLinkedList {
        constructor() {
            this.head = null;
            this.length = 0;
        }
    
        append(value) {
            const newNode = new Node(value);
            this.length++;
            if (this.head === null) {
                this.head = newNode;
                return;
            }
            let current = this.head;
            while (current.next != null) {
                current = current.next;
            }
            current.next = newNode;
        }
    
        display() {
            console.log('the static linked list is:\r\n');
            let current = this.head;
            if (current === null) {
                console.log('empty!');
                return;
            }
            while (current !== null) {
                console.log(JSON.stringify(current));
                console.log(`its value is ${current.data}\r\n`);
                current = current.next;
            }
        }
    }

其中append方法是在链表尾部添加新的Node对象，display方法可以打印出Node对象和它的数据。使用这个静态链表类也很简单，比如添加4个结点到这个链表里面：

const staticLinkedList = new StaticLinkedList();
    staticLinkedList.append(3);
    staticLinkedList.append(7);
    staticLinkedList.append(16);
    staticLinkedList.append(24);

我们还应该提供更加灵活添加结点的方法，比如我想在第三个结点位置插入一个新的结点，数值为11，那么现有的append方法就不适用了，需要定义一个新的插入结点的方法，代码如下：

/**
         * Method to insert an new element at the specific location
         *
         * @param {*} elementValue the value of the element that to be inserted
         * @param {*} index the position of the element, from 1 to maximum of the list
         * @returns true/false
         */
        insertAt(elementValue, index) {
            if (index < 1 || index > this.length + 1) {
                console.log('index is out of the range!');
                return false;
            }
    
            const newNode = new Node(elementValue);
            let startPos = 1;
            let current = this.head;
            while (startPos < index - 1) {
                current = current.next;
                startPos++;
            }
            newNode.next = current.next;
            current.next = newNode;
            this.length++;
            return true;
        }

这段代码需要理解的是新结点如何添加到链表的那两行代码，首先是newNode.next = current.next,这行代码是把新结点的next指向了原来插入前位置的结点的下一个结点。然后current.next = nextNode，把新结点替换掉原来该位置的结点。

为了更好地理解，我画了一张示意图：

![79a4a077d06813a08f5765039ebc6289.png][]

要注意的是step1和step2的顺序不能颠倒，否则会导致代码运行错误。

然后我们还需要定义一个移除指定位置结点的方法，如下所示：

removeAt(index) {
            if (index < 1 || index > this.length + 1) {
                console.log('index is out of the range!');
                return;
            }
            let current = this.head;
            let startPos = 1;
            let previous = null;
            while (startPos < index) {
                previous = current;
                current = current.next;
                startPos++;
            }
    
            previous.next = current.next;
            this.length--;
        }

我对previous.next = current.next也画了一张示意图，删除原来结点，需要把它前面一个结点的next指向该结点的next。

![9de93183002d2cf42c5adac6daf16fe9.png][]

**总结：**  
静态链表的添加和移除略有不同，需要利用Node中的next进行模拟指针操作，让新的结点加入到链表，让需要被删除的结点直接从上一个结点的next指向到原有结点的next。

[79a4a077d06813a08f5765039ebc6289.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/770b1df78b5642c4a20fb625cd258098.png
[9de93183002d2cf42c5adac6daf16fe9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/654e129c5d1e4a3ebff543c3ea37f30c.png