使用js实现链表

- 日理万妓 2022-05-08 15:08 185阅读 0赞

>        链表是一种动态的数据结构，不同于数组的是，链表分配内存空间的灵活性，它不会像数组一样被分配一块连续的内存。当你想在数组的任意位置，插入一个新值的时候，必须对数组中的各个元素进行相应的位置移动才能达到目标，开销显然是很大的。然而链表的灵活性在于它的每个元素节点分为两部分，一部分是存储元素本身，另一部分是指向下一个节点元素的引用，也可以称为指针，当你要插入数据时，把上一个节点的向下指针指向新数据节点，新数据节点的向下指针指向原有数据。但是链表不像数组那样可以直接通过索引立刻定位，只能通过遍历。

*  单链表

function List() {       
        this.head = new Node("head");
        this.find = find;
        this.insert = insert;
        this.remove = remove;
        this.getAll= getAll;
        this.findPrevious = findPrevious;        
    }
    
    function Node(element) {
        this.element = element;
        this.next = null;
    }
    
    function find(item) {
        var currNode = this.head;
        while(currNode.element != item) {
            currNode = currNode.next;
        }
        return currNode;
    }
    
    function insert(newElement,item) {
        var newNode = new Node(newElement);
        var current = this.find(item);
        if(current == null) 
            return console.log("can't find the item");
        newNode.next = current.next;
        current.next = newNode;
    }
    
    function remove(item) {
        var prevNode = this.findPrevious(item);
        if(prevNode.next != null)
            prevNode.next = prevNode.next.next;
    
    }
    
    function findPrevious(item) {
        var currNode = this.head;
        while(currNode.next != null && currNode.next.element != item) {
            currNode = currNode.next;
        }
        return currNode;
    }
    
    function getAll() {
        var current = this.head;
        while(current.next != null) {
            console.log(current.next.element);
            current = current.next;
        }
    }

*  双向链表

function LList() {           
        this.head = new LNode("head");
        this.findLast = findLast;
        this.insert = insert;
        this.remove = remove;
        this.getAll = getAll;
    }
    
    function LNode(element) {     //双向链表结点
        this.element = element;
        this.next = null;
        this.prev = null;
    }
    
    function insert(newElement.item) {
        var newNode = new Node(newElement);
        var current = this.find(item);
        newNode.next = current.next;
        current.next.prev = newNode;
        newNode.prev = current;
        current.next = newNode;
    }
    
    function remove(item) {
        var current = this.find(item);
        if(current.next != null) {
            current.prev.next = current.next;
            current.next.prev = current.prev;
            current.next = null;
            current.prev = null;
        }   
    }
    
    function findLast() {
        var currNode = this.head;
        while(current.next != null) {
            current = current.next;
        }
        return current;
    }
    
    function dispReverse() {            //反序显示双向链表的元素
        var currNode = this.findLast();
        while(currNode.prev != null) {
            console.log(currNode.element);
            currNode = currNode.prev;
        }
    }

*  循环链表

function CList() {                 
        this.head = new Node("head");
        this.head.next = this.head;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，185人围观）

还没有评论，来说两句吧...

相关阅读

相关 160. 相交链表（JS实现）

1 题目 > 编写一个程序，找到两个单链表相交的起始节点。 > 如下面的两个链表： > 在节点 c1 开始相交。 > 示例 1： > 输入：interse

喜欢ヅ旅行/ 2023年03月06日 03:20/ 0 赞/ 33 阅读

相关 148. 排序链表（JS实现）

1 题目 > 在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。 > 示例 1: > 输入: 4->2->1->3 > 输出: 1->

向右看齐/ 2023年03月04日 08:18/ 0 赞/ 64 阅读

相关 143. 重排链表（JS实现）

1 题目 > 给定一个单链表 L：L0→L1→…→Ln-1→Ln ， > 将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→… > 你不能只是单纯

╰+哭是因爲堅強的太久メ/ 2023年03月04日 08:16/ 0 赞/ 104 阅读

相关 141. 环形链表（JS实现）

1 题目 > 给定一个链表，判断链表中是否有环。 > 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos

绝地灬酷狼/ 2023年03月04日 08:15/ 0 赞/ 77 阅读

相关 86. 分隔链表（JS实现）

1 题目 > 给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。 > 你应当保留两个分区中每个节点的初始相对位置。

深藏阁楼爱情的钟/ 2023年02月19日 01:28/ 0 赞/ 20 阅读

相关 61. 旋转链表（JS实现）

1 题目 > 给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。 > 示例 1: > 输入: 1->2->3->4->5->NULL

矫情吗；*/ 2023年02月17日 08:59/ 0 赞/ 18 阅读

相关 328. 奇偶链表（JS实现）

1 题目 > 给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。 > 请尝试使用

太过爱你忘了你带给我的痛/ 2022年11月28日 00:42/ 0 赞/ 287 阅读

相关【JS】js链表

[https://juejin.im/post/6844904001557757959][https_juejin.im_post_6844904001557757959]

红太狼/ 2022年11月20日 08:03/ 0 赞/ 287 阅读

相关使用js实现链表

> 链表是一种动态的数据结构，不同于数组的是，链表分配内存空间的灵活性，它不会像数组一样被分配一块连续的内存。当你想在数组的任意位置，插入一个新值的时候，必须对数

- 日理万妓/ 2022年05月08日 15:08/ 0 赞/ 186 阅读

相关 JS实现单向链表、双向链表、循环链表

[https://cloud.tencent.com/developer/article/1114246][https_cloud.tencent.com_developer_

怼烎@/ 2021年12月23日 16:49/ 0 赞/ 506 阅读