JavaScript数据结构（三）链表

1740

多个元素组成的列表

元素存储不连续，用next指针连在一起

JavaScript中没有链表

可以使用Object模拟链表

数组 VS 链表

数组：增删非首位元素时需要移动元素

链表：增删非首位元素时，不需要移动元素，只需要更改next的指向即可

1. 定义

存储有序的元素集合

不是连续放置的

一个存储元素本身的节点 + 一个指向下一个元素的引用

image-20210423215543759

2. 具体操作

创建

class Node {  //表示想要添加到链表中的项
    constructor(element, next) {
      this.element = element;
      this.next = next;  //指向链表中下一个元素的指针
    }
}

class LinkedList {
    constructor() {
    this.count = 0;
    this.head = undefined; //保存引用
    }
}
复制代码

方法

//返回特定位置的元素
getElementAt(index) {
    if (index >= 0 && index <= this.count) {
      let node = this.head;
      for (let i = 0; i < index && node != null; i++) {
        node = node.next;  //通过循环，使得node指向index元素
      }
      return node;
    } 
    throw new Error("out range");
}

//返回元素在链表中的索引。如果链表中没有该元素则返回-1
indexOf(element) {
    let current = this.head;
    for (let i = 0; i < this.size() && current != null; i++) {
      if (current.element === element) {
        return i;
      }
      current = current.next;
    }
    return -1;
}

//向尾部添加一个新元素
push(element) {
    let node = new Node(element);
    if (this.head == null) {  //如果是空链表，直接加到头部
      this.head = node;
    } else {
        let current = this.head;
        while (current.next != null) { //获得最后一项
            current = current.next;
        } 
        //当current.next == undefined||null时，即到达链表尾部
        //**链表最后一个节点的下一个元素始终是undefined或null**
        current.next = node;  //将其next赋为新元素，建立链接
    }
    this.count++;
}
//也可以使用这个方法
// ……
// else {
//      **let current = this.getElementAt(this.count - 1);**  //找到node
//      **current.next = node;**
//     }
// ……

//向特定位置插入一个新元素
insert(element, index) {
    if (index >= 0 && index <= this.count) {  //在范围内
        let node = new Node(element);
        if (index === 0) {  //在头部直接加
            const current = this.head;
            node.next = current;
            this.head = node;
        } else {
            const pre = this.getElementAt(index - 1);  //获得前一个节点的位置
            node.next = pre.next; //新创建的节点赋值为pre.next
            pre.next = node;  //将pre.next指向新创建的节点
        }
        this.count++;  //长度+1
        return true;
    }
    throw new Error("out range");
}

//从特定位置移除一个元素
removeAt(index) {
    if (index >= 0 && index < this.count) {
        let current = this.head;
        if (index === 0) { //移除第一项
            this.head = current.next; //也可以使用head=head.next
        } else {
            for (let i = 0; i < index; i++) {  //从移除的位置开始，其后元素往前移一位
                let pre = current;
                current = current.next;
            }
            //pre为要移除元素的前一位，next指针指向移除元素的下一位，即实现了移除元素
            pre.next = current.next; 
        }
        this.count--;
        return current.element;
    }
    return undefined; //如果index不在范围内，返回undefined
}

//移除一个元素
remove(element) {
    const index = this.indexOf(element);
    return this.removeAt(index);
}

isEmpty() {
	return this.size() === 0;
}

size() {
	return this.count;
}

getHead() {
	return this.head;
}

clear() {
    this.head = undefined;
    this.count = 0;
}

//把LinkedList对象转换成一个字符串
toString() {
    if (this.head == null) {
      return '';
    }
    let objString = `${this.head.element}`;
    let current = this.head.next;
    for (let i = 1; i < this.size() && current != null; i++) {
      objString = `${objString},${current.element}`;
      current = current.next;
    }
    return objString;
}
复制代码

image-20210424130232992

3. 双向链表

链接是双向的：一个链向下一个元素，另一个链向前一个元素

image-20210425190521544

优势：在单向链表中，如果迭代时错过了要找的元素，就需要回到起点重新开始迭代

双向链表要同时控制 next 和 prev 这两个指针

class Node {
    constructor(element, next) {
      this.element = element;
      this.next = next; 
    }
}

function defaultEquals(a, b) {
    return a === b;
}

class LinkedList {
    constructor(equalsFn = defaultEquals) {
    this.count = 0;
    this.head = undefined;
    this.equalsFn = equalsFn;
    }
}

class DoublyNode extends Node {
    constructor(element,next,prev) {
        super(element,next);
        this.prev = prev;
    }
}

class DoublyLinkedList extends LinkedList {
    constructor(equalasFn = defaultEquals) {
        super(equalasFn);
        this.tail = undefined;
    }
}
复制代码
insert(element, index) {
    if (index >= 0 && index <= this.count) {
        const node = new DoublyNode(element);
        let current = this.head;
        if (index === 0) {
            if(this.head == null) { //空链表，直接让this.head和this.tail指向node即可
                this.head = node;
                this.tail = node;
            } else {
                node.next = this.head;
                current.prev = node; 
                this.head = node;
            }
        }else if (index === this.count) { //插入到末尾
            current = this.tail;
            current.next = node;
            node.prev = current;
            this.tail = node;
        } eles {
            const previous = this.getElementAt(index - 1); //查找插入点前一个位置
            current = previous.next;
            node.next = current;
            previous.next = node;
            current.prev = node;
            node.prev = previous;
        }
        this.count++;
        return true;
    }
    return false;
}

removeAt(index) {
    if (index >= 0 && index < this.count) { //在范围内
        let current = this.head;
        if (index === 0) {
            this.head = current.next;
            if (this.count === 1) {
                this.tail = undefined;
            } else {
                this.head.prev = undefined;
            }
        } else if (index === this.count - 1) { //删除最后一个元素
            current = this.tail;
            this.tail = current.prev;
            this.tail.next = undefined;
        } else {
            current = this.getElementAt(index);
            const previous = current.prev;
            previous.next = current.next;
            current.next.prev = previous;
        }
        this.count--;
        return current.element;
    }
    return undefined;
}
复制代码

4. 循环链表

具有链表单项引用+双向链表双向引用

最后一个元素指向下一个元素的指针（tail.next）指向第一个元素（head）

image-20210425202902743

双向循环链表：有指向head元素的tail.next和指向tail元素的head.prev

image-20210425203025901

class CircularLinkedList extends LinkedList {
    constructor(equalsFN = defaultEquals) {
        super(equalsFn);
    }
}
复制代码
insert(element, index) {
    if (index >= 0 && index <= this.count) {
        const node = new Node(element);
        let current = this.head;
        if(index === 0) { //插入点为链表的第一个位置
            if (this.head == null) { //该链表为空
                this.head = node;
                node.next = this.head;
            } else {
                node.next = current; //node的next指针指向头部
                current = this.getElementAt(this.size()); //最后一个元素
                this.head = node; //新增元素作为链表的头部
                current.next = this.head;  //最后一个元素再指向头部
            }
        } else {
            const previous = this.getElementAt(index - 1);
            node.next = previous.next;
            previous.next = node;
        }
        this.count++;
        return true;
    }
    return false;
}

removeAt(index) {
    if(index >= 0 && index < this.count) {
        let current = this.head;
        if(index === 0) { //移除第一个元素
            if(this.size() === 1) {
                this.head = undefined; //只有一个元素，直接让头部为undefined
            } else {
                const removed = this.head;
                current = this.getElementAt(this.size()); //最后一个元素
                this.head = this.head.next;  //头部元素变成下一个元素
                current.next = this.head;  //最后一个元素next指针指向头部
                current = removed;  //获得移除的元素，后面return移除元素的值
            }
        } else {
            const previous = this.getElementAt(index - 1);
            current = previous.next;
            previous.next = current.next;
        }
        this.count--;
        return current.element;
    }
    return undefined;
}
复制代码

5. 有序链表

保持元素有序的链表结构

const Compare = {
    LESS_THAN: -1,
    BIGGER_THAN: 1
};
function defaultCompare(a,b) {
    if (a === b) {
        return 0;
    }
    return a < b ? Compare.LESS_THAN : Compare.BIGGER_THAN;
}
class SortedLinkedList extends LinkedList {
    constructor(equalsFn = defaultEquals, compareFn = defaultCompare) {
        super(equalsFn);
        this.compareFn = compareFn;
    }
}
复制代码
insert(element, index = 0) {
    if(this.isEmpty()) {
        return super.insert(element,0);
    }
    const pos = this.getIndexNextSortedElement(element);
    return super.insert(elemenet,pos);
}

getIndexNextSortedElement(element) {
    let current = this.head;
    let i = 0;
    for(; i < this.size() && current; i++) {
        const comp = this.compareFn(element,current.element);
        if(comp === Compare.LESS_THAN) {
            return i;
        }
        current = current.next;
    }
    return i;
}
复制代码

6. 创建StackLinkedList 类

class StackLinkedList {
    constructor() {
    	this.items = new DoublyLinkedList(); // {1}
    }
    push(element) {
        this.items.push(element); // {2}
    }
    pop() {
        if (this.isEmpty()) {
            return undefined;
    }
    return this.items.removeAt(this.size() - 1); // {3}
    }
}
复制代码

7. LeetCode题

LeetCode206

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function(head) {
    let p1 = head;
    let p2 = null;
    while(p1) {
        const tmp = p1.next;
        p1.next = p2; //指向前一个指针
        p2 = p1; 
        p1 = tmp; 
    }
    return p2; //p1已经跑不见了
};
复制代码

大致的思路：

翻转节点，将n+1的next指向n

具体操作：

创建一对快慢指针，p1指向头部，p2指向null（慢于p1）

当p1存在时，将p1.next用tmp存起来，p1.next指向前一个指针，p2、p1向右走，直到所有节点都翻转过来

LeetCode2

var addTwoNumbers = function(l1, l2) {
    const l3 = new ListNode(0)
    let p1 = l1
    let p2 = l2
    let p3 = l3
    let carry = 0  //存放上一个val的个位数
    while(p1 || p2) {
        const v1 = p1 ? p1.val:0
        const v2 = p2 ? p2.val:0
        const val = v1 + v2 + carry  //加起来
        carry = Math.floor(val / 10)  //取出十位数
        p3.next = new ListNode(val % 10)  //把个位数加上去
        //p1 p2向右走
        if(p1) p1 = p1.next  
        if(p2) p2 = p2.next
        p3 = p3.next
    }
    if(carry) {
        p3.next = new ListNode(carry)  //把carry也放进去
    }
    return l3.next
};
复制代码

LeetCode83

var deleteDuplicates = function(head) {
    let p = head;
    while(p && p.next) {
        if(p.val === p.next.val){
            p.next = p.next.next;
        }else {
            p = p.next;
        }
    }
    return head;
    
};
复制代码

LeetCode141

var hasCycle = function(head) {
    let slow = head;
    let fast = head;
    while(slow && fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;
        if(slow === fast){
            return true;
        }
    }
    return false;
};
复制代码

快慢指针： 快慢指针遇上，表明有环

© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
前端
喜欢就支持一下吧
点赞0 分享
AI-robot的头像-一一网
asgbookphp ‘index.php’ 跨站脚本攻击漏洞-一一网
asgbookphp ‘index.php’ 跨站脚本攻击漏洞
asgbookphp ‘index.php’ 跨站脚本攻击漏洞
14年前 2.6W+
机器学习之随机森林回归篇（RandomForestRegressor）-一一网
机器学习之随机森林回归篇（RandomForestRegressor）
机器学习之随机森林回归篇（RandomForestRegressor）
4年前 4202
详解数仓中的数据分层：ODS、DWD、DWM、DWS、ADS-一一网
详解数仓中的数据分层：ODS、DWD、DWM、DWS、ADS
详解数仓中的数据分层：ODS、DWD、DWM、DWS、ADS
4年前 3895
DZCP Clanportal ＇Index.PHP＇任意文件上载漏洞-一一网
DZCP Clanportal ＇Index.PHP＇任意文件上载漏洞
DZCP Clanportal ＇Index.PHP＇任意文件上载漏洞
19年前 3842
Wireshark之抓包文件保存-一一网
Wireshark之抓包文件保存
Wireshark之抓包文件保存
4年前 3406
支付宝生活号H5接入支付宝支付流程-一一网
支付宝生活号H5接入支付宝支付流程
支付宝生活号H5接入支付宝支付流程
3年前 3135
相关推荐
支付宝生活号H5接入支付宝支付流程-一一网
支付宝生活号H5接入支付宝支付流程
支付宝生活号H5接入支付宝支付流程
3年前 3135
手摸手教你实现vue的动态路由（addRoute版）-一一网
手摸手教你实现vue的动态路由（addRoute版）
手摸手教你实现vue的动态路由（addRoute版）
4年前 3118
Unity实用功能之使用TextMeshPro组件-一一网
Unity实用功能之使用TextMeshPro组件
Unity实用功能之使用TextMeshPro组件
4年前 3062
vue 项目运行报错：npm ERR! This is probably not a problem with npm. There is likely …-一一网
vue 项目运行报错：npm ERR! This is probably not a problem with npm. There is likely …
vue 项目运行报错：npm ERR! This is probably not a problem with npm. There is likely …...
4年前 2847
Windi CSS 在 Vue3 + Vite 项目中的使用-一一网
Windi CSS 在 Vue3 + Vite 项目中的使用
Windi CSS 在 Vue3 + Vite 项目中的使用
3年前 2728
vue3 使用 qrcode.vue 生成二维码-一一网
vue3 使用 qrcode.vue 生成二维码
vue3 使用 qrcode.vue 生成二维码
4年前 2621
搜索
开启精彩搜索
世界，您好！-一一网
3.7W+人已阅读
世界，您好！
TOP1
番茄社区无限观看+付费视频破解教程-一一网
番茄社区无限观看+付费视频破解教程
5年前3.2W+人已阅读
TOP2
香蕉视频v3.8.3_VIP会员破解教程-一一网
香蕉视频v3.8.3_VIP会员破解教程
5年前3.1W+人已阅读
TOP3
[桜井宁宁]COS和泉纱雾超可爱写真福利集-一一网
密码保护：[桜井宁宁]COS和泉纱雾超可爱写真福利集
5年前2.8W+人已阅读
TOP4
[桜井宁宁] 爆乳奶牛少女cos写真-一一网
密码保护：[桜井宁宁] 爆乳奶牛少女cos写真
5年前2.8W+人已阅读
TOP5
快猫v1.1.7会员破解版_最新快猫vip破解教程大全-一一网
快猫v1.1.7会员破解版_最新快猫vip破解教程大全
5年前2.7W+人已阅读
TOP6
标签云
默认路由黑裙黑群晖麦克风车机鸿蒙系统鸿蒙系统鸿蒙OS鸿蒙驱动软件驱动题库音频剪辑音乐剪辑面板面具静态雷石集群随机阿里云